title: Statistical mechanics of compressed sensing.
abstract: Compressed sensing (CS) is an important recent advance that shows how to reconstruct sparse high dimensional signals from surprisingly small numbers of random measurements. The nonlinear nature of the reconstruction process poses a challenge to understanding the performance of CS. We employ techniques from the statistical physics of disordered systems to compute the typical behavior of CS as a function of the signal sparsity and measurement density. We find surprising and useful regularities in the nature of errors made by CS, a new phase transition which reveals the possibility of CS for nonnegative signals without optimization, and a new null model for sparse regression.
authors.affiliation: Sloan Swartz Center for Theoretical Neurobiology, UCSF, San Francsico, California 94143, USA. surya@phy.ucsf.edu
authors.forename: Surya
authors.initials: S
authors.lastname: Ganguli
authors.forename: Haim
authors.initials: H
authors.lastname: Sompolinsky
mesh_terms: D003198:Computer Simulation; D044962:Data Compression / Q000379:methods*; D003627:Data Interpretation, Statistical; D008954:Models, Biological; D015233:Models, Statistical