Skip to main content

The minimax noise sensitivity in compressed sensing

Publication ,  Journal Article
Reeves, G; Donoho, D
Published in: IEEE International Symposium on Information Theory - Proceedings
January 1, 2013

Consider the compressed sensing problem of estimating an unknown k-sparse n-vector from a set of m noisy linear equations. Recent work focused on the noise sensitivity of particular algorithms - the scaling of the reconstruction error with added noise. In this paper, we study the minimax noise sensitivity - the minimum is over all possible recovery algorithms and the maximum is over all vectors obeying a sparsity constraint. This fundamental quantity characterizes the difficulty of recovery when nothing is known about the vector other than the fact that it has at most k nonzero entries. Assuming random sensing matrices (i.i.d. Gaussian), we obtain non-asymptotic bounds which show that the minimax noise sensitivity is finite if m ≥ k + 3 and infinite if m ≤ k + 1. We also study the large system behavior where δ = m/n (0,1) denotes the undersampling fraction and k/n = ε (0,1) denotes the sparsity fraction. There is a phase transition separating successful and unsuccessful recovery: the minimax noise sensitivity is bounded for any δ > ε and is unbounded for any δ < ε. One consequence of our results is that the Bayes optimal phase transitions of Wu and Verdu can be obtained uniformly over the class of all sparse vectors. © 2013 IEEE.

Duke Scholars

Published In

IEEE International Symposium on Information Theory - Proceedings

DOI

ISSN

2157-8095

Publication Date

January 1, 2013

Start / End Page

116 / 120
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Reeves, G., & Donoho, D. (2013). The minimax noise sensitivity in compressed sensing. IEEE International Symposium on Information Theory - Proceedings, 116–120. https://doi.org/10.1109/ISIT.2013.6620199
Reeves, G., and D. Donoho. “The minimax noise sensitivity in compressed sensing.” IEEE International Symposium on Information Theory - Proceedings, January 1, 2013, 116–20. https://doi.org/10.1109/ISIT.2013.6620199.
Reeves G, Donoho D. The minimax noise sensitivity in compressed sensing. IEEE International Symposium on Information Theory - Proceedings. 2013 Jan 1;116–20.
Reeves, G., and D. Donoho. “The minimax noise sensitivity in compressed sensing.” IEEE International Symposium on Information Theory - Proceedings, Jan. 2013, pp. 116–20. Scopus, doi:10.1109/ISIT.2013.6620199.
Reeves G, Donoho D. The minimax noise sensitivity in compressed sensing. IEEE International Symposium on Information Theory - Proceedings. 2013 Jan 1;116–120.

Published In

IEEE International Symposium on Information Theory - Proceedings

DOI

ISSN

2157-8095

Publication Date

January 1, 2013

Start / End Page

116 / 120