This paper is concerned with the performance of Orthogonal Matching Pursuit (OMP) algorithms applied to a dictionary $mathcal{D}$ in a Hilbert space $mathcal{H}$. Given an element $fin mathcal{H}$, OMP generates a sequence of approximations $f_n$, $n
=1,2,dots$, each of which is a linear combination of $n$ dictionary elements chosen by a greedy criterion. It is studied whether the approximations $f_n$ are in some sense comparable to {em best $n$ term approximation} from the dictionary. One important result related to this question is a theorem of Zhang cite{TZ} in the context of sparse recovery of finite dimensional signals. This theorem shows that OMP exactly recovers $n$-sparse signal, whenever the dictionary $mathcal{D}$ satisfies a Restricted Isometry Property (RIP) of order $An$ for some constant $A$, and that the procedure is also stable in $ell^2$ under measurement noise. The main contribution of the present paper is to give a structurally simpler proof of Zhangs theorem, formulated in the general context of $n$ term approximation from a dictionary in arbitrary Hilbert spaces $mathcal{H}$. Namely, it is shown that OMP generates near best $n$ term approximations under a similar RIP condition.
We consider the problem of optimal recovery of an element $u$ of a Hilbert space $mathcal{H}$ from $m$ measurements obtained through known linear functionals on $mathcal{H}$. Problems of this type are well studied cite{MRW} under an assumption that $
u$ belongs to a prescribed model class, e.g. a known compact subset of $mathcal{H}$. Motivated by reduced modeling for parametric partial differential equations, this paper considers another setting where the additional information about $u$ is in the form of how well $u$ can be approximated by a certain known subspace $V_n$ of $mathcal{H}$ of dimension $n$, or more generally, how well $u$ can be approximated by each $k$-dimensional subspace $V_k$ of a sequence of nested subspaces $V_0subset V_1cdotssubset V_n$. A recovery algorithm for the one-space formulation, proposed in cite{MPPY}, is proven here to be optimal and to have a simple formulation, if certain favorable bases are chosen to represent $V_n$ and the measurements. The major contribution of the present paper is to analyze the multi-space case for which it is shown that the set of all $u$ satisfying the given information can be described as the intersection of a family of known ellipsoids in $mathcal{H}$. It follows that a near optimal recovery algorithm in the multi-space problem is to identify any point in this intersection which can provide a much better accuracy than in the one-space problem. Two iterative algorithms based on alternating projections are proposed for recovery in the multi-space problem. A detailed analysis of one of them provides a posteriori performance estimates for the iterates, stopping criteria, and convergence rates. Since the limit of the algorithm is a point in the intersection of the aforementioned ellipsoids, it provides a near optimal recovery for $u$.
