Signal and Noise Statistics Oblivious Orthogonal Matching Pursuit

Sreejith Kallummil, Sheetal Kalyani
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:2429-2438, 2018.

Abstract

Orthogonal matching pursuit (OMP) is a widely used algorithm for recovering sparse high dimensional vectors in linear regression models. The optimal performance of OMP requires a priori knowledge of either the sparsity of regression vector or noise statistics. Both these statistics are rarely known a priori and are very difficult to estimate. In this paper, we present a novel technique called residual ratio thresholding (RRT) to operate OMP without any a priori knowledge of sparsity and noise statistics and establish finite sample and large sample support recovery guarantees for the same. Both analytical results and numerical simulations in real and synthetic data sets indicate that RRT has a performance comparable to OMP with a priori knowledge of sparsity and noise statistics.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-kallummil18a, title = {Signal and Noise Statistics Oblivious Orthogonal Matching Pursuit}, author = {Kallummil, Sreejith and Kalyani, Sheetal}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {2429--2438}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/kallummil18a/kallummil18a.pdf}, url = {https://proceedings.mlr.press/v80/kallummil18a.html}, abstract = {Orthogonal matching pursuit (OMP) is a widely used algorithm for recovering sparse high dimensional vectors in linear regression models. The optimal performance of OMP requires a priori knowledge of either the sparsity of regression vector or noise statistics. Both these statistics are rarely known a priori and are very difficult to estimate. In this paper, we present a novel technique called residual ratio thresholding (RRT) to operate OMP without any a priori knowledge of sparsity and noise statistics and establish finite sample and large sample support recovery guarantees for the same. Both analytical results and numerical simulations in real and synthetic data sets indicate that RRT has a performance comparable to OMP with a priori knowledge of sparsity and noise statistics.} }
Endnote
%0 Conference Paper %T Signal and Noise Statistics Oblivious Orthogonal Matching Pursuit %A Sreejith Kallummil %A Sheetal Kalyani %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-kallummil18a %I PMLR %P 2429--2438 %U https://proceedings.mlr.press/v80/kallummil18a.html %V 80 %X Orthogonal matching pursuit (OMP) is a widely used algorithm for recovering sparse high dimensional vectors in linear regression models. The optimal performance of OMP requires a priori knowledge of either the sparsity of regression vector or noise statistics. Both these statistics are rarely known a priori and are very difficult to estimate. In this paper, we present a novel technique called residual ratio thresholding (RRT) to operate OMP without any a priori knowledge of sparsity and noise statistics and establish finite sample and large sample support recovery guarantees for the same. Both analytical results and numerical simulations in real and synthetic data sets indicate that RRT has a performance comparable to OMP with a priori knowledge of sparsity and noise statistics.
APA
Kallummil, S. & Kalyani, S.. (2018). Signal and Noise Statistics Oblivious Orthogonal Matching Pursuit. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:2429-2438 Available from https://proceedings.mlr.press/v80/kallummil18a.html.

Related Material