Problem 35: Maximal Complex Equiangular Tight Frames

From Open Problems in Sublinear Algorithms
Revision as of 01:40, 13 November 2012 by Krzysztof Onak (talk | contribs) (Created page with "{{DISPLAYTITLE:Problem 35: Maximal Complex Equiangular Tight Frames}} {{Infobox |label1 = Proposed by |data1 = Joel Tropp |label2 = Source |data2 = [[Workshops:Kanpur_2009|Kan...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Proposed by Joel Tropp
Source Kanpur 2009
Short link http://sublinear.info/35

Consider a system of unit vectors $\{ x_k : k = 1, 2, \dots, N \}$ in $\mathbb{C}^d$. It can be shown that the maximum inner product among these vectors satisfies the Welch bound $$ \max_{i \neq j} |\langle x_i, x_j \rangle | \geq \sqrt{\frac{N-d}{d(N - 1)}}. $$ Miraculously, when this bound is attained, the modulus of the inner product between every pair of vectors is identical. Such a configuration is referred to as an equiangular tight frame (ETF).

It can be shown that the cardinality $N$ of an ETF is $\mathbb{C}^d$ must satisfy the bound $N \leq d^2$. When this bound is attained, the ETF is referred to as a maximal ETF. In other words, a maximal ETF is a system of $d^2$ unit vectors in $\mathbb{C}^d$ whose pairwise inner products share the modulus $(d+1)^{-1/2}$.

A striking geometric fact about maximal ETFs is that each one corresponds with a regular simplex consisting of $d^2$ points embedded in the set of rank-one, trace-one, complex, Hermitian matrices with dimension $d$. This correspondence is achieved by mapping each vector $x$ in the ETF to the matrix $xx^*$. Researchers believe that there is a maximal ETF for every dimension $d$. This question, so far, has resisted all efforts at solution.