CaltechAUTHORS
  A Caltech Library Service

Breaking through the Thresholds: an Analysis for Iterative Reweighted ℓ_1 Minimization via the Grassmann Angle Framework

Xu, Weiyu and Khajehnejad, M. Amin and Avestimehr, A. Salman and Hassibi, Babak (2010) Breaking through the Thresholds: an Analysis for Iterative Reweighted ℓ_1 Minimization via the Grassmann Angle Framework. In: 2010 IEEE International Conference on Acoustics, Speech and Signal Processing. IEEE , Piscataway, NJ, pp. 5498-5501. ISBN 978-1-4244-4295-9. https://resolver.caltech.edu/CaltechAUTHORS:20150130-073717820

[img] PDF - Published Version
See Usage Policy.

126Kb
[img] PDF - Submitted Version
See Usage Policy.

107Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20150130-073717820

Abstract

It is now well understood that the ℓ_1 minimization algorithm is able to recover sparse signals from incomplete measurements [2], [1], [3] and sharp recoverable sparsity thresholds have also been obtained for the ℓ_1 minimization algorithm. However, even though iterative reweighted ℓ_1 minimization algorithms or related algorithms have been empirically observed to boost the recoverable sparsity thresholds for certain types of signals, no rigorous theoretical results have been established to prove this fact. In this paper, we try to provide a theoretical foundation for analyzing the iterative reweighted ℓ1 algorithms. In particular, we show that for a nontrivial class of signals, the iterative reweighted ℓ_1 minimization can indeed deliver recoverable sparsity thresholds larger than that given in [1], [3]. Our results are based on a high-dimensional geometrical analysis (Grassmann angle analysis) of the null-space characterization for ℓ_1 minimization and weighted ℓ1 minimization algorithms.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1109/ICASSP.2010.5495210DOIArticle
http://ieeexplore.ieee.org/document/5495210/PublisherArticle
http://arxiv.org/abs/0904.0994arXivDiscussion Paper
Additional Information:© 2010 IEEE.
Subject Keywords:compressed sensing, basis pursuit, Grassmann angle, reweighted ℓ_1 minimization, random linear subspaces
Record Number:CaltechAUTHORS:20150130-073717820
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20150130-073717820
Official Citation:W. Xu, M. A. Khajehnejad, A. S. Avestimehr and B. Hassibi, "Breaking through the thresholds: an analysis for iterative reweighted ℓ1 minimization via the Grassmann angle framework," 2010 IEEE International Conference on Acoustics, Speech and Signal Processing, Dallas, TX, 2010, pp. 5498-5501. doi: 10.1109/ICASSP.2010.5495210
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:54235
Collection:CaltechAUTHORS
Deposited By: Shirley Slattery
Deposited On:30 Jan 2015 22:51
Last Modified:03 Oct 2019 07:56

Repository Staff Only: item control page