Back to Search
Start Over
Perturbation Analysis of Orthogonal Least Squares
- Source :
- Canadian Mathematical Bulletin. 62:780-797
- Publication Year :
- 2019
- Publisher :
- Canadian Mathematical Society, 2019.
-
Abstract
- 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}, 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).
- Subjects :
- General Mathematics
0202 electrical engineering, electronic engineering, information engineering
Applied mathematics
Orthogonal least squares
020206 networking & telecommunications
020201 artificial intelligence & image processing
02 engineering and technology
Isometry (Riemannian geometry)
Mathematics
Subjects
Details
- ISSN :
- 14964287 and 00084395
- Volume :
- 62
- Database :
- OpenAIRE
- Journal :
- Canadian Mathematical Bulletin
- Accession number :
- edsair.doi...........b73e03ec9d94696ee1aab455d68d05d3