Fast Fourier optimization

  • 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 realworld 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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Robert J. Vanderbei
DOI:https://doi.org/10.1007/s12532-011-0034-8
ISSN:1867-2949
Parent Title (English):Mathematical Programming Computation
Subtitle (English):Sparsity matters
Publisher:Springer Science and Business Media LLC
Document Type:Article
Language:English
Year of Completion:2012
Tag:Software; Theoretical Computer Science
Volume:4
Issue:1
Page Number:17
First Page:53
Last Page:69
Mathematical Programming Computation :MPC 2012 - Issue 1
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.