2009/04/06 by Weiyu Xu, Xu, Weiyu, M. Amin Khajehnejad +5
Computer Science · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Probability (math.PR) #cs.IT #math.IT #math.PR
paper · pdf · doi:10.48550/arxiv.0904.0994
Submitted to ITW 2009 in Sicily
arxiv created 2009/04/06 · arxiv updated 2009/12/01
It is now well understood that ℓ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.