Stojnic, Mihailo and Xu, Weiyu and Hassibi, Babak (2008) Compressed sensing  probabilistic analysis of a nullspace characterization. In: 2008 IEEE International Conference on Acoustics, Speech and Signal Processing. International Conference on Acoustics Speech and Signal Processing (ICASSP). IEEE , pp. 33773380. ISBN 9781424414833. https://resolver.caltech.edu/CaltechAUTHORS:20100707153301650

PDF
 Published Version
See Usage Policy. 194kB 
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20100707153301650
Abstract
It is well known that compressed sensing problems reduce to solving large underdetermined systems of equations. To assure that the problem is well defined, i.e., that the solution is unique the vector of unknowns is of course assumed to be sparse. Nonetheless, even when the solution is unique, finding it in general may be computationally difficult. However, starting with the seminal work of Candes and Tao [2005], it has been shown that linear programming techniques, obtained from an l_1norm relaxation of the original nonconvex problem, can provably find the unknown vector in certain instances. In particular, using a certain restricted isometry property, Candes and Tao [2005] shows that for measurement matrices chosen from a random Gaussian ensemble, l_1 optimization can find the correct solution with overwhelming probability even when the number of nonzero entries of the unknown vector is proportional to the number of measurements (and the total number of unknowns). The subsequent paper [Donoho and Tanner, 2005] uses results on neighborly polytopes from [Vershik and Sporyshev, 1992] to give a "sharp" bound on what this proportionality should be in the Gaussian case. In the current paper, we observe that what matters is not so much the distribution from which the entries of the measurement matrix A are drawn, but rather the statistics of the nullspace of A. Using this observation, we provide an alternative proof of the main result of Candes and Tao [2005] by analyzing matrices whose nullspace is isotropic (of which i.i.d. Gaussian ensembles are a special case).
Item Type:  Book Section  

Related URLs: 
 
Additional Information:  © 2008 IEEE. This work was supported in part by the National Science Foundation under grant no. CCR0133818, by the David and Lucille Packard Foundation, and by Caltech’s Lee Center for Advanced Networking.  
Funders: 
 
Subject Keywords:  compressed sensing; l(1)optimization  
Series Name:  International Conference on Acoustics Speech and Signal Processing (ICASSP)  
DOI:  10.1109/ICASSP.2008.4518375  
Record Number:  CaltechAUTHORS:20100707153301650  
Persistent URL:  https://resolver.caltech.edu/CaltechAUTHORS:20100707153301650  
Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided.  
ID Code:  18936  
Collection:  CaltechAUTHORS  
Deposited By:  Tony Diaz  
Deposited On:  09 Jul 2010 17:30  
Last Modified:  08 Nov 2021 23:48 
Repository Staff Only: item control page