Decoding by linear programming

被引：5153

作者：

Candes, EJ ^{[1
]}

Tao, T

机构：

[1] CALTECH, Dept Appl & Computat Math, Pasadena, CA 91125 USA

[2] Univ Calif Los Angeles, Dept Math, Los Angeles, CA 90095 USA

来源：

IEEE TRANSACTIONS ON INFORMATION THEORY | 2005年 / 51卷 / 12期

基金：

美国国家科学基金会;

关键词：

basis pursuit; decoding of (random) linear codes; duality in optimization; Gaussian random matrices; l(1) minimization; linear codes; linear programming; principal angles; restricted orthonormality; singular values of random matrices; sparse solutions to underdetermined systems;

D O I：

10.1109/TIT.2005.858979

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

This paper considers a natural error correcting problem with real valued input/output. We wish to recover an input vector f is an element of R-n from corrupted measurements y = Af + e. Here, A is an m by n (coding) matrix and e is an arbitrary and unknown vector of errors. Is it possible to recover f exactly from the data y?

引用

页码：4203 / 4215

页数：13

共 28 条

[1]

[Anonymous], 2001, MATH SURVEYS MONOGRA

[2]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[3]

[Anonymous], 2003, THESIS MIT CAMBRIDGE

[4] LIMIT OF THE SMALLEST EIGENVALUE OF A LARGE DIMENSIONAL SAMPLE COVARIANCE-MATRIX [J].

BAI, ZD ;

YIN, YQ .

ANNALS OF PROBABILITY, 1993, 21 (03) :1275-1294

[5]

BLOOMFIELD P, 1983, LEAST ABSOLUTE DEVAL

[6]

Boyd S., 2004, CONVEX OPTIMIZATION

[7]

CANDES EJ, UNPUB IEEE T INF THE

[8]

CANDES EJ, IN PRESS FOUND COMPU

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

Chen, SSB ;

Donoho, DL ;

Saunders, MA .

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

[10] Noiselets [J].

Coifman, R ;

Geshwind, F ;

Meyer, Y .

APPLIED AND COMPUTATIONAL HARMONIC ANALYSIS, 2001, 10 (01) :27-44

← 1 2 3 →