A Near-Optimal Restricted Isometry Condition of Multiple Orthogonal Least Squares

Junhan Kim; Byonghyo Shim

doi:10.1109/ACCESS.2019.2907303

A Near-Optimal Restricted Isometry Condition of Multiple Orthogonal Least Squares

Junhan Kim, Byonghyo Shim

Department of Computer Science and Engineering

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

11 Citations (Scopus)

Abstract

In this paper, we analyze the performance guarantee of multiple orthogonal least squares (MOLS) in recovering sparse signals. Specifically, we show that the MOLS algorithm ensures the accurate recovery of any K -sparse signal, provided that a sampling matrix satisfies the restricted isometry property (RIP) with \begin{equation∗} \delta -{LK-L+2} < \frac {\sqrt {L}}{\sqrt {K+2L-1}}\end{equation∗} where L is the number of indices chosen in each iteration. In particular, if L=1 , our result indicates that the conventional OLS algorithm exactly reconstructs any K -sparse vector under \delta -{K+1} < \frac {1}{\sqrt {K+1}} , which is consistent with the best existing result for OLS.

Original language	English
Article number	8674762
Pages (from-to)	46822-46830
Number of pages	9
Journal	IEEE Access
Volume	7
DOIs	https://doi.org/10.1109/ACCESS.2019.2907303
Publication status	Published - 2019

Bibliographical note

Funding Information:
This work was supported in part by the National Research Foundation of Korea (NRFK) grant funded by the Korean Government (MSIP) (2016R1A2B3015576) and in part by the Framework of International Cooperation Program managed by NRFK (2016K1A3A1A20006019).

Publisher Copyright:
© 2013 IEEE.

Keywords

Sparse signal recovery
multiple OLS (MOLS)
orthogonal least squares (OLS)
restricted isometry property (RIP)

ASJC Scopus subject areas

General Computer Science
General Materials Science
General Engineering

Access to Document

10.1109/ACCESS.2019.2907303

Cite this

@article{aff26ee05f9549b68e32aecf8992b5ef,

title = "A Near-Optimal Restricted Isometry Condition of Multiple Orthogonal Least Squares",

abstract = "In this paper, we analyze the performance guarantee of multiple orthogonal least squares (MOLS) in recovering sparse signals. Specifically, we show that the MOLS algorithm ensures the accurate recovery of any K -sparse signal, provided that a sampling matrix satisfies the restricted isometry property (RIP) with \begin{equation∗} \delta -{LK-L+2} < \frac {\sqrt {L}}{\sqrt {K+2L-1}}\end{equation∗} where L is the number of indices chosen in each iteration. In particular, if L=1 , our result indicates that the conventional OLS algorithm exactly reconstructs any K -sparse vector under \delta -{K+1} < \frac {1}{\sqrt {K+1}} , which is consistent with the best existing result for OLS.",

keywords = "Sparse signal recovery, multiple OLS (MOLS), orthogonal least squares (OLS), restricted isometry property (RIP)",

author = "Junhan Kim and Byonghyo Shim",

note = "Funding Information: This work was supported in part by the National Research Foundation of Korea (NRFK) grant funded by the Korean Government (MSIP) (2016R1A2B3015576) and in part by the Framework of International Cooperation Program managed by NRFK (2016K1A3A1A20006019). Publisher Copyright: {\textcopyright} 2013 IEEE.",

year = "2019",

doi = "10.1109/ACCESS.2019.2907303",

language = "English",

volume = "7",

pages = "46822--46830",

journal = "IEEE Access",

issn = "2169-3536",

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

}

TY - JOUR

T1 - A Near-Optimal Restricted Isometry Condition of Multiple Orthogonal Least Squares

AU - Kim, Junhan

AU - Shim, Byonghyo

N1 - Funding Information: This work was supported in part by the National Research Foundation of Korea (NRFK) grant funded by the Korean Government (MSIP) (2016R1A2B3015576) and in part by the Framework of International Cooperation Program managed by NRFK (2016K1A3A1A20006019). Publisher Copyright: © 2013 IEEE.

PY - 2019

Y1 - 2019

N2 - In this paper, we analyze the performance guarantee of multiple orthogonal least squares (MOLS) in recovering sparse signals. Specifically, we show that the MOLS algorithm ensures the accurate recovery of any K -sparse signal, provided that a sampling matrix satisfies the restricted isometry property (RIP) with \begin{equation∗} \delta -{LK-L+2} < \frac {\sqrt {L}}{\sqrt {K+2L-1}}\end{equation∗} where L is the number of indices chosen in each iteration. In particular, if L=1 , our result indicates that the conventional OLS algorithm exactly reconstructs any K -sparse vector under \delta -{K+1} < \frac {1}{\sqrt {K+1}} , which is consistent with the best existing result for OLS.

AB - In this paper, we analyze the performance guarantee of multiple orthogonal least squares (MOLS) in recovering sparse signals. Specifically, we show that the MOLS algorithm ensures the accurate recovery of any K -sparse signal, provided that a sampling matrix satisfies the restricted isometry property (RIP) with \begin{equation∗} \delta -{LK-L+2} < \frac {\sqrt {L}}{\sqrt {K+2L-1}}\end{equation∗} where L is the number of indices chosen in each iteration. In particular, if L=1 , our result indicates that the conventional OLS algorithm exactly reconstructs any K -sparse vector under \delta -{K+1} < \frac {1}{\sqrt {K+1}} , which is consistent with the best existing result for OLS.

KW - Sparse signal recovery

KW - multiple OLS (MOLS)

KW - orthogonal least squares (OLS)

KW - restricted isometry property (RIP)

UR - http://www.scopus.com/inward/record.url?scp=85065160423&partnerID=8YFLogxK

U2 - 10.1109/ACCESS.2019.2907303

DO - 10.1109/ACCESS.2019.2907303

M3 - Article

AN - SCOPUS:85065160423

SN - 2169-3536

VL - 7

SP - 46822

EP - 46830

JO - IEEE Access

JF - IEEE Access

M1 - 8674762

ER -

A Near-Optimal Restricted Isometry Condition of Multiple Orthogonal Least Squares

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this