A fast reconstruction algorithm for deterministic compressive sensing using second order Reed-Muller codes

被引：87

作者：

Howard, S. D. ^{[1
]}

Calderbank, A. R. ^{[2
]}

Searle, S. J. ^{[3
]}

机构：

[1] Def Sci & Technol Org, POB 1500, Edinburgh, SA 5111, Australia

[2] Princeton Univ, Elect Engn, Princeton, NJ 08544 USA

[3] Univ Melbourne, Elect & Elect Engn, Melbourne, Vic 3010, Australia

来源：

2008 42ND ANNUAL CONFERENCE ON INFORMATION SCIENCES AND SYSTEMS, VOLS 1-3 | 2008年

关键词：

D O I：

10.1109/CISS.2008.4558486

中图分类号：

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

学科分类号：

0812 [计算机科学与技术];

摘要：

This paper proposes a deterministic compressed sensing matrix that comes by design with a very fast reconstruction algorithm, in the sense that its complexity depends only on the number of measurements n and not on the signal dimension N. The matrix construction is based on the second order Reed-Muller codes and associated functions. This matrix does not have RIP uniformly with respect to all kappa-sparse vectors, but it acts as a near isometry on kappa-sparse vectors with very high probability.

引用

页码：11 / +

页数：2

共 20 条

[1]

[Anonymous], 1983, THEORY ERROR CORRECT

[2]

[Anonymous], 2008, SPARSE RECOVERY USIN

[3]

BAJWA W, 2007, IEEE WORKSH STAT SIG

[4]

Baron D., 2005, ALL C COMM CONTR COM

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

Decoding by linear programming [J].

Candes, EJ ;

Tao, T .

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

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

COHEN A, 2007, COMPRESSED SENSING B

[9]

ALTERNATING BILINEAR FORMS OVER GF(Q) [J].

DELSARTE, P ;

GOETHALS, JM .

JOURNAL OF COMBINATORIAL THEORY SERIES A, 1975, 19 (01) :26-50

[10]

Devore R.A., 2007, DETERMINISTIC CONSTR

← 1 2 →