Towards a better compressed sensing

Abstract

In this paper we look at a well known linear inverse problem that is one of the mathematical cornerstones of the compressed sensing field. In seminal works \cite{CRT,DOnoho06CS} ${\ell }_1$ optimization and its success when used for recovering sparse solutions of linear inverse problems was considered. Moreover, \cite{CRT,DOnoho06CS} established for the first time in a statistical context that an unknown vector of linear sparsity can be recovered as a known existing solution of an under-determined linear system through ${\ell }_1$ optimization. In \cite{DonohoPol,DonohoUnsigned} (and later in \cite{StojnicCSetam09,StojnicUpper10}) the precise values of the linear proportionality were established as well. While the typical ${\ell }_1$ optimization behavior has been essentially settled through the work of \cite{DonohoPol,DonohoUnsigned,StojnicCSetam09,StojnicUpper10}, we in this paper look at possible upgrades of ${\ell }_1$ optimization. Namely, we look at a couple of algorithms that turn out to be capable of recovering a substantially higher sparsity than the ${\ell }_1$. However, these algorithms assume a bit of "feedback" to be able to work at full strength. This in turn then translates the original problem of improving upon ${\ell }_1$ to designing algorithms that would be able to provide output needed to feed the ${\ell }_1$ upgrades considered in this papers.

acknowledgement footnote added

References in corpus (8)

• Algorithmic linear dimension reduction in the l_1 norm for sparse vectors
• Various thresholds for ${\ell }_1$-optimization in compressed sensing
• Block-length dependent thresholds in block-sparse compressed sensing
• Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling
• Meshes that trap random subspaces
• A rigorous geometry-probability equivalence in characterization of ${\ell }_1$-optimization
• Bounds on restricted isometry constants of random matrices
• Optimality of ${\ell }_2/{\ell }_1$-optimization block-length dependent thresholds

Cited by in corpus (1)

• Universally Elevating the Phase Transition Performance of Compressed Sensing: Non-Isometric Matrices are Not Necessarily Bad Matrices