# zbMATH — the first resource for mathematics

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.
Reviewer: Reviewer (Berlin)

##### MSC:
 90C06 Large-scale problems in mathematical programming 90C25 Convex programming 94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
##### Software:
CoSaMP; FPC_AS; glmnet; Matlab; na28; NESTA; PDCO; RecPF
Full Text: