Nearly Optimal Bounds for Orthogonal Least Squares

Abstract

In this paper, we study the orthogonal least squares (OLS) algorithm for sparse recovery. On the one hand, we show that if the sampling matrix $\mathbf{A}$ satisfies the restricted isometry property (RIP) of order $K+1$ with isometry constant $${\delta }_{K+1}<\frac{1}{\sqrt{K+1}},$$ then OLS exactly recovers the support of any $K$-sparse vector $\mathbf{x}$ from its samples $\mathbf{y}=\mathbf{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 $\mathbf{x}$ in $K$ iterations for some $K$ if $${\delta }_{K+1}\ge \frac{1}{\sqrt{K+\frac{1}{4}}}.$$

To appear in IEEE Transactions on Signal Processing

References in corpus (3)

• A Sharp Condition for Exact Support Recovery of with Orthogonal Matching Pursuit
• On The Exact Recovery Condition of Simultaneous Orthogonal Matching Pursuit
• A Sharp Restricted Isometry Constant Bound of Orthogonal Matching Pursuit

Cited by in corpus (10)

• A New Analysis for Support Recovery with Block Orthogonal Matching Pursuit
• Recovery Conditions of Sparse Signals Using Orthogonal Least Squares-Type Algorithms
• Block-Sparse Tensor Recovery
• Blind Orthogonal Least Squares based Compressive Spectrum Sensing
• Efficient Least Residual Greedy Algorithms for Sparse Recovery
• A Two Stage Generalized Block Orthogonal Matching Pursuit (TSGBOMP) Algorithm
• Preconditioned Multiple Orthogonal Least Squares and Applications in Ghost Imaging via Sparsity Constraint
• Joint Sparse Recovery Using Signal Space Matching Pursuit
• Modified Hard Thresholding Pursuit with Regularization Assisted Support Identification
• On the Fundamental Recovery Limit of Orthogonal Least Squares