The performance of orthogonal multi-matching pursuit under RIP

DOI10.4208/JCM.1505-M4529arXiv1210.5323MaRDI QIDQ6236491FDOQ6236491

Authors: Zhiqiang Xu 

Publication date: 19 October 2012

Abstract: The orthogonal multi-matching pursuit (OMMP) is a natural extension of orthogonal matching pursuit (OMP). We denote the OMMP with the parameter $M$ as OMMP(M) where $Mgeq1$ is an integer. The main difference between OMP and OMMP(M) is that OMMP(M) selects $M$ atoms per iteration, while OMP only adds one atom to the optimal atom set. In this paper, we study the performance of orthogonal multi-matching pursuit (OMMP) under RIP. In particular, we show that, when the measurement matrix A satisfies $(9s,1/10)$-RIP, there exists an absolutely constant $M_{0}leq8$ so that OMMP(M_0) can recover $s$-sparse signal within $s$ iterations. We furthermore prove that, for slowly-decaying $s$-sparse signal, OMMP(M) can recover s-sparse signal within $O(fracsM)$ iterations for a large class of $M$. In particular, for $M=s^a$ with $ain[0,1/2]$, OMMP(M) can recover slowly-decaying $s$-sparse signal within $O(s^{1-a})$ iterations. The result implies that OMMP can reduce the computational complexity heavily.

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

This page was built for publication: The performance of orthogonal multi-matching pursuit under RIP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6236491)