Painless reconstruction from magnitudes of frame coefficients (Q1040679)

The paper is concerned with the problem of reconstructing a vector in a finite dimensional Hilbert space when only the magnitudes of the coefficients of the vector under a linear map are known. This question appears in signal processing and even in quantum state tomography, for example. The authors use a different approach as the former ones. Namely, they apply the concept of projective \(t\)-design and win a simple and efficient algorithm which requires \(d^2\) or \(d(d+1)/2\) coefficients (depending on the underlying field \(\mathbb{C}\) or \(\mathbb{R}\), respectively). To present the reconstruction formula, the notion of mutually unbiased bases will be given. Let \(H\) be a real or complex Hilbert space. A family of vectors \(\{e_k^{(j)}\}\subset H\), \((k=1,2,\dots,d; j=1,2,\dots,m)\) is said to form \(m\) mutually unbiased bases if for all appropriate \(j,j'\) and \(k,k'\), the equality \[ |\langle e_k^{(j)},e_{k'}^{(j')}\rangle|=\delta_{k,k'}\delta_{j,j'}+\frac{1}{\sqrt{d}}(1-\delta_{j,j'}) \] holds (here \(\delta\) is the usual Kronecker symbol). Reconstruction formula (Corollary 4.4): Let a family of vectors \(\{e_k^{(j)},k=1,2,\dots,d; j=1,2,\dots,m)\) that form \(d+1\) mutually unbiased bases in \(\mathbb{C}^d\) be given. Let us assume that the first set of these basis vectors \(\{e_k^{(1)}\}_{k=1}^d\) is the canonical orthonormal basis of \(\mathbb{C}^d\), and that the coefficients of our vector \(x\) in this basis are \(\{x_k\}_{k=1}^d\). If not all coefficients are zero, say \(x_1\neq0\), then for \(i=1,2,\dots,d\), \[ x_i=\frac{1}{\overline{x_1}}\sum_{j=1}^{d+1}\sum_{l=1}^d|\langle x,e_l^{(j)}\rangle|^2\langle e_1^{(1)},e_l^{(j)}\rangle\langle e_l^{(j)},e_i^{(1)}\rangle-\|x\|^2\delta_{i,1}. \] In the last section, so-called uniform tight frames are constructed to reduce the number of operations significantly. The previously described methods use \(O(d^2)\) frame coefficients but the suggested modification reduce the number of needed frame coefficients. (A frame is a generalization of a Hilbert space basis that is not necessarily linearly independent. A frame allows us to represent any vector as a set of frame coefficients, and to reconstruct a vector from its coefficients in a numerically stable way. -- A formal definition by R. Crandall.)