Skip to yearly menu bar Skip to main content


( events)   Timezone:  
Poster
Wed Jul 11 09:15 AM -- 12:00 PM (PDT) @ Hall B #19
Signal and Noise Statistics Oblivious Orthogonal Matching Pursuit
Sreejith Kallummil · Sheetal Kalyani
[ PDF

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.