Fast Fourier optimization
Fast Fourier optimization
复制标题
快速傅立叶优化
DOI：
10.1007/s12532-011-0034-8
复制
发表时间：
2012
影响因子：
6.3
通讯作者：
R. Vanderbei
中科院分区：
文献类型：
--
作者：
R. Vanderbei
从光学到信号处理，再到雷达和声学，许多有趣且基本实用的优化问题都涉及函数傅里叶变换的约束。众所周知，快速傅立叶变换（FFT）是一种递归算法，它可以显著提高离散傅立叶变换的计算效率。然而，由于它是递归的，很难嵌入到一个线性优化问题。在本文中，我们解释了快速傅立叶变换背后的主要思想，并展示了如何适应它的方式，使其编码为约束的优化问题。我们展示了一个现实世界的问题，从高对比度成像领域。在这个问题上，戏剧性的改进被转化为用更精细的离散点网格解决问题的能力。正如我们将展示的，一般来说，优化约束的“快速傅立叶”版本产生更大但更稀疏的约束矩阵，因此可以将快速傅立叶变换视为优化问题中稀疏化约束的方法，这通常是一件好事。
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.