NESTA: A Fast and Accurate First-Order Method for Sparse Recovery
NESTA: A Fast and Accurate First-Order Method for Sparse Recovery
复制标题
DOI：
10.1137/090756855
复制
发表时间：
2011-01-01
影响因子：
2.1
通讯作者：
Candes, Emmanuel J.
中科院分区：
文献类型：
--
作者：
Becker, Stephen;Bobin, Jerome;Candes, Emmanuel J.
从间接的和可能欠采样的数据中准确地恢复信号或图像重建是一个相当感兴趣的话题;例如，最近压缩传感领域的文献已经相当庞大。本文采用了平滑技术和加速一阶算法，都从Nesterov [数学。Ser. A，103（2005），pp. 127-152]，并且证明了该方法理想地适合于解决大规模压缩感测重建问题，因为（1）它在计算上是高效的，（2）它是准确的并且返回具有几个正确数字的解，（3）它是灵活的并且适合于许多种类的重建问题，以及（4）它是鲁棒的，在这个意义上，它在宽范围的问题上的优异性能不依赖于几个参数的微调。对具有大动态范围的真实信号进行的综合数值实验表明，该算法与最近提出的最先进的方法相比毫不逊色。我们也应用该算法来解决其他问题，有较少的替代品，如全变差最小化和凸规划寻求最小化的l（1）范数下的约束，其中W不是对角。该代码可以在网上作为MATLAB语言的免费软件包获得。
Accurate signal recovery or image reconstruction from indirect and possibly undersampled data is a topic of considerable interest; for example, the literature in the recent field of compressed sensing is already quite immense. This paper applies a smoothing technique and an accelerated first-order algorithm, both from Nesterov [Math. Program. Ser. A, 103 (2005), pp. 127-152], and demonstrates that this approach is ideally suited for solving large-scale compressed sensing reconstruction problems as (1) it is computationally efficient, (2) it is accurate and returns solutions with several correct digits, (3) it is flexible and amenable to many kinds of reconstruction problems, and (4) it is robust in the sense that its excellent performance across a wide range of problems does not depend on the fine tuning of several parameters. Comprehensive numerical experiments on realistic signals exhibiting a large dynamic range show that this algorithm compares favorably with recently proposed state-of-the-art methods. We also apply the algorithm to solve other problems for which there are fewer alternatives, such as total-variation minimization and convex programs seeking to minimize the l(1) norm of Wx under constraints, in which W is not diagonal. The code is available online as a free package in the MATLAB language.