Skip to main content
SpringerLink
Log in

Painless Reconstruction from Magnitudes of Frame Coefficients

  • Published:
Journal of Fourier Analysis and Applications Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Appleby, D.M.: Symmetric informationally complete-positive operator valued measures and the extended Clifford group. J. Math. Phys. 46(5), 052107 (2005)

    Article  MathSciNet  Google Scholar 

  2. Balan, R., Casazza, P., Edidin, D.: On signal reconstruction without phase. Appl. Comput. Harmon. Anal. 20, 345–356 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  3. Balan, R., Casazza, P., Edidin, D.: Equivalence of reconstruction from the absolute value of the frame coefficients to a sparse representation problem. IEEE Signal Process. Lett. 14, 341–343 (2007)

    Article  Google Scholar 

  4. Bandyopadhyay, S., Boykin, P.O., Roychowdhury, V., Vatan, F.: A new proof for the existence of mutually unbiased bases. Algorithmica 34(4), 512–528 (2002). Quantum computation and quantum cryptography

    Article  MATH  MathSciNet  Google Scholar 

  5. Bodmann, B.G.: Optimal linear transmission by loss-insensitive packet encoding. Appl. Comput. Harmon. Anal. 22, 274–285 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  6. Bodmann, B.G., Paulsen, V.I.: Frames, graphs and erasures. Linear Algebra Appl. 404, 118–146 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  7. Boykin, P.O., Sitharam, M., Tiep, P.H., Wocjan, P.: Mutually unbiased bases and orthogonal decompositions of Lie algebras. Quantum Inf. Comput. 7, 371–382 (2007)

    MATH  MathSciNet  Google Scholar 

  8. Calderbank, A.R., Cameron, P.J., Kantor, W.M., Seidel, J.J.: Z 4-Kerdock codes, orthogonal spreads, and extremal Euclidean line-sets. Proc. Lond. Math. Soc. (3) 75(2), 436–480 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  9. Casazza, P., Kovačević, J.: Equal-norm tight frames with erasures. Adv. Comput. Math. 18, 387–430 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  10. Casazza, P.G., Kutyniok, G.: Frames of subspaces. In: Wavelets, Frames and Operator Theory. Contemp. Math., vol. 345, pp. 87–113. Am. Math. Soc., Providence (2004)

    Google Scholar 

  11. Casazza, P.G., Fickus, M.: Fourier transforms of finite chirps. EURASIP J. Appl. Signal Process. 2006, 1–7 (2006). Frames and overcomplete representations in signal processing, communications, and information theory

    MathSciNet  Google Scholar 

  12. Casazza, P.G., Kutyniok, G.: Robustness of fusion frames under erasures of subspaces and of local frame vectors. In: Grinberg, E.L., Larson, D., Jorgensen, P.E.T., (eds.) Radon Transforms, Geometry, and Wavelets, New Orleans, LA, 2006. Contemp. Math., vol. 464, pp. 149–160. Am. Math. Soc., Providence (2008)

    Google Scholar 

  13. Casazza, P.G., Kutyniok, G., Li, S.: Fusion frames and distributed processing. Appl. Comput. Harmon. Anal. 25, 114–132 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  14. Cameron, P.J., Seidel, J.J.: Quadratic forms over GF(2). Indag. Math. 35, 1–8 (1973)

    MathSciNet  Google Scholar 

  15. Chaturvedi, S.: Aspects of mutually unbiased bases in odd-prime-power dimension. Phys. Rev. A 65, 0044301 (2002)

    Article  Google Scholar 

  16. Delsarte, P., Goethals, J.M., Seidel, J.J.: Spherical codes and designs. Geom. Dedic. 6(3), 363–388 (1977)

    Article  MATH  MathSciNet  Google Scholar 

  17. Finkelstein, J.: Pure-state informationally complete and “really” complete measurements. Phys. Rev. A 70, 052107 (2004)

    Article  MathSciNet  Google Scholar 

  18. Flammia, S.T., Silberfarb, A., Caves, C.M.: Minimal informationally complete measurements for pure states. Found. Phys. 35(12), 1985–2006 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  19. Godsil, C., Roy, A.: Equiangular lines, mutually unbiased bases and spin models. Eur. J. Comb. 30, 246–262 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  20. Goyal, V.K., Kovačević, J., Kelner, J.A.: Quantized frame expansions with erasures. Appl. Comput. Harmon. Anal. 10, 203–233 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  21. Hayes, M.H., Lim, J.S., Oppenheim, A.V.: Signal reconstruction from phase and magnitude. IEEE Trans. Acoust. Speech Signal Process. 28(6), 672–680 (1980)

    Article  MATH  MathSciNet  Google Scholar 

  22. Hoggar, S.G.: t-designs in projective spaces. Eur. J. Comb. 3, 233–254 (1982)

    MATH  MathSciNet  Google Scholar 

  23. Howard, S.D., Calderbank, A.R., Moran, W.: The finite Heisenberg-Weyl groups in radar and communications. EURASIP J. Appl. Signal Process. 2006, 1–12 (2006). Special issue on “Frames and overcomplete representations in signal processing, communications, and information theory”

    MathSciNet  Google Scholar 

  24. Holmes, R., Paulsen, V.I.: Optimal frames for erasures. Linear Algebra Appl. 377, 31–51 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  25. Kovačević, J., Dragotti, P.L., Goyal, V.K.: Filter bank frame expansions with erasures. IEEE Trans. Inf. Theory 48, 1439–1450 (2002)

    Article  MATH  Google Scholar 

  26. Klappenecker, A., Rötteler, M.: Mutually unbiased bases are complex projective 2-designs. In: Proc. Int. Symp. on Inf. Theory, pp. 1740–1744. IEEE Press, New York (2005)

    Google Scholar 

  27. Levenshtein, V.I.: On designs in compact metric spaces and a universal bound on their size. Discrete Math. 192, 251–271 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  28. Lemmens, P.W.H., Seidel, J.J.: Equiangular lines. J. Algebra 24, 494–512 (1973)

    Article  MATH  MathSciNet  Google Scholar 

  29. Lyubich, Yu.I.: On tight projective designs. E-print: math/0703526 (2007)

  30. Nawab, H., Quatieri, T.F., Lim, J.S.: Signal reconstruction from the short-time Fourier transform magnitude. In: Proceedings of ICASSP’82, vol. 7, pp. 1046–1048 (1982)

  31. Neumaier, A.: Combinatorial configurations in terms of distances. Memorandum 81-09 (Wiskunde), Eindhoven Univ. Technol. (1981)

  32. Renes, J.M., Blume-Kohout, R., Scott, A.J., Caves, C.M.: Symmetric informationally complete quantum measurements. J. Math. Phys. 45(6), 2171–2180 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  33. Scott, A.J.: Tight informationally complete quantum measurements. J. Phys. A Math. Gen. 39(43), 13507–13530 (2006)

    Article  MATH  Google Scholar 

  34. Strohmer, T., Heath, R.: Grassmannian frames with applications to coding and communications. Appl. Comput. Harmon. Anal. 14, 257–275 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  35. van Lint, J.H., Seidel, J.J.: Equilateral point sets in elliptic geometry. Indag. Math. 28, 335–348 (1966)

    Google Scholar 

  36. Vale, R., Waldron, S.: Tight frames and their symmetries. Constr. Approx. 21(1), 83–112 (2005)

    MATH  MathSciNet  Google Scholar 

  37. Wootters, W.K., Fields, B.D.: Optimal state-determination by mutually unbiased measurements. Ann. Phys. 191(2), 363–381 (1989)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Mathematics Department and CSCAMM, University of Maryland, College Park, MD, 20742, USA

    Radu Balan

  2. Department of Mathematics, University of Houston, Houston, TX, 77204-3008, USA

    Bernhard G. Bodmann

  3. Department of Mathematics, University of Missouri, Columbia, MO, 65211-4100, USA

    Peter G. Casazza & Dan Edidin

Authors
  1. Radu Balan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Bernhard G. Bodmann
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Peter G. Casazza
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Dan Edidin
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Bernhard G. Bodmann.

Additional information

Communicated by Thomas Strohmer.

The research of B.G. Bodmann was supported by the National Science Foundation grant DMS 0807399, P.G. Casazza was supported by the National Science Foundation grant DMS 0704216, and D. Edidin was supported by a grant from the Missouri Research Board.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Balan, R., Bodmann, B.G., Casazza, P.G. et al. Painless Reconstruction from Magnitudes of Frame Coefficients. J Fourier Anal Appl 15, 488–501 (2009). https://doi.org/10.1007/s00041-009-9065-1

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00041-009-9065-1

Keywords

Mathematics Subject Classification (2000)

Search

Navigation