Signal and Noise Statistics Oblivious Orthogonal Matching Pursuit
This addresses a practical limitation in sparse signal recovery for applications like compressed sensing, though it is an incremental improvement over existing OMP methods.
The paper tackles the problem of operating Orthogonal Matching Pursuit (OMP) without prior knowledge of sparsity or noise statistics, which are typically required for optimal performance, by introducing a residual ratio thresholding (RRT) technique. It establishes support recovery guarantees and shows through simulations that RRT achieves performance comparable to OMP with such prior knowledge.
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.