IEEE Transactions on Signal Processing · 2017 · 92 citations · 25 references
ComputingComputer ScienceAlgorithmsInformation TheoryOptimizationIterative SolversMatrix ComputationLeast Squares ProblemsLower BoundsSparse Linear AlgebraUpper Bounds
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.
25