Signal and Noise Statistics Oblivious Orthogonal Matching Pursuit
arXiv:1806.00650
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 \textit{a priori} knowledge of either the sparsity of regression vector or noise statistics. Both these statistics are rarely known \textit{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 \textit{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 \textit{a priori} knowledge of sparsity and noise statistics.
arXiv commentAccepted in ICML 2018. Significantly improved and extended version of arXiv preprint arXiv:1707.08712
References in corpus (1)
Cited by in corpus (6)
- Structured and Unstructured Outlier Identification for Robust PCA: A Non iterative, Parameter free Algorithm
- Subspace clustering without knowing the number of clusters: A parameter free approach
- Robust Information Criterion for Model Selection in Sparse High-Dimensional Linear Regression Models
- Noise Statistics Oblivious GARD For Robust Regression With Sparse Outliers
- Residual Ratio Thresholding for Model Order Selection
- Tune smarter not harder: A principled approach to tuning learning rates for shallow nets