Information-Theoretic Characterization of Sparse Recovery

Cem Aksoylar, Venkatesh Saligrama
Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, PMLR 33:38-46, 2014.

Abstract

We formulate sparse support recovery as a salient set identification problem and use information-theoretic analyses to characterize the recovery performance and sample complexity. We consider a very general framework where we are not restricted to linear models or specific distributions. We state non-asymptotic bounds on recovery probability and a tight mutual information formula for sample complexity. We evaluate our bounds for applications such as sparse linear regression and explicitly characterize effects of correlation or noisy features on recovery performance. We show improvements upon previous work and identify gaps between the performance of recovery algorithms and fundamental information. This illustrates a trade-off between computational complexity and sample complexity, contrasting the recovery of the support as a discrete object with signal estimation approaches.

Cite this Paper

BibTeX
@InProceedings{pmlr-v33-aksoylar14, title = {{Information-Theoretic Characterization of Sparse Recovery}}, author = {Aksoylar, Cem and Saligrama, Venkatesh}, booktitle = {Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics}, pages = {38--46}, year = {2014}, editor = {Kaski, Samuel and Corander, Jukka}, volume = {33}, series = {Proceedings of Machine Learning Research}, address = {Reykjavik, Iceland}, month = {22--25 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v33/aksoylar14.pdf}, url = {https://proceedings.mlr.press/v33/aksoylar14.html}, abstract = {We formulate sparse support recovery as a salient set identification problem and use information-theoretic analyses to characterize the recovery performance and sample complexity. We consider a very general framework where we are not restricted to linear models or specific distributions. We state non-asymptotic bounds on recovery probability and a tight mutual information formula for sample complexity. We evaluate our bounds for applications such as sparse linear regression and explicitly characterize effects of correlation or noisy features on recovery performance. We show improvements upon previous work and identify gaps between the performance of recovery algorithms and fundamental information. This illustrates a trade-off between computational complexity and sample complexity, contrasting the recovery of the support as a discrete object with signal estimation approaches.} }
Endnote
%0 Conference Paper %T Information-Theoretic Characterization of Sparse Recovery %A Cem Aksoylar %A Venkatesh Saligrama %B Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2014 %E Samuel Kaski %E Jukka Corander %F pmlr-v33-aksoylar14 %I PMLR %P 38--46 %U https://proceedings.mlr.press/v33/aksoylar14.html %V 33 %X We formulate sparse support recovery as a salient set identification problem and use information-theoretic analyses to characterize the recovery performance and sample complexity. We consider a very general framework where we are not restricted to linear models or specific distributions. We state non-asymptotic bounds on recovery probability and a tight mutual information formula for sample complexity. We evaluate our bounds for applications such as sparse linear regression and explicitly characterize effects of correlation or noisy features on recovery performance. We show improvements upon previous work and identify gaps between the performance of recovery algorithms and fundamental information. This illustrates a trade-off between computational complexity and sample complexity, contrasting the recovery of the support as a discrete object with signal estimation approaches.
RIS
TY - CPAPER TI - Information-Theoretic Characterization of Sparse Recovery AU - Cem Aksoylar AU - Venkatesh Saligrama BT - Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics DA - 2014/04/02 ED - Samuel Kaski ED - Jukka Corander ID - pmlr-v33-aksoylar14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 33 SP - 38 EP - 46 L1 - http://proceedings.mlr.press/v33/aksoylar14.pdf UR - https://proceedings.mlr.press/v33/aksoylar14.html AB - We formulate sparse support recovery as a salient set identification problem and use information-theoretic analyses to characterize the recovery performance and sample complexity. We consider a very general framework where we are not restricted to linear models or specific distributions. We state non-asymptotic bounds on recovery probability and a tight mutual information formula for sample complexity. We evaluate our bounds for applications such as sparse linear regression and explicitly characterize effects of correlation or noisy features on recovery performance. We show improvements upon previous work and identify gaps between the performance of recovery algorithms and fundamental information. This illustrates a trade-off between computational complexity and sample complexity, contrasting the recovery of the support as a discrete object with signal estimation approaches. ER -
APA
Aksoylar, C. & Saligrama, V.. (2014). Information-Theoretic Characterization of Sparse Recovery. Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 33:38-46 Available from https://proceedings.mlr.press/v33/aksoylar14.html.

Related Material