CaltechAUTHORS
  A Caltech Library Service

Enhancing Sparsity by Reweighted ℓ(1) Minimization

Candès, Emmanuel J. and Wakin, Michael B. and Boyd, Stephen P. (2008) Enhancing Sparsity by Reweighted ℓ(1) Minimization. Journal of Fourier Analysis and Applications, 14 (5-6). pp. 877-905. ISSN 1069-5869. https://resolver.caltech.edu/CaltechAUTHORS:CANjfaa08

[img] PDF
Restricted to Caltech community only
See Usage Policy.

968Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:CANjfaa08

Abstract

It is now well understood that (1) it is possible to reconstruct sparse signals exactly from what appear to be highly incomplete sets of linear measurements and (2) that this can be done by constrained ℓ1 minimization. In this paper, we study a novel method for sparse signal recovery that in many situations outperforms ℓ1 minimization in the sense that substantially fewer measurements are needed for exact recovery. The algorithm consists of solving a sequence of weighted ℓ1-minimization problems where the weights used for the next iteration are computed from the value of the current solution. We present a series of experiments demonstrating the remarkable performance and broad applicability of this algorithm in the areas of sparse signal recovery, statistical estimation, error correction and image processing. Interestingly, superior gains are also achieved when our method is applied to recover signals with assumed near-sparsity in overcomplete representations—not by reweighting the ℓ1 norm of the coefficient sequence as is common, but by reweighting the ℓ1 norm of the transformed object. An immediate consequence is the possibility of highly efficient data acquisition protocols by improving on a technique known as Compressive Sensing.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1007/s00041-008-9045-xDOIUNSPECIFIED
Additional Information:© 2008 Springer. Received: 10 October 2007 Published online: 15 October 2008. Communicated by Albert Cohen. E.C. was partially supported by a National Science Foundation grant CCF-515362, by the 2006 Waterman Award (NSF) and by a grant from DARPA. This work was performed while M.W. was an NSF Postdoctoral Fellow (NSF DMS-0603606) in the Department of Applied and Computational Mathematics at Caltech. S.B. was partially supported by NSF award 0529426, NASA award NNX07AEIIA, and AFOSR awards FA9550-06-1-0514 and FA9550-06-1-0312. We would like to thank Nathaniel Braun and Peter Stobbe for fruitful discussions about this project. Parts of this work were presented at the Fourth IEEE International Symposium on Biomedical Imaging (ISBI ’07) held April 12–15, 2007 and at the Von Neumann Symposium on Sparse Representation and High-Dimensional Geometry held July 8–12, 2007. Related work was first developed as lecture notes for the course EE364b: Convex Optimization II, given at Stanford Winter quarter 2006-07 [62].
Funders:
Funding AgencyGrant Number
National Science FoundationCCF-515362
National Science Foundation, Waterman AwardUNSPECIFIED
Defense Advanced Research Projects AgencyUNSPECIFIED
National Science FoundationDMS-0603606
National Science FoundationDMS-0529426
NASANNX07AEIIA
Air Force Office of Scientific ResearchFA9550-06-1-0514
Air Force Office of Scientific ResearchFA9550-06-1-0312
Subject Keywords:ℓ(1)-Minimization; Iterative reweighting; Underdetermined systems of linear equations; Compressive sensing; Dantzig selector; Sparsity; FOCUSS
Issue or Number:5-6
Record Number:CaltechAUTHORS:CANjfaa08
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:CANjfaa08
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:12852
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:08 Jan 2009 21:27
Last Modified:03 Oct 2019 00:32

Repository Staff Only: item control page