Prof. Venkatesh Saligrama,
Professor of Electrical and Computer Engineering,
The problem of sparse recovery arises in a number of statistical signal processing and learning applications. Sparsity arises from the fact that the observed signal or outcome of an experiment can be expressed in terms of a small subset among a collection of elementary signals, features and independent variables. We consider a Bayesian setting where the measured signal/outcome, the class of elementary signals/features, and the sparse subset are all stochastically realized. This setting unifies many interesting instances including linear and non-linear observation models and non-Gaussian settings.
We derive fundamental lower and upper bounds for the sample complexity of sparse recovery. These bounds are based on drawing an analogy between sparse recovery and the noisy channel coding theorem due to Shannon. We show that for many interesting class of problems the sample complexity can be bounded using explicit expressions involving mutual information between the observed outcomes and the sparse subset of features. We then compute these bounds for a number of interesting linear and non-linear scenarios and demonstrate tight bounds for sample complexity of sparse recovery.
Venkatesh Saligrama is a Professor in the Electrical and Computer Engineering Department at Boston University. He obtained his Ph.D. degree
from MIT and B.Tech from IIT Madras. His research interests are in Statistical Signal Processing, Statistical Learning, Video Analysis, Information and Decision theory. He has edited a book on Networked Sensing, Information and Control. He is currently serving as an Associate Editor for IEEE Transactions on Information Theory. He has previously served as an Associate Editor for IEEE Transactions on Signal Processing and has been on the Technical Program Committees of several IEEE conferences. He is the recipient of several awards including the Presidential Early Career Award (PECASE), ONR Young Investigator Award, the NSF Career Award and the Outstanding Research Award at the United Technologies Corporation.