The Orthogonal Least Squares (OLS) algorithm is an efficient sparse recovery algorithm that has received much attention in recent years. On one hand, this paper considers that the OLS algorithm recovers the supports of sparse signals in the noisy case. We show that the OLS algorithm exactly recovers the support of $K$-sparse signal $\boldsymbol{x}$ from $\boldsymbol{y}=\boldsymbol{\unicode[STIX]{x1D6F7}}\boldsymbol{x}+\boldsymbol{e}$ in $K$ iterations, provided that the sensing matrix $\boldsymbol{\unicode[STIX]{x1D6F7}}$ satisfies the restricted isometry property (RIP) with restricted isometry constant (RIC) $\unicode[STIX]{x1D6FF}_{K+1}<1/\sqrt{K+1}$, and the minimum magnitude of the nonzero elements of $\boldsymbol{x}$ satisfies some constraint. On the other hand, this paper demonstrates that the OLS algorithm exactly recovers the support of the best $K$-term approximation of an almost sparse signal $\boldsymbol{x}$ in the general perturbations case, which means both $\boldsymbol{y}$ and $\boldsymbol{\unicode[STIX]{x1D6F7}}$ are perturbed. We show that the support of the best $K$-term approximation of $\boldsymbol{x}$ can be recovered under reasonable conditions based on the restricted isometry property (RIP).

The generalized orthogonal matching pursuit $\left( \text{gOMP} \right)$ algorithm has received much attention in recent years as a natural extension of the orthogonal matching pursuit $\left( \text{OMP} \right)$. It is used to recover sparse signals in compressive sensing. In this paper, a new bound is obtained for the exact reconstruction of every $K$-sparse signal via the $\text{gOMP}$ algorithm in the noiseless case. That is, if the restricted isometry constant $\left( \text{RIC} \right)$${{\delta }_{NK+1}}$ of the sensing matrix $A$ satisfies

${{\delta }_{NK+1}}\,<\frac{1}{\sqrt{\frac{K}{N}+\,1}},$

then the $\text{gOMP}$ can perfectly recover every $K$-sparse signal $x$ from $y\,=\,Ax$. Furthermore, the bound is proved to be sharp. In the noisy case, the above bound on $\text{RIC}$ combining with an extra condition on the minimum magnitude of the nonzero components of $K$-sparse signals can guarantee that the $\text{gOMP}$ selects all of the support indices of the $K$-sparse signals.