Weak Recovery Conditions from Graph Partitioning Bounds and Order Statistics

• 成果类型: Article
• 署名作者: d'Aspremont, Alexandre; El Karoui, Noureddine
• 署名单位: Institut Polytechnique de Paris; Ecole Polytechnique; University of California System; University of California Berkeley
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1120.0581
• 发表日期: 2013
• 页码: 228-247
• 关键词: approximation algorithms; random projections; signal recovery; model selection; semidefinite; relaxation; PROPERTY

摘要

We study a weaker formulation of the nullspace property which guarantees recovery of sparse signals from linear measurements by l(1) minimization We require this condition to hold only with high probability, given a distribution on the nullspace of the coding matrix A. Under some assumptions on the distribution of the reconstruction error, we show that testing these weak conditions means bounding the optimal value of two classical graph partitioning problems: the k-Dense-Subgraph and MaxCut problems. Both problems admit efficient, relatively tight relaxations, and we use a randomization argument to produce new approximation bounds for k-Dense-Subgraph. We test the performance of our results on several families of coding matrices.