×

NESTA: A fast and accurate first-order method for sparse recovery. (English) Zbl 1209.90265

Summary: 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 Yu. Nesterov [Math. Program. 103, No. 1 (A), 127–152 (2005; Zbl 1079.90102)], 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 \(\ell_1\) norm of \(W_x\) under constraints, in which \(W\) is not diagonal. The code is available online as a free package in the Matlab language.

MSC:

90C06 Large-scale problems in mathematical programming
90C25 Convex programming
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory

Citations:

Zbl 1079.90102
PDFBibTeX XMLCite
Full Text: DOI arXiv Link