2010/04/28 by Alexandre d'Aspremont, Alexandre d’Aspremont, Noureddine El Karoui +2
Biochemistry, Genetics and Molecular Biology · Engineering · Mathematics · #65C60 #90C22 #92C55 #97K20 #FOS: Mathematics #Gene expression and cancer classification #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Statistical Methods and Inference #Statistics Theory (math.ST) #math.OC #math.ST #msc:65C60 #msc:90C22 #msc:92C55 #msc:97K20 #stat.TH
paper · pdf · doi:10.48550/arxiv.1004.5151
Final version
openalex publication_date 2010/04/28 · arxiv created 2012/11/07 · arxiv updated 2015/03/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study a weaker formulation of the nullspace property which guarantees recovery of sparse signals from linear measurements by l1 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.