Optimal Restricted Isometry Condition of Normalized Sampling Matrices for Exact Sparse Recovery With Orthogonal Least Squares

In this paper, we analyze the performance guarantee of the orthogonal least squares (OLS) algorithm expressed in terms of the restricted isometry property (RIP). We show the optimality of the proposed guarantee by showing that there exists an example for which OLS fails to work when the proposed condition is violated. In addition, we show that if the columns of a sampling matrix are
l
₂
-normalized, then the proposed condition is an optimal recovery guarantee for the orthogonal matching pursuit (OMP) algorithm. We also establish a nearly optimal performance guarantee of OLS in the more general case where a sampling matrix might not have unit
l
₂
-norm columns. Moreover, we analyze the performance of OLS in the noisy case. Our result demonstrates that under a suitable constraint on the minimum magnitude of nonzero elements in an input signal, the proposed RIP condition ensures OLS to identify the support exactly. By providing a necessary condition on the minimum magnitude, we show that the proposed minimum magnitude condition is nearly optimal.