DocumentCode :
639867
Title :
The minimax noise sensitivity in compressed sensing
Author :
Reeves, G. ; Donoho, David
Author_Institution :
Dept. of Stat., Stanford Univ., Stanford, CA, USA
fYear :
2013
fDate :
7-12 July 2013
Firstpage :
116
Lastpage :
120
Abstract :
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.
Keywords :
Bayes methods; compressed sensing; matrix algebra; minimax techniques; signal reconstruction; Bayes optimal phase transitions; compressed sensing; minimax noise sensitivity; noisy linear equations; nonasymptotic bounds; random sensing matrices; reconstruction error; recovery algorithms; sparse vectors; sparsity constraint; sparsity fraction; system behavior; undersampling fraction; unknown k-sparse n-vector; Compressed sensing; Information theory; Maximum likelihood estimation; Noise; Sensitivity; Upper bound; Vectors;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Information Theory Proceedings (ISIT), 2013 IEEE International Symposium on
Conference_Location :
Istanbul
ISSN :
2157-8095
Type :
conf
DOI :
10.1109/ISIT.2013.6620199
Filename :
6620199
Link To Document :
بازگشت