TR2015-026
Weighted One-norm Minimization with Inaccurate Support Estimates: Sharp Analysis via the Null-space Property
-
- "Weighted One-Norm Minimization with Inaccurate Support Estimates: Sharp Analysis via the Null-Space Property", IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), DOI: 10.1109/ICASSP.2015.7178585, April 2015, pp. 3317-3321.BibTeX TR2015-026 PDF
- @inproceedings{Mansour2015apr2,
- author = {Mansour, H. and Saab, R.},
- title = {Weighted One-Norm Minimization with Inaccurate Support Estimates: Sharp Analysis via the Null-Space Property},
- booktitle = {IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP)},
- year = 2015,
- pages = {3317--3321},
- month = apr,
- publisher = {IEEE},
- doi = {10.1109/ICASSP.2015.7178585},
- url = {https://www.merl.com/publications/TR2015-026}
- }
,
- "Weighted One-Norm Minimization with Inaccurate Support Estimates: Sharp Analysis via the Null-Space Property", IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), DOI: 10.1109/ICASSP.2015.7178585, April 2015, pp. 3317-3321.
-
MERL Contact:
-
Research Area:
Abstract:
We study the problem of recovering sparse vectors given possibly erroneous support estimates. First, we provide necessary and sufficient conditions for weighted l1 minimization to successfully recovery all sparse signals whose support estimate is sufficiently accurate. We relate these conditions to the analogous ones for l1 minimization, showing that they are equivalent when the support estimate is 50% accurate but that the weighted l1 conditions are easier to satisfy when the support is more than 50% accurate. Second, to quantify this improvement, we provide bounds on the number of Gaussian measurements that ensure, with high probability, that weighted l1 minimization succeeds. The resulting number of measurements can be significantly less than what is needed to ensure recovery via l1 minimization. Finally, we illustrate our results via numerical experiments.
Related News & Events
-
NEWS Multimedia Group researchers presented 8 papers at ICASSP 2015 Date: April 19, 2015 - April 24, 2015
Where: IEEE International Conference on Acoustics, Speech & Signal Processing (ICASSP)
MERL Contacts: Anthony Vetro; Hassan Mansour; Petros T. Boufounos; Jonathan Le RouxBrief- Multimedia Group researchers have presented 8 papers at the recent IEEE International Conference on Acoustics, Speech & Signal Processing, which was held in Brisbane, Australia from April 19-24, 2015.