How well can we estimate a sparse vector?

被引：48

作者：

Candes, Emmanuel J. ^{[1
,2
]}

Davenport, Mark A. ^{[3
]}

机构：

[1] Stanford Univ, Dept Math, Stanford, CA 94035 USA

[2] Stanford Univ, Dept Stat, Stanford, CA 94035 USA

[3] Georgia Inst Technol, Sch Elect & Comp Engn, Atlanta, GA 30332 USA

来源：

APPLIED AND COMPUTATIONAL HARMONIC ANALYSIS | 2013年 / 34卷 / 02期

关键词：

Compressive sensing; Sparse estimation; Sparse linear regression; Minimax lower bounds; Fano's inequality; Matrix Bernstein inequality; DANTZIG SELECTOR; LASSO; RATES;

D O I：

10.1016/j.acha.2012.08.010

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The estimation of a sparse vector in the linear model is a fundamental problem in signal. processing, statistics, and compressive sensing. This paper establishes a lower bound on the mean-squared error, which holds regardless of the sensing/design matrix being used and regardless of the estimation procedure. This lower bound very nearly matches the known upper bound one gets by taking a random projection of the sparse vector followed by an l(1) estimation procedure such as the Dantzig selector. In this sense, compressive sensing techniques cannot essentially be improved. (C) 2012 Elsevier Inc. All rights reserved.

引用

页码：317 / 323

页数：7

共 19 条

[1] Information Theoretic Bounds for Compressed Sensing [J].

Aeron, Shuchin ;

Saligrama, Venkatesh ;

Zhao, Manqi .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2010, 56 (10) :5111-5130

[2] Strong converse for identification via quantum channels [J].

Ahlswede, R ;

Winter, A .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2002, 48 (03) :569-579

[3]

[Anonymous], ARXIV11031943

[4] SIMULTANEOUS ANALYSIS OF LASSO AND DANTZIG SELECTOR [J].

Bickel, Peter J. ;

Ritov, Ya'acov ;

Tsybakov, Alexandre B. .

ANNALS OF STATISTICS, 2009, 37 (04) :1705-1732

[5] Robust uncertainty principles:: Exact signal reconstruction from highly incomplete frequency information [J].

Candès, EJ ;

Romberg, J ;

Tao, T .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2006, 52 (02) :489-509

[6]

Candes E, 2007, ANN STAT, V35, P2313, DOI 10.1214/009053606000001523

[7] 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

[8]

Cover T.M., 2006, ELEMENTS INFORM THEO, V2nd ed

[9] Compressed sensing [J].

Donoho, DL .

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

[10]

HAN TS, 1994, IEEE T INFORM THEORY, V40, P1247, DOI 10.1109/18.335943

← 1 2 →