Nearly Optimal Bounds for Orthogonal Least Squares

Jinming Wen, Jian Wang, Qinyu Zhang

IEEE Transactions on Signal Processing · 2017 · 92 citations · 25 references

DOIFull text

Open access

Concepts

Abstract

In this paper, we study the orthogonal least squares (OLS) algorithm for sparse recovery. On one hand, we show that if the sampling matrix A satisfies the restricted isometry property of order K + 1 with isometry constant δ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">κ+ 1</sub> <; 1/√κ + 1 then OLS exactly recovers the support of any K-sparse vector x from its samples y = Ax in K iterations. On the other hand, we show that OLS may not be able to recover the support of a K-sparse vector x in K iterations for some K if δ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">κ+ 1</sub> ≥ 1/√κ+1/4.

References

25