Improved Performance Guarantees for Orthogonal Matching Pursuit and Application to Dimensionality Reduction

Sonkar, Munnu and Tiwari, Latika and Challa, Subrahmanya Sastry (2021) Improved Performance Guarantees for Orthogonal Matching Pursuit and Application to Dimensionality Reduction. In: International Conference on Machine Vision and Augmented Intelligence, MAI 2021, 11 February 2021 through 14 February 2021, Jabalpur.

Full text not available from this repository. (Request a copy)

Abstract

In Compressed Sensing (CS), Orthogonal Matching Pursuit (OMP) is a popular solver for recovering the sparse solution of an underdetermined system. The performance guarantees of OMP involving coherence-based arguments are known to be pessimistic. The present work aims at improving the performance guarantees via preconditioning. Since the systems Ax = y and GAx = Gy have the same set of solutions, both analytically and numerically, for an invertible and well-conditioned matrix G, while singling out the conditions, we determine G via a convex optimization problem in such a way that the performance guarantees of OMP get improved. Alongside the proof of concept, we demonstrate the implications of proposed improved bound towards dimensionality reduction by considering the reconstruction of a signal from a small set of its linearly projected samples. © 2021, The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.

[error in script]

IITH Creators:

IITH Creators	ORCiD
Challa, Subrahmanya Sastry	UNSPECIFIED

Item Type:

Conference or Workshop Item (Paper)

Additional Information:

Acknowledgements The first author is thankful to the MHRD, Govt. of India, for its financial support. The third author is grateful to the CSIR, Govt. of India (25(0309)/20/EMR-II) for its support.

Uncontrolled Keywords:

Compressive Sensing; Improved recovery guarantees; OMP algorithm; Preconditioning

Subjects:

Mathematics

Divisions:

Department of Mathematics

Depositing User:

. LibTrainee 2021

Date Deposited:

27 Aug 2022 10:16

Last Modified:

27 Aug 2022 10:16