Title: A Remark on the Restricted Isometry Property in Orthogonal Matching Pursuit
Abstract:This paper demonstrates that if the restricted isometry constant δ <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">K</i> +1 of the measurement matrix A sat...This paper demonstrates that if the restricted isometry constant δ <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">K</i> +1 of the measurement matrix A satisfies [δ <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">K</i> +1 <; 1 √K+1] then a greedy algorithm called Orthogonal Matching Pursuit (OMP) can recover every K-sparse signal x in K iterations from Ax. By contrast, a matrix is also constructed with the restricted isometry constant [δ <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">K</i> +1 = 1 √K] such that OMP can not recover some K-sparse signal x in K iterations. This result positively verifies the conjecture given by Dai and Milenkovic in 2009.Read More