A Sharp Restricted Isometry Constant Bound of Orthogonal Matching Pursuit

2015/01/08 by Qun Mo, Mo, Qun · 2 citations
Computer Science · Engineering · #15A23 #15A54 #42C40 #Control Systems and Identification #FOS: Computer and information sciences #Face and Expression Recognition #Information Theory (cs.IT) #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.1501.01708

openalex publication_date 2015/01/08 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28

Abstract

We shall show that if the restricted isometry constant (RIC) δ_s+1(A) of the measurement matrix A satisfies δ_s+1(A) lt; (1)/(√(s + 1)), then the greedy algorithm Orthogonal Matching Pursuit(OMP) will succeed. That is, OMP can recover every s-sparse signal x in s iterations from b = Ax. Moreover, we shall show the upper bound of RIC is sharp in the following sense. For any given s ∈ \N, we shall construct a matrix A with the RIC δ_s+1(A) = (1)/(√(s + 1)) such that OMP may not recover some s-sparse signal x in s iterations.

Cited by

• A Sharp Condition for Exact Support Recovery of Sparse Signals With Orthogonal Matching Pursuit
• A Quasi-Orthogonal Matching Pursuit Algorithm for Compressive Sensing

Related

• A remark on the Restricted Isometry Property in Orthogonal Matching Pursuit
• Remarks on the Restricted Isometry Property in Orthogonal Matching Pursuit algorithm
• Improved Bounds on the Restricted Isometry Constant for Orthogonal Matching Pursuit
• A Sharp Condition for Exact Support Recovery of Sparse Signals With Orthogonal Matching Pursuit
• Analysis of Orthogonal Matching Pursuit using the Restricted Isometry Property