Abstract
Compressed sensing (CS) exploits the compressibility of natural signals to reduce the number of samples required for accurate reconstruction. The cost for sub-Nyquist sampling has been computationally expensive reconstruction algorithms, including large-scale ℓ1 optimization. Therefore, first-order optimization methods that exploit only the gradient of the reconstruction cost function have been developed; notable examples include iterative soft thresholding (IST), fast iterative soft thresholding algorithm (FISTA), and approximate message passing (AMP). The performance of these algorithms has been studied mainly in the standard framework of convex optimization, called the deterministic framework here. In this paper, we first show that the deterministic approach results in overly pessimistic conclusions that are not indicative of algorithm performance in practice. As an alternative to the deterministic framework, we second study the theoretical aspects of the statistical convergence rate, a topic that has remained unexplored in the sparse recovery literature. Our theoretical and empirical studies reveal several hallmark properties of the statistical convergence of first-order methods, including universality over the matrix ensemble and the least favorable coefficient distribution.
Original language | English (US) |
---|---|
Title of host publication | 2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011 |
Pages | 134-138 |
Number of pages | 5 |
DOIs | |
State | Published - Oct 26 2011 |
Event | 2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011 - St. Petersburg, Russian Federation Duration: Jul 31 2011 → Aug 5 2011 |
Other
Other | 2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011 |
---|---|
Country | Russian Federation |
City | St. Petersburg |
Period | 7/31/11 → 8/5/11 |
ASJC Scopus subject areas
- Theoretical Computer Science
- Information Systems
- Modeling and Simulation
- Applied Mathematics