A New Analysis for Support Recovery of OLS and OMP with Partial Support Information

In some applications of compressed sensing, one may be interested in the recovery of a sparse vector whose support is partially known in advance. The recovery of signals using prior support information has been previously studied in the literature. In noiseless case, this paper considers the orthogonal least squares (OLS) and orthogonal matching pursuit (OMP) algorithms for sparse recovery when the partial prior information is available. This prior support consists of two parts. One part is a subset of the true support and another part is outside of the true support. For k-sparse signals \(\textbf{x}\) $\mathbf{x}$ with the prior support which is composed of g true indices and b wrong indices, we show that if \(\textbf{A}\) $\mathbf{A}$ has \(\ell _{2}\) ${\ell }_2$ -norm columns and satisfies the certain RIP condition, then the proposed RIP condition ensures that OLS and OMP can identify the support exactly. Furthermore, our results are superior to the existing results.