The stability of low-rank matrix reconstruction: A constrained singular value perspective

Gongguo Tang; Arye Nehorai

doi:10.1109/ALLERTON.2010.5707128

The stability of low-rank matrix reconstruction: A constrained singular value perspective

Gongguo Tang
, Arye Nehorai

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

1 Scopus citations

Abstract

The stability of low-rank matrix reconstruction is investigated in this paper. The ℓ*-constrained minimal singular value (ℓ*-CMSV) of the measurement operator is shown to determine the recovery performance of nuclear norm minimization based algorithms. Compared with the stability results using the matrix restricted isometry constant, the performance bounds established using ℓ*-CMSV are more concise and tight, and their derivations are less complex. 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.

Original language	English
Title of host publication	2010 48th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2010
Pages	1745-1751
Number of pages	7
DOIs	https://doi.org/10.1109/ALLERTON.2010.5707128
State	Published - 2010
Event	48th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2010 - Monticello, IL, United States Duration: Sep 29 2010 → Oct 1 2010

Publication series

Name	2010 48th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2010

Conference

Conference	48th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2010
Country/Territory	United States
City	Monticello, IL
Period	09/29/10 → 10/1/10

Keywords

Matrix Dantzig selector
Matrix LASSO estimator
Matrix basis pursuit
Matrix restricted isometry property
ℓ*-constrained minimal singular value

Access to Document

10.1109/ALLERTON.2010.5707128

Cite this

Tang, G., & Nehorai, A. (2010). The stability of low-rank matrix reconstruction: A constrained singular value perspective. In 2010 48th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2010 (pp. 1745-1751). Article 5707128 (2010 48th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2010). https://doi.org/10.1109/ALLERTON.2010.5707128

@inproceedings{e671492a3cfc4c8390642fff2ab56790,

title = "The stability of low-rank matrix reconstruction: A constrained singular value perspective",

abstract = "The stability of low-rank matrix reconstruction is investigated in this paper. The ℓ*-constrained minimal singular value (ℓ*-CMSV) of the measurement operator is shown to determine the recovery performance of nuclear norm minimization based algorithms. Compared with the stability results using the matrix restricted isometry constant, the performance bounds established using ℓ*-CMSV are more concise and tight, and their derivations are less complex. 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.",

keywords = "Matrix Dantzig selector, Matrix LASSO estimator, Matrix basis pursuit, Matrix restricted isometry property, ℓ*-constrained minimal singular value",

author = "Gongguo Tang and Arye Nehorai",

year = "2010",

doi = "10.1109/ALLERTON.2010.5707128",

language = "English",

isbn = "9781424482146",

series = "2010 48th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2010",

pages = "1745--1751",

booktitle = "2010 48th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2010",

note = "48th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2010 ; Conference date: 29-09-2010 Through 01-10-2010",

}

Tang, G & Nehorai, A 2010, The stability of low-rank matrix reconstruction: A constrained singular value perspective. in 2010 48th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2010., 5707128, 2010 48th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2010, pp. 1745-1751, 48th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2010, Monticello, IL, United States, 09/29/10. https://doi.org/10.1109/ALLERTON.2010.5707128

The stability of low-rank matrix reconstruction: A constrained singular value perspective. / Tang, Gongguo; Nehorai, Arye.
2010 48th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2010. 2010. p. 1745-1751 5707128 (2010 48th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2010).

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

TY - GEN

T1 - The stability of low-rank matrix reconstruction

T2 - 48th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2010

AU - Tang, Gongguo

AU - Nehorai, Arye

PY - 2010

Y1 - 2010

N2 - The stability of low-rank matrix reconstruction is investigated in this paper. The ℓ*-constrained minimal singular value (ℓ*-CMSV) of the measurement operator is shown to determine the recovery performance of nuclear norm minimization based algorithms. Compared with the stability results using the matrix restricted isometry constant, the performance bounds established using ℓ*-CMSV are more concise and tight, and their derivations are less complex. 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.

AB - The stability of low-rank matrix reconstruction is investigated in this paper. The ℓ*-constrained minimal singular value (ℓ*-CMSV) of the measurement operator is shown to determine the recovery performance of nuclear norm minimization based algorithms. Compared with the stability results using the matrix restricted isometry constant, the performance bounds established using ℓ*-CMSV are more concise and tight, and their derivations are less complex. 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.

KW - Matrix Dantzig selector

KW - Matrix LASSO estimator

KW - Matrix basis pursuit

KW - Matrix restricted isometry property

KW - ℓ-constrained minimal singular value

UR - https://www.scopus.com/pages/publications/79952382524

U2 - 10.1109/ALLERTON.2010.5707128

DO - 10.1109/ALLERTON.2010.5707128

M3 - Conference contribution

AN - SCOPUS:79952382524

SN - 9781424482146

T3 - 2010 48th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2010

SP - 1745

EP - 1751

BT - 2010 48th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2010

Y2 - 29 September 2010 through 1 October 2010

ER -

The stability of low-rank matrix reconstruction: A constrained singular value perspective

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this