Simple bounds for recovering low-complexity models

• 成果类型: Article
• 署名作者: Candes, Emmanuel; Recht, Benjamin
• 署名单位: Stanford University; Stanford University; University of Wisconsin System; University of Wisconsin Madison
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-012-0540-0
• 发表日期: 2013
• 页码: 577-589
• 关键词: INEQUALITIES

摘要

This note presents a unified analysis of the recovery of simple objects from random linear measurements. When the linear functionals are Gaussian, we show that an s-sparse vector in can be efficiently recovered from 2s log n measurements with high probability and a rank r, n x n matrix can be efficiently recovered from r(6n - 5r) measurements with high probability. For sparse vectors, this is within an additive factor of the best known nonasymptotic bounds. For low-rank matrices, this matches the best known bounds. We present a parallel analysis for block-sparse vectors obtaining similarly tight bounds. In the case of sparse and block-sparse signals, we additionally demonstrate that our bounds are only slightly weakened when the measurement map is a random sign matrix. Our results are based on analyzing a particular dual point which certifies optimality conditions of the respective convex programming problem. Our calculations rely only on standard large deviation inequalities and our analysis is self-contained.