Fast Fourier optimization | Mathematical Programming Computation Skip to main content
Springer Nature Link
Log in

Fast Fourier optimization

Sparsity matters

  • Full Length Paper
  • Published:
Mathematical Programming Computation Aims and scope Submit manuscript

Abstract

Many interesting and fundamentally practical optimization problems, ranging from optics, to signal processing, to radar and acoustics, involve constraints on the Fourier transform of a function. It is well-known that the fast Fourier transform (fft) is a recursive algorithm that can dramatically improve the efficiency for computing the discrete Fourier transform. However, because it is recursive, it is difficult to embed into a linear optimization problem. In this paper, we explain the main idea behind the fast Fourier transform and show how to adapt it in such a manner as to make it encodable as constraints in an optimization problem. We demonstrate a real-world problem from the field of high-contrast imaging. On this problem, dramatic improvements are translated to an ability to solve problems with a much finer grid of discretized points. As we shall show, in general, the “fast Fourier” version of the optimization constraints produces a larger but sparser constraint matrix and therefore one can think of the fast Fourier transform as a method of sparsifying the constraints in an optimization problem, which is usually a good thing.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Brigham E., Morrow R.: The fast Fourier transform. IEEE Spectrum 4(12), 63–70 (1967)

    Article  Google Scholar 

  2. Carlotti, A., Vanderbei, R.J., Kasdin, N.J.: Optimal pupil apodizations for arbitrary apertures. Optics Express (2012, to appear)

  3. Coleman, J., Scholnik, D.: Design of nonlinear-phase FIR filters with second-order cone programming. In: Proceedings of 1999 Midwest Symposium on Circuits and Systems (1999)

  4. Cooley J., Tukey J.: An algorithm for the machine calculation of complex fourier series. Math. Comput. 19, 297–301 (1965)

    Article  MathSciNet  MATH  Google Scholar 

  5. Duhamel P., Vetterli M.: Fast fourier transforms: a tutorial review and a state of the art. Signal Process. 19, 259–299 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  6. Guyon O., Pluzhnik E., Kuchner M., Collins B., Ridgway S.: Theoretical limits on extrasolar terrestrial planet detection with coronagraphs. Astrophys. J. Suppl. 167(1), 81–99 (2006)

    Article  Google Scholar 

  7. Indebetouw G.: Optimal apodizing properties of gaussian pupils. J. Modern Optics 37(7), 1271–1275 (1990)

    Article  Google Scholar 

  8. Trauger J.T., Traub W.: A laboratory demonstration of the capability to image an earth-like extrasolar planet. Nature 446(7137), 771–774 (2007)

    Article  Google Scholar 

  9. Kasdin, N., Vanderbei, R., Spergel, D., Littman, M.: Extrasolar planet finding via optimal apodized and shaped pupil coronagraphs. Astrophys. J. 582, 1147–1161 (2003). http://www.orfe.princeton.edu/~rvdb/tex/tpf/ApJOptimal.pdf

  10. Kasdin N., Vanderbei R., Littman M., Spergel D.: Optimal one-dimensional apodizations and shaped pupils for planet finding coronagraphy. Appl. Optics 44(7), 1117–1128 (2005)

    Article  Google Scholar 

  11. Lebret H., Boyd S.: Antenna array pattern synthesis via convex optimization. IEEE Transact. Signal Process. 45, 526–532 (1997)

    Article  Google Scholar 

  12. Mailloux R.: Phased Array Antenna Handbook. Artech House, Dedham (2005)

    Google Scholar 

  13. Martinez P., Dorrer C., Carpentier E.A., Kasper M., Boccaletti A., Dohlen K., Yaitskova N.: Design, analysis, and testing of a microdot apodizer for the apodized pupil Lyot coronagraph. Astron. Astrophys. 495(1), 363–370 (2009)

    Article  Google Scholar 

  14. Papadimitriou C.: Optimality of the fast Fourier transform. J. ACM 26, 95–102 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  15. Scholnik D., Coleman J.: Optimal array-pattern synthesis for wideband digital transmit arrays. IEEE J. Signal Process 1(4), 660–677 (2007)

    Google Scholar 

  16. Soummer R.: Apodized pupil lyot coronagraphs for arbitrary telescope apertures. Astrophys. J. Lett. 618, 161–164 (2005)

    Article  Google Scholar 

  17. Soummer R., Pueyo L., Sivaramakrishnan A., Vanderbei R.: Fast computation of lyot-style coronagraph propagation. Optics Express 15(24), 15,935–15,951 (2007)

    Article  Google Scholar 

  18. Spergel D., Kasdin N.: A shaped pupil coronagraph: a simpler path towards TPF. Bull. Am. Astron. Soc. 33, 1431 (2001)

    Google Scholar 

  19. Tanaka S., Enya K., Abe L., Nakagawa T., Kataza H.: Binary-shaped pupil coronagraphs for high-contrast imaging using a space telescope with central obstructions. PASJ 58(3), 627–639 (2006)

    Google Scholar 

  20. Vanderbei R.: Splitting dense columns in sparse linear systems. Lin. Alg. Appl. 152, 107–117 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  21. Vanderbei R.: LOQO: an interior point code for quadratic programming. Optimization Methods Software 12, 451–484 (1999)

    Article  MathSciNet  Google Scholar 

  22. Wu S., Boyd S., Vandenberghe L.: FIR filter design via semidefinite programming and spectral factorization. Proc. IEEE Conf. Decis. Control 35, 271–276 (1996)

    Google Scholar 

  23. Wu, S., Boyd, S., Vandenberghe, L.: FIR filter design via spectral factorization and convex optimization. Datta, B. (ed.) Applied and Computational Control, Signals, and Circuits, vol. 1, pp. 215–246. Birkhauser (1999)

Download references

Author information

Authors and Affiliations

  1. Department of Operations Research and Financial Engineering, Princeton University, Princeton, NJ, 08544, USA

    Robert J. Vanderbei

Authors
  1. Robert J. Vanderbei
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Robert J. Vanderbei.

Additional information

The author was supported by a grant from NASA.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Vanderbei, R.J. Fast Fourier optimization. Math. Prog. Comp. 4, 53–69 (2012). https://doi.org/10.1007/s12532-011-0034-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12532-011-0034-8

Keywords

Mathematics Subject Classification (2000)

Search

Navigation