Fast Fourier optimization: Sparsity matters

Robert J. Vanderbei

Research output: Contribution to journalArticlepeer-review

18 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)53-69
Number of pages17
JournalMathematical Programming Computation
Volume4
Issue number1
DOIs
StatePublished - Mar 2012
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Software

Keywords

  • Cooley-Tukey algorithm
  • Fast Fourier transform (fft)
  • Fourier transform
  • High-contrast imaging
  • Interior-point methods
  • Linear programming
  • Optimization

Fingerprint

Dive into the research topics of 'Fast Fourier optimization: Sparsity matters'. Together they form a unique fingerprint.

Cite this