Breaking the ℓ<inf>1</inf> recovery thresholds with reweighted ℓ<inf>1</inf> optimization

Weiyu Xu, Moein Khajehnejad, A. Salman Avestimehr, Babak Hassibi

Abstract

It is now well understood that l <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> minimization algorithm is able to recover sparse signals from incomplete measurements and sharp recoverable sparsity thresholds have also been obtained for the l <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> minimization algorithm. In this paper, we investigate a new iterative reweighted l <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> minimization algorithm and showed that the new algorithm can increase the sparsity recovery threshold of l <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> minimization when decoding signals from relevant distributions. Interestingly, we observed that the recovery threshold performance of the new algorithm depends on the behavior, more specifically the derivatives, of the signal amplitude probability distribution at the origin.
BibTeX
@inproceedings{xu2009breaking,
  author = {Weiyu Xu and Moein Khajehnejad and A. Salman Avestimehr and Babak Hassibi},
  title = {{Breaking the \&amp;\#x2113;\&lt;inf\&gt;1\&lt;/inf\&gt; recovery thresholds with reweighted \&amp;\#x2113;\&lt;inf\&gt;1\&lt;/inf\&gt; optimization}},
  booktitle = {Allerton},
  year = {2009},
  doi = {10.1109/allerton.2009.5394882},
}

Loading related content...

Figure