Shifting Inequality and Recovery of Sparse Signals

被引：123

作者：

Cai, T. Tony ^{[1
]}

Wang, Lie ^{[2
]}

Xu, Guangwu ^{[3
]}

机构：

[1] Univ Penn, Wharton Sch, Dept Stat, Philadelphia, PA 19104 USA

[2] MIT, Dept Math, Cambridge, MA 02139 USA

[3] Univ Wisconsin, Dept Elect Engn & Comp Sci, Milwaukee, WI 53211 USA

来源：

IEEE TRANSACTIONS ON SIGNAL PROCESSING | 2010年 / 58卷 / 03期

关键词：

l(1) minimization; restricted isometry property; shifting inequality; sparse recovery;

D O I：

10.1109/TSP.2009.2034936

中图分类号：

TM [电工技术]; TN [电子技术、通信技术];

学科分类号：

0808 ; 0809 ;

摘要：

In this paper, we present a concise and coherent analysis of the constrained l(1) minimization method for stable recovering of high-dimensional sparse signals both in the noiseless case and noisy case. The analysis is surprisingly simple and elementary, while leads to strong results. In particular, it is shown that the sparse recovery problem can be solved via l(1) minimization under weaker conditions than what is known in the literature. A key technical tool is an elementary inequality, called Shifting Inequality, which, for a given nonnegative decreasing sequence, bounds the l(2) norm of a subsequence in terms of the l(1) norm of another subsequence by shifting the elements to the upper end.

引用

页码：1300 / 1308

页数：9

共 16 条

[1] A frame construction and a universal distortion bound for sparse representations [J].

Akcakaya, Mehmet ;

Tarokh, Vahid .

IEEE TRANSACTIONS ON SIGNAL PROCESSING, 2008, 56 (06) :2443-2450

[2] Toeplitz-structured compressed sensing matrices [J].

Bajwa, Waheed U. ;

Haypt, Jarvis D. ;

Raz, Gil M. ;

Wright, Stephen J. ;

Nowak, Robert D. .

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

[3] A Simple Proof of the Restricted Isometry Property for Random Matrices [J].

Baraniuk, Richard ;

Davenport, Mark ;

DeVore, Ronald ;

Wakin, Michael .

CONSTRUCTIVE APPROXIMATION, 2008, 28 (03) :253-263

[4]

CAI T, 2009, STABLE RECOVERY SPAR

[5] On Recovery of Sparse Signals Via l1 Minimization [J].

Cai, T. Tony ;

Xu, Guangwu ;

Zhang, Jun .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2009, 55 (07) :3388-3397

[6]

Candes E. J., COMPTE RENDUS ACAD 1, V346, P589

[7] Decoding by linear programming [J].

Candes, EJ ;

Tao, T .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2005, 51 (12) :4203-4215

[8]

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

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

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

← 1 2 →