Computable quantification of the stability of sparse signal reconstruction

Gongguo Tang; Arye Nehorai

doi:10.1109/ACSSC.2010.5757510

Computable quantification of the stability of sparse signal reconstruction

Gongguo Tang, Arye Nehorai

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

2 Scopus citations

Abstract

The ℓ₁-constrained minimal singular value (ℓ₁-CMSV) of the sensing matrix is shown to determine, in a concise and tight manner, the recovery performance of ℓ₁-based algorithms such as Basis Pursuit, the Dantzig selector, and the LASSO estimator. Several random measurement ensembles are shown to have ℓ₁-CMSVs bounded away from zero with high probability, as long as the number of measurements is relatively large. Three algorithms based on projected gradient method and interior point algorithm are developed to compute ℓ₁-CMSV. A lower bound of the ℓ₁-CMSV is also available by solving a semi-definite programming problem.

Original language	English
Title of host publication	Conference Record of the 44th Asilomar Conference on Signals, Systems and Computers, Asilomar 2010
Pages	248-252
Number of pages	5
DOIs	https://doi.org/10.1109/ACSSC.2010.5757510
State	Published - 2010
Event	44th Asilomar Conference on Signals, Systems and Computers, Asilomar 2010 - Pacific Grove, CA, United States Duration: Nov 7 2010 → Nov 10 2010

Publication series

Name	Conference Record - Asilomar Conference on Signals, Systems and Computers
ISSN (Print)	1058-6393

Conference

Conference	44th Asilomar Conference on Signals, Systems and Computers, Asilomar 2010
Country/Territory	United States
City	Pacific Grove, CA
Period	11/7/10 → 11/10/10

Keywords

Basis Pursuit
Dantzig selector
LASSO estimator
random measurement ensemble
semidefinite relaxation
sparse signal reconstruction
ℓ-constrained minimal singular value

Access to Document

10.1109/ACSSC.2010.5757510

Cite this

@inproceedings{e4bbf67c58d743cc8a2a5ec246d317cd,

title = "Computable quantification of the stability of sparse signal reconstruction",

abstract = "The ℓ1-constrained minimal singular value (ℓ1-CMSV) of the sensing matrix is shown to determine, in a concise and tight manner, the recovery performance of ℓ1-based algorithms such as Basis Pursuit, the Dantzig selector, and the LASSO estimator. Several random measurement ensembles are shown to have ℓ1-CMSVs bounded away from zero with high probability, as long as the number of measurements is relatively large. Three algorithms based on projected gradient method and interior point algorithm are developed to compute ℓ1-CMSV. A lower bound of the ℓ1-CMSV is also available by solving a semi-definite programming problem.",

keywords = "Basis Pursuit, Dantzig selector, LASSO estimator, random measurement ensemble, semidefinite relaxation, sparse signal reconstruction, ℓ-constrained minimal singular value",

author = "Gongguo Tang and Arye Nehorai",

year = "2010",

doi = "10.1109/ACSSC.2010.5757510",

language = "English",

isbn = "9781424497218",

series = "Conference Record - Asilomar Conference on Signals, Systems and Computers",

pages = "248--252",

booktitle = "Conference Record of the 44th Asilomar Conference on Signals, Systems and Computers, Asilomar 2010",

note = "44th Asilomar Conference on Signals, Systems and Computers, Asilomar 2010 ; Conference date: 07-11-2010 Through 10-11-2010",

}

Tang, G & Nehorai, A 2010, Computable quantification of the stability of sparse signal reconstruction. in Conference Record of the 44th Asilomar Conference on Signals, Systems and Computers, Asilomar 2010., 5757510, Conference Record - Asilomar Conference on Signals, Systems and Computers, pp. 248-252, 44th Asilomar Conference on Signals, Systems and Computers, Asilomar 2010, Pacific Grove, CA, United States, 11/7/10. https://doi.org/10.1109/ACSSC.2010.5757510

Computable quantification of the stability of sparse signal reconstruction. / Tang, Gongguo; Nehorai, Arye.
Conference Record of the 44th Asilomar Conference on Signals, Systems and Computers, Asilomar 2010. 2010. p. 248-252 5757510 (Conference Record - Asilomar Conference on Signals, Systems and Computers).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Computable quantification of the stability of sparse signal reconstruction

AU - Tang, Gongguo

AU - Nehorai, Arye

PY - 2010

Y1 - 2010

N2 - The ℓ1-constrained minimal singular value (ℓ1-CMSV) of the sensing matrix is shown to determine, in a concise and tight manner, the recovery performance of ℓ1-based algorithms such as Basis Pursuit, the Dantzig selector, and the LASSO estimator. Several random measurement ensembles are shown to have ℓ1-CMSVs bounded away from zero with high probability, as long as the number of measurements is relatively large. Three algorithms based on projected gradient method and interior point algorithm are developed to compute ℓ1-CMSV. A lower bound of the ℓ1-CMSV is also available by solving a semi-definite programming problem.

AB - The ℓ1-constrained minimal singular value (ℓ1-CMSV) of the sensing matrix is shown to determine, in a concise and tight manner, the recovery performance of ℓ1-based algorithms such as Basis Pursuit, the Dantzig selector, and the LASSO estimator. Several random measurement ensembles are shown to have ℓ1-CMSVs bounded away from zero with high probability, as long as the number of measurements is relatively large. Three algorithms based on projected gradient method and interior point algorithm are developed to compute ℓ1-CMSV. A lower bound of the ℓ1-CMSV is also available by solving a semi-definite programming problem.

KW - Basis Pursuit

KW - Dantzig selector

KW - LASSO estimator

KW - random measurement ensemble

KW - semidefinite relaxation

KW - sparse signal reconstruction

KW - ℓ-constrained minimal singular value

UR - http://www.scopus.com/inward/record.url?scp=79958017113&partnerID=8YFLogxK

U2 - 10.1109/ACSSC.2010.5757510

DO - 10.1109/ACSSC.2010.5757510

M3 - Conference contribution

AN - SCOPUS:79958017113

SN - 9781424497218

T3 - Conference Record - Asilomar Conference on Signals, Systems and Computers

SP - 248

EP - 252

BT - Conference Record of the 44th Asilomar Conference on Signals, Systems and Computers, Asilomar 2010

T2 - 44th Asilomar Conference on Signals, Systems and Computers, Asilomar 2010

Y2 - 7 November 2010 through 10 November 2010

ER -

Computable quantification of the stability of sparse signal reconstruction

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this