Weak Recovery Conditions from Graph Partitioning Bounds and Order Statistics

Weak Recovery Conditions from Graph Partitioning Bounds and Order Statistics

0.00 Avg rating0 Votes
Article ID: iaor20132377
Volume: 38
Issue: 2
Start Page Number: 228
End Page Number: 247
Publication Date: May 2013
Journal: Mathematics of Operations Research
Authors: ,
Keywords: graph partitioning, order statistics
Abstract:

We study a weaker formulation of the nullspace property which guarantees recovery of sparse signals from linear measurements by 𝓁 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.

Reviews

Required fields are marked *. Your email address will not be published.