Sparsest solutions of underdetermined linear systems via lq-minimization for 0 < q ≤ 1

被引：511

作者：

Foucart, Simon ^{[1
]}

Lai, Ming-Jun ^{[2
]}

机构：

[1] Vanderbilt Univ, Dept Math, Nashville, TN 37240 USA

[2] Univ Georgia, Dept Math, Athens, GA 30602 USA

来源：

APPLIED AND COMPUTATIONAL HARMONIC ANALYSIS | 2009年 / 26卷 / 03期

基金：

美国国家科学基金会;

关键词：

SIGNAL RECOVERY; REPRESENTATIONS; APPROXIMATION; DICTIONARIES; MINIMIZATION;

D O I：

10.1016/j.acha.2008.09.001

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We present a condition on the matrix of an underdetermined linear system which guarantees that the solution of the system with minimal l(q)-quasinorm is also the sparsest one. This generalizes, and slightly improves, a similar result for the l(1)-norm. We then introduce a simple numerical scheme to compute solutions with minimal l(q)-quasinorm, and we Study its convergence. Finally, we display the results of some experiments which indicate that the e.-method performs better than other available methods. (C) 2008 Elsevier Inc. All rights reserved.

引用

页码：395 / 407

页数：13

共 15 条

[1]

BARANIUK R, CONSTR APPR IN PRESS

[2]

CANDES E, J FOURIER A IN PRESS

[3] The restricted isometry property and its implications for compressed sensing [J].

Candes, Emmanuel J. .

COMPTES RENDUS MATHEMATIQUE, 2008, 346 (9-10) :589-592

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

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

[6] Exact reconstruction of sparse signals via nonconvex minimization [J].

Chartrand, Rick .

IEEE SIGNAL PROCESSING LETTERS, 2007, 14 (10) :707-710

[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] Optimally sparse representation in general (nonorthogonal) dictionaries via l1 minimization [J].

Donoho, DL ;

Elad, M .

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2003, 100 (05) :2197-2202

[9] Highly sparse representations from dictionaries are unique and independent of the sparseness measure [J].

Gribonval, R. ;

Nielsen, A. .

APPLIED AND COMPUTATIONAL HARMONIC ANALYSIS, 2007, 22 (03) :335-355

[10] SPARSE APPROXIMATE SOLUTIONS TO LINEAR-SYSTEMS [J].

NATARAJAN, BK .

SIAM JOURNAL ON COMPUTING, 1995, 24 (02) :227-234

← 1 2 →

Sparsest solutions of underdetermined linear systems via lq-minimization for 0 &lt; q ≤ 1

Sparsest solutions of underdetermined linear systems via lq-minimization for 0 < q ≤ 1