A Near-Optimal Restricted Isometry Condition of Multiple Orthogonal Least Squares

Abstract

In this paper, we analyze the performance guarantee of multiple orthogonal least squares (MOLS) in recovering sparse signals. Specifically, we show that the MOLS algorithm ensures the accurate recovery of any K-sparse signal, provided that a sampling matrix satisfies the restricted isometry property (RIP) with δLK-L+2 <; √L/K+2L-1 where L is the number of indices chosen in each iteration. In particular, if L=1, our result indicates that the conventional OLS algorithm exactly reconstructs any K-sparse vector under δK+1 <; 1/K+1, which is consistent with the best existing result for OLS.

Keywords

• Sparse signal recovery
• orthogonal least squares (OLS)
• multiple OLS (MOLS)
• restricted isometry property (RIP)