Timezone: »
Poster
Resolution Limits of Sparse Coding in High Dimensions
Alyson Fletcher · Sundeep Rangan · Vivek K Goyal
Recent research suggests that neural systems employ sparse coding. However, there is limited theoretical understanding of fundamental resolution limits in such sparse coding. This paper considers a general sparse estimation problem of detecting the sparsity pattern of a $k$-sparse vector in $\R^n$ from $m$ random noisy measurements. Our main results provide necessary and sufficient conditions on the problem dimensions, $m$, $n$ and $k$, and the signal-to-noise ratio (SNR) for asymptotically-reliable detection. We show a necessary condition for perfect recovery at any given SNR for all algorithms, regardless of complexity, is $m = \Omega(k\log(n-k))$ measurements. This is considerably stronger than all previous necessary conditions. We also show that the scaling of $\Omega(k\log(n-k))$ measurements is sufficient for a trivial ``maximum correlation'' estimator to succeed. Hence this scaling is optimal and does not require lasso, matching pursuit, or more sophisticated methods, and the optimal scaling can thus be biologically plausible.
Author Information
Alyson Fletcher (UCLA)
Sundeep Rangan (Qualcomm)
Vivek K Goyal (Massachusetts Institute of Technology)
More from the Same Authors
-
2022 Poster: Instability and Local Minima in GAN Training with Kernel Discriminators »
Evan Becker · Parthe Pandit · Sundeep Rangan · Alyson Fletcher -
2019 Poster: Input-Output Equivalence of Unitary and Contractive RNNs »
Melikasadat Emami · Mojtaba Sahraee Ardakan · Sundeep Rangan · Alyson Fletcher -
2017 Poster: Rigorous Dynamics and Consistent Estimation in Arbitrarily Conditioned Linear Systems »
Alyson Fletcher · Mojtaba Sahraee-Ardakan · Sundeep Rangan · Philip Schniter -
2016 : From Brains to Bits and Back Again »
Yoshua Bengio · Terrence Sejnowski · Christos H Papadimitriou · Jakob H Macke · Demis Hassabis · Alyson Fletcher · Andreas Tolias · Jascha Sohl-Dickstein · Konrad P Koerding -
2016 : Welcome and Opening Remarks »
Alyson Fletcher · Konrad P Koerding -
2016 Workshop: Brains and Bits: Neuroscience meets Machine Learning »
Alyson Fletcher · Eva Dyer · Jascha Sohl-Dickstein · Joshua T Vogelstein · Konrad Koerding · Jakob H Macke -
2015 Workshop: Statistical Methods for Understanding Neural Systems »
Alyson Fletcher · Jakob H Macke · Ryan Adams · Jascha Sohl-Dickstein -
2014 Poster: Scalable Inference for Neuronal Connectivity from Calcium Imaging »
Alyson Fletcher · Sundeep Rangan -
2014 Spotlight: Scalable Inference for Neuronal Connectivity from Calcium Imaging »
Alyson Fletcher · Sundeep Rangan -
2013 Workshop: High-dimensional Statistical Inference in the Brain »
Alyson Fletcher · Dmitri B Chklovskii · Fritz Sommer · Ian H Stevenson -
2012 Poster: Approximate Message Passing with Consistent Parameter Estimation and Applications to Sparse Learning »
Ulugbek S Kamilov · Sundeep Rangan · Alyson Fletcher · MIchael Unser -
2011 Poster: Neural Reconstruction with Approximate Message Passing (NeuRAMP) »
Alyson Fletcher · Sundeep Rangan · Lav R Varshney · Aniruddha Bhargava -
2009 Poster: Orthogonal Matching Pursuit From Noisy Random Measurements: A New Analysis »
Alyson Fletcher · Sundeep Rangan -
2009 Spotlight: Orthogonal Matching Pursuit From Noisy Random Measurements: A New Analysis »
Alyson Fletcher · Sundeep Rangan -
2009 Poster: Asymptotic Analysis of MAP Estimation via the Replica Method and Compressed Sensing »
Sundeep Rangan · Alyson Fletcher · Vivek K Goyal -
2009 Spotlight: Asymptotic Analysis of MAP Estimation via the Replica Method and Compressed Sensing »
Sundeep Rangan · Alyson Fletcher · Vivek K Goyal