A Near-Optimal Condition for Exact Sparse Recovery with Orthogonal Least Squares

Abstract

Orthogonal least squares (OLS) is a classic algorithm for sparse recovery and subset selection. In this paper, we analyze the performance guarantee of the OLS algorithm using the restricted isometry property (RIP) framework. Specifically, we show that OLS exactly recovers any K-sparse signal in K iterations, provided that a sampling matrix satisfies the RIP with delta(K+1) < 1/root(1 + delta(K+1))K +1/4 + 1/2. Our result bridges the gap between the recent result of Wen et at. and the fundamental limit of OLS at which the exact reconstruction cannot be uniformly guaranteed. Furthermore, we show that the OLS algorithm is stable under measurement noise. Specifically, we show that if the signal-to-noise ratio (SNR) scales linearly with the sparsity of an input signal, then the l(2) -norm of the recovery error is bounded by the noise power.