Nearly Optimal Bounds for Orthogonal Least Squares

Jinming Wen; Jian Wang; Qinyu Zhang

doi:10.1109/TSP.2017.2728502

Nearly Optimal Bounds for Orthogonal Least Squares

Jinming Wen
, Jian Wang^*
, Qinyu Zhang

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

90 Scopus citations

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 δK+1 < √ 1 K+1 then OLS exactly recovers the support of any K-sparse vector x from its samplesy = AxinK 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 δK+1 ≥ √ 1 K+ 14.

Original language	English
Article number	7982803
Pages (from-to)	5347-5356
Number of pages	10
Journal	IEEE Transactions on Signal Processing
Volume	65
Issue number	20
DOIs	https://doi.org/10.1109/TSP.2017.2728502
State	Published - 15 Oct 2017
Externally published	Yes

Keywords

Sparse recovery
orthogonal least squares (OLS)
orthogonal matching pursuit (OMP)
restricted isometry property (RIP)

Access to Document

10.1109/TSP.2017.2728502

Cite this

@article{9a44d8a4a9e34c669ff2073663a265aa,

title = "Nearly Optimal Bounds for Orthogonal Least Squares",

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 δK+1 < √ 1 K+1 then OLS exactly recovers the support of any K-sparse vector x from its samplesy = AxinK 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 δK+1 ≥ √ 1 K+ 14.",

keywords = "Sparse recovery, orthogonal least squares (OLS), orthogonal matching pursuit (OMP), restricted isometry property (RIP)",

author = "Jinming Wen and Jian Wang and Qinyu Zhang",

note = "Publisher Copyright: {\textcopyright} 2017 IEEE.",

year = "2017",

month = oct,

day = "15",

doi = "10.1109/TSP.2017.2728502",

language = "英语",

volume = "65",

pages = "5347--5356",

journal = "IEEE Transactions on Signal Processing",

issn = "1053-587X",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "20",

}

TY - JOUR

T1 - Nearly Optimal Bounds for Orthogonal Least Squares

AU - Wen, Jinming

AU - Wang, Jian

AU - Zhang, Qinyu

PY - 2017/10/15

Y1 - 2017/10/15

N2 - 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 δK+1 < √ 1 K+1 then OLS exactly recovers the support of any K-sparse vector x from its samplesy = AxinK 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 δK+1 ≥ √ 1 K+ 14.

AB - 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 δK+1 < √ 1 K+1 then OLS exactly recovers the support of any K-sparse vector x from its samplesy = AxinK 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 δK+1 ≥ √ 1 K+ 14.

KW - Sparse recovery

KW - orthogonal least squares (OLS)

KW - orthogonal matching pursuit (OMP)

KW - restricted isometry property (RIP)

UR - https://www.scopus.com/pages/publications/85028912110

U2 - 10.1109/TSP.2017.2728502

DO - 10.1109/TSP.2017.2728502

M3 - 文章

AN - SCOPUS:85028912110

SN - 1053-587X

VL - 65

SP - 5347

EP - 5356

JO - IEEE Transactions on Signal Processing

JF - IEEE Transactions on Signal Processing

IS - 20

M1 - 7982803

ER -

Nearly Optimal Bounds for Orthogonal Least Squares

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this