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 vec tor or noise statistics. Both these statistics are rarely known a priori and are very difficult to es mate. In this paper, we present a novel technique called residual ratio thresholding (RRT) to operat OMP without any a priori knowledge of sparsity and noise statistics and establish finite sample a large sample support recovery guarantees for the same. Both analytical results and numerical simulations in real and synthetic data sets indicate t RRT has a performance comparable to OMP with a priori knowledge of sparsity and noise statistic