Sampling Bounds for Sparse Support Recovery in the Presence of Noise

被引：32

作者：

Reeves, Galen ^{[1
]}

Gastpar, Michael ^{[1
]}

机构：

[1] Univ Calif Berkeley, Dept Elect Engn & Comp Sci, Berkeley, CA 94720 USA

来源：

2008 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY PROCEEDINGS, VOLS 1-6 | 2008年

关键词：

D O I：

10.1109/ISIT.2008.4595378

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

It is well known that the support of a sparse signal can be recovered from a small number of random projections. However, in the presence of noise all known sufficient conditions require that the per-sample signal-to-noise ratio (SNR) grows without bound with the dimension of the signal. If the noise is due to quantization of the samples, this means that an unbounded rate per sample is needed. In this paper, it is shown that an unbounded SNR is also a necessary condition for perfect recovery, but any fraction (less than one) of the support can be recovered with bounded SNR. This means that a finite rate per sample is sufficient for partial support recovery. Necessary and sufficient conditions are given for both stochastic and non-stochastic signal models. This problem arises in settings such as compressive sensing, model selection, and signal denoising.

引用

页码：2187 / 2191

页数：5

共 22 条

[1]

AERON S, 2007, ARXIV070434340 CSIT

[2]

AKCAKAYA M, 2007, ARYIV07110366VL CSIT

[3] Near-optimal signal recovery from random projections: Universal encoding strategies? [J].

Candes, Emmanuel J. ;

Tao, Terence .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2006, 52 (12) :5406-5425

[4] Stable signal recovery from incomplete and inaccurate measurements [J].

Candes, Emmanuel J. ;

Romberg, Justin K. ;

Tao, Terence .

COMMUNICATIONS ON PURE AND APPLIED MATHEMATICS, 2006, 59 (08) :1207-1223

[5] Atomic decomposition by basis pursuit [J].

Chen, SSB ;

Donoho, DL ;

Saunders, MA .

SIAM JOURNAL ON SCIENTIFIC COMPUTING, 1998, 20 (01) :33-61

[6] Compressed sensing [J].

Donoho, DL .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2006, 52 (04) :1289-1306

[7] Stable recovery of sparse overcomplete representations in the presence of noise [J].

Donoho, DL ;

Elad, M ;

Temlyakov, VN .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2006, 52 (01) :6-18

[8]

Feng P., 1996, P IEEE INT C AC SPEE, V3, P1689

[9]

FLETCHER AK, 2008, NECESSARY SUFFICIENT

[10] Rate-distortion bounds for sparse approximation [J].

Fletcher, Alyson K. ;

Rangan, Sundeep ;

Goyal, Vivek K. .

2007 IEEE/SP 14TH WORKSHOP ON STATISTICAL SIGNAL PROCESSING, VOLS 1 AND 2, 2007, :254-+

← 1 2 3 →