Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 1206.68340
Wang, Yilun; Yin, Wotao
Sparse signal reconstruction via iterative support detection. (English)
[J] SIAM J. Imaging Sci. 3, No. 3, 462-491, electronic only (2010). ISSN 1936-4954/e

Summary: We present a novel sparse signal reconstruction method, Iterative Support Detection (ISD), aiming to achieve fast reconstruction and a reduced requirement on the number of measurements compared to the classical $\ell_1$ minimization approach. ISD addresses failed reconstructions of $\ell_1$ minimization due to insufficient measurements. It estimates a support set $I$ from a current reconstruction and obtains a new reconstruction by solving the minimization problem $\min\{\sum_{i\notin I}|x_i|:Ax=b\}$, and it iterates these two steps for a small number of times. ISD differs from the orthogonal matching pursuit method, as well as its variants, because (i) the index set $I$ in ISD is not necessarily nested or increasing, and (ii) the minimization problem above updates all the components of $x$ at the same time. We generalize the null space property to the truncated null space property and present our analysis of ISD based on the latter. We introduce an efficient implementation of ISD, called threshold-ISD, for recovering signals with fast decaying distributions of nonzeros from compressive sensing measurements. Numerical experiments show that threshold-ISD has significant advantages over the classical $\ell_1$ minimization approach, as well as two state-of-the-art algorithms: the iterative reweighted $\ell_1$ minimization algorithm (IRL1) and the iterative reweighted least-squares algorithm (IRLS). {\tt MATLAB} code is available for download from http://www.caam.rice.edu/ optimization/L1/ISD/.

MSC 2000:: *68U10 Image processing
65K10 Optimization techniques (numerical methods)
90C25 Convex programming
90C51 Interior-point methods

Keywords: compressed sensing; $\ell_1$ minimization; iterative support detection; basis pursuit

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]