Mathematics – Probability
Scientific paper
2009-04-06
Mathematics
Probability
Submitted to ITW 2009 in Sicily
Scientific paper
It is now well understood that $\ell_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 $\ell_1$ minimization algorithm. However, even though iterative reweighted $\ell_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 $\ell_1$ algorithms. In particular, we show that for a nontrivial class of signals, the iterative reweighted $\ell_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 $\ell_1$ minimization and weighted $\ell_1$ minimization algorithms.
Avestimehr Salman
Hassibi Babak
Khajehnejad Amin M.
Xu Weiyu
No associations
LandOfFree
Breaking through the Thresholds: an Analysis for Iterative Reweighted $\ell_1$ Minimization via the Grassmann Angle Framework does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Breaking through the Thresholds: an Analysis for Iterative Reweighted $\ell_1$ Minimization via the Grassmann Angle Framework, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Breaking through the Thresholds: an Analysis for Iterative Reweighted $\ell_1$ Minimization via the Grassmann Angle Framework will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-133658