Fast Fourier Optimization: Sparsity Matters
arXiv:1209.0617 · doi:10.1007/s12532-011-0034-8
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 {\em 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.
arXiv comment16 pages, 8 figures
References in corpus (10)
- SparsePak: A Formatted Fiber Field Unit for The WIYN Telescope Bench Spectrograph. I. Design, Construction, and Calibration
- Theoretical Limits on Extrasolar Terrestrial Planet Detection with Coronagraphs
- Apodized Pupil Lyot Coronagraphs for Arbitrary Telescope Apertures
- Fast computation of Lyot-style coronagraph propagation
- Circularly Symmetric Apodization via Starshaped Masks
- Rectangular-Mask Coronagraphs for High-Contrast Imaging
- Design, analysis and test of a microdots apodizer for the Apodized Pupil Lyot Coronagraph
- Spiderweb Masks for High-Contrast Imaging
- Optimal Asymmetric Apodizations and Shaped Pupils for Planet Finding Coronagraphy
- Optimal pupil apodizations for arbitrary apertures
Cited by in corpus (5)
- Apodized pupil Lyot coronagraphs for arbitrary apertures. V. Hybrid Shaped Pupil designs for imaging Earth-like planets with future space observatories
- Design, pointing control, and on-sky performance of the mid-infrared vortex coronagraph for the VLT/NEAR experiment
- Optimal pupil apodizations for arbitrary apertures
- Apodized Pupil Lyot Coronagraphs with arbitrary aperture telescopes: novel designs using hybrid focal plane masks
- Flight masks of the Roman Space Telescope Coronagraph Instrument