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)


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 CreatorsORCiD
Challa, Subrahmanya SastryUNSPECIFIED
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
Publisher URL:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 10317 Statistics for this ePrint Item