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

详细信息    查看全文

• 作者：Sté ; phane Chré ; tien^a ; ^{stephane.chretien@univ-fcomte.fr} ; Sé ; bastien Darses^b ; ^{darses@cmi.univ-mrs.fr}
• 关键词：Decoupling ; Matrix Chernoff inequality ; Random sub-matrices ; Compressed sensing
• 刊名：Statistics and Probability Letters
• 出版年：2012
• 出版时间：July, 2012
• 年：2012
• 卷：82
• 期：7
• 页码：1479-1487
• 全文大小：232 K

文摘

Let be a real matrix with coherence . We present a simplified and improved study of the quasi-isometry property for most submatrices of obtained by uniform column sampling. Our results depend on , the operator norm 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).