Title: Sparse Recovery With Orthogonal Matching Pursuit Under RIP
Abstract:This paper presents a new analysis for the orthogonal matching pursuit (OMP) algorithm. It is shown that if the restricted isometry property (RIP) is satisfied at sparsity level <formula formulatype="...This paper presents a new analysis for the orthogonal matching pursuit (OMP) algorithm. It is shown that if the restricted isometry property (RIP) is satisfied at sparsity level <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex Notation="TeX">$O(\bar{k})$</tex></formula> , then OMP can stably recover a <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex Notation="TeX">$\bar{k}$</tex></formula> -sparse signal in 2-norm under measurement noise. For compressed sensing applications, this result implies that in order to uniformly recover a <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$\bar{k}$</tex></formula> -sparse signal in <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">${\BBR}^d$</tex></formula> , only <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$O(\bar{k} \ln d)$</tex></formula> random projections are needed. This analysis improves some earlier results on OMP depending on stronger conditions that can only be satisfied with <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$\Omega(\bar{k}^2 \ln d)$</tex></formula> or <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$\Omega(\bar{k}^{1.6} \ln d)$</tex> </formula> random projections.Read More