Paper Info
Title
Resolution Limits of Sparse Coding in High Dimensions
Abstract
This paper addresses the problem of sparsity pattern detection for unknown k- sparse n-dimensional signals observed through m noisy, random linear measure- ments. Sparsity pattern recovery arises in a number of setti ngs including statistical model selection, pattern detection, and image acquisition . The main results in this paper are necessary and sufficient conditions for asymptoti cally-reliable sparsity pattern recovery in terms of the dimensions m, n and k as well as the signal-to- noise ratio (SNR) and the minimum-to-average ratio (MAR) of the nonzero entries of the signal. We show that m > 2klog(n − k)/(SNRMAR) is necessary for any algorithm to succeed, regardless of complexity; this matches a previous suffi- cient condition for maximum likelihood estimation within a constant factor under certain scalings of k, SNR and MAR with n. We also show a sufficient condition for a computationally-trivial thresholding algorithm tha t is larger than the previ- ous expression by only a factor of 4(1+ SNR) and larger than the requirement for lasso by only a factor of 4/MAR. This provides insight on the precise value and limitations of convex programming-based algorithms. This paper considers the problem of estimating sparse signals in the presence of noise. We are specifically concerned with understanding the theoretical estimation limits and how far practical algorithms are from those limits. In the context of visual co rtex modeling, this analysis may help us understand what visual features are resolvable from visual data. To keep the analysis general, we consider the following abstract estimation problem: An unknown sparse signal x is modeled as an n-dimensional real vector with k nonzero components. The locations of the nonzero components is called the sparsity pattern. We consider the problem of detecting the sparsity pattern of x from an m-dimensional measurement vector y = Ax + d, where A ∈ Rm×n is a known measurement matrix and d ∈ Rm is an additive noise vector with a known distribution. We are interested in � This work was supported in part by a University of California President's Postdoctoral Fellowship, NSF
Year
Venue
DocType
2008
NIPS
Conference
Citations 
PageRank 
References 
2
0.45
14
Authors
3
Name
Order
Citations
PageRank
Alyson K. Fletcher155241.10
Sundeep Rangan23101163.90
Vivek K. Goyal32031171.16