Invertibility of random submatrices via tail-decoupling and a matrix Chernoff inequality

Stéphane Chrétien and Sébastien Darses

Statistics & Probability Letters, 2012, vol. 82, issue 7, 1479-1487

Abstract: Let X be a n×p real matrix with coherence μ(X)=maxj≠j′|XjtXj′|. We present a simplified and improved study of the quasi-isometry property for most submatrices of X obtained by uniform column sampling. Our results depend on μ(X), the operator norm ‖X‖ and the dimensions with explicit constants, which improve the previously known values by a large factor. The analysis relies on a tail-decoupling argument, of independent interest, and a recent version of the Non-Commutative Chernoff inequality (NCCI).

Keywords: Decoupling; Matrix Chernoff inequality; Random sub-matrices; Compressed sensing (search for similar items in EconPapers)
Date: 2012
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0167715212001319
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:stapro:v:82:y:2012:i:7:p:1479-1487

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.spl.2012.03.038

Access Statistics for this article

Statistics & Probability Letters is currently edited by Somnath Datta and Hira L. Koul

More articles in Statistics & Probability Letters from Elsevier
Bibliographic data for series maintained by Catherine Liu ().