Publications
Detailed Information
Optimal Restricted Isometry Condition for Exact Sparse Recovery with Orthogonal Least Squares
Cited 2 time in
Web of Science
Cited 2 time in Scopus
- Authors
- Issue Date
- 2020-06
- Publisher
- IEEE
- Citation
- 2020 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT), pp.1385-1390
- Abstract
- Orthogonal least squares (OLS) is a classic algorithm for sparse recovery, function approximation, and subset selection. In this paper, we analyze the performance guarantee of the OLS algorithm. Specifically, we show that OLS guarantees the exact reconstruction of any K-sparse vector in K iterations, provided that a sensing matrix has unit l(2)-norm columns and satisfies the restricted isometry property (RIP) of order K + 1 with delta(K+1) < C-K = {1/root K, K = 1, 1/root K+1/4, K = 2, 1/root K+1/16, K = 3, 1/root K, K >= 4, Furthermore, we show that the proposed guarantee is optimal in the sense that if delta(K+1) >= C-K, then there exists a counterexample for which OLS fails the recovery.
- ISSN
- 2157-8095
- Files in This Item:
- There are no files associated with this item.
Item View & Download Count
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.