Mathematics – Optimization and Control
Scientific paper
2010-04-28
Mathematics
Optimization and Control
Simplified proofs for some lemmas in the appendix. Many typos fixed. Several formatting changes
Scientific paper
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 semidefinite relaxation techniques to produce tractable bounds. We test the performance of our results on several families of coding matrices.
d'Aspremont Alexandre
Karoui Noureddine El
No associations
LandOfFree
Weak Recovery Conditions from Graph Partitioning Bounds and Order Statistics does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Weak Recovery Conditions from Graph Partitioning Bounds and Order Statistics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Weak Recovery Conditions from Graph Partitioning Bounds and Order Statistics will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-284181