Skip to main content

Fast Fourier optimization

Author(s): Vanderbei, Robert J.

To refer to this page use:
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.
Publication Date: Mar-2012
Electronic Publication Date: 18-Jan-2012
Citation: Vanderbei, Robert J. "Fast Fourier optimization" Mathematical Programming Computation, 4(1), 53 - 69, doi:10.1007/s12532-011-0034-8
DOI: doi:10.1007/s12532-011-0034-8
ISSN: 1867-2949
EISSN: 1867-2957
Pages: 53 - 69
Type of Material: Journal Article
Journal/Proceeding Title: Mathematical Programming Computation
Version: This is the author’s final manuscript. All rights reserved to author(s).

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.