Painless Reconstruction from Magnitudes of Frame Coefficients

The goal of this paper is to develop fast algorithms for signal reconstruction from magnitudes of frame coefficients. This problem is important to several areas of research in signal processing, especially speech recognition technology, as well as state tomography in quantum theory. We present linear reconstruction algorithms for tight frames associated with projective 2-designs in finite-dimensional real or complex Hilbert spaces. Examples of such frames are two-uniform frames and mutually unbiased bases, which include discrete chirps. The number of operations required for reconstruction with these frames grows at most as the cubic power of the dimension of the Hilbert space. Moreover, we present a very efficient algorithm which gives reconstruction on the order of d operations for a d-dimensional Hilbert space.