\section{Approximate Model-CoSaMP}
\label{sec:amcosamp}
In this Section, we propose a second algorithm for model-based compressive sensing with approximate projection oracles.
Our algorithm is a generalization of model-based CoSaMP, which was initially developed in~\cite{modelcs}.
We call our variant \emph{Approximate Model-CoSaMP} (or AM-CoSaMP); see
Algorithm~\ref{alg:approxmodelcosamp} for a complete description. 

Algorithm~\ref{alg:approxmodelcosamp} closely resembles the {\em Signal-Space
CoSaMP} (or SSCoSaMP) algorithm proposed and
analyzed in~\cite{davenport_redundant,GN13}. Like our approach, SSCoSaMP also makes
assumptions about the existence of head- and tail-approximation
oracles. However, there are some important technical differences in our
development. SSCoSaMP was introduced in the context of
recovering signals that are sparse in overcomplete and incoherent
dictionaries.
In contrast, we focus on recovering signals from structured sparsity models.

Moreover, the authors of~\cite{davenport_redundant,GN13} assume that a \emph{single} oracle simultaneously achieves the conditions specified in Definitions \ref{def:headapproxoracle} and \ref{def:tailapproxoracle}.
In contrast, our approach assumes the existence of two separate head- and tail-approximation oracles and consequently is somewhat more general.
Finally, our analysis is simpler and more concise than that provided in~\cite{davenport_redundant,GN13} and follows directly from the results in Section~\ref{sec:amiht}. 

\begin{algorithm}[!t]
\caption{Approximate Model-CoSaMP}
\label{alg:approxmodelcosamp}
\begin{algorithmic}[1]
\Function{AM-CoSaMP}{$y,A,t$}
\State $x^0 \gets 0$
\For{$i \gets 0, \ldots, t$}
\State $b^i \gets A^T (y - A x^i)$
\State $\Gamma \gets \mathrm{supp}(H(b^i))$
\State $S \gets \Gamma \cup \mathrm{supp}(x^i)$ \label{line:cosampsupportupdate}
\State $z \vert_S \gets A_S\pinv y, \quad z \vert_{S^C} \gets 0$
\State $x^{i+1} \gets T(z)$
\EndFor
\State \textbf{return} $x^{t+1}$
\EndFunction
\end{algorithmic}
\end{algorithm}


We prove that AM-CoSaMP (Alg.\ \ref{alg:approxmodelcosamp}) exhibits robust signal recovery.
We make the same assumptions as in Section \ref{sec:amiht}:
(i) $x \in \R^n$ and $x \in \Mmodel$.
(ii) $y = A x + e$ for an arbitrary $e \in \R^m$ (the measurement noise).
(iii) $T$ is a $(c_T, \Msupports, \Msupports_T, 2)$-tail-approximation oracle.
(iv) $H$ is a $(c_H, \Msupports_T \supportplus \Msupports, \Msupports_H, 2)$-head-approximation-oracle.
(v) $A$ has the $(\delta, \Msupports \supportplus \Msupports_T \supportplus \Msupports_H)$-model-RIP.
Our main result in this section is the following:

\begin{theorem}[Geometric convergence of AM-CoSaMP]
\label{thm:amcosamp}
Let $r^i = x-x^i$, where $x^i$ is the signal estimate computed by AM-CoSaMP in iteration $i$.
Then, 
\begin{equation*}
\norm{r^{i+1}}_2  \leq \alpha \norm{r^i}_2 + \beta \norm{e}_2 \, ,
\end{equation*}
where 
\begin{align*}
\alpha &= (1+c_T) \sqrt{ \frac{1+\delta}{1-\delta}} \sqrt{1
  -\alpha_0^2} \, , \\
\beta &= (1+c_T) \left[\sqrt{ \frac{1+\delta}{1-\delta}} \left(\frac{\beta_0}{\alpha_0} + \frac{\alpha_0 \beta_0}{\sqrt{1-\alpha_0^2}}\right) + \frac{2}{\sqrt{1-\delta}} \right] \, , \\
\alpha_0 &= c_H (1 - \delta) - \delta \, , \\
\beta_0 &= (1+c_H)\sqrt{1+\delta} \, .
\end{align*}

\end{theorem}
\begin{proof}
We can bound the error $\norm*{r^{i+1}}_2$ as follows:
\begin{align*}
\norm{r^{i+1}}_2 &= \norm{x - x^{i+1}}_2 \\
    &\leq  \norm{x^{i+1} - z}_2 + \norm{x - z}_2 \\
    &\leq  c_T \norm{x - z}_2 + \norm{x - z}_2 \\
    &= (1 + c_T) \norm{x - z}_2 \\
    &\leq  (1 + c_T) \frac{\norm{A (x - z )}_2}{\sqrt{1 - \delta}} \\
    &=  (1 + c_T) \frac{\norm{ Ax - A  z }_2}{\sqrt{1 - \delta}} \, .
\end{align*}
Most of these inequalities follow the same steps as the proof provided in~\cite{cosamp}.
The second relation above follows from the triangle inequality, the third relation follows from the tail approximation property and the fifth relation follows from the $(\delta, \Msupports \supportplus \Msupports_T \supportplus \Msupports_H)$-model-RIP of $A$.

We also have $Ax = y - e$ and $Az = A_S z_S$.
Substituting, we get:
\begin{align*}
\norm{r^{i+1}}_2 & \leq   (1 + c_T) \left( \frac{\norm{ y - A_S  z_S }_2}{\sqrt{1 - \delta}} + \frac{\norm{e}_2}{\sqrt{1 -\delta}} \right) \\
& \leq   (1 + c_T) \left( \frac{\norm{ y - A_S  x_S }_2}{\sqrt{1 - \delta}} + \frac{\norm{e}_2}{\sqrt{1 -\delta}} \right) \, . \numberthis \label{eq:cosamperror}
\end{align*}
The first inequality follows from the triangle inequality and the second from the fact that $z_S$ is the least squares estimate $A_S\pinv y $ (in particular, it is at least as good as $x_S$).

Now, observe that $y = Ax +e = A_S x_S + A_{S^c} x_{S^c} + e$.  Therefore, we can further simplify inequality \eqref{eq:cosamperror} as
\begin{align*}
\norm{r^{i+1}}_2 & \leq (1 + c_T) \frac{\norm{ A_{S^c}  x_{S^c}}_2}{\sqrt{1 - \delta}} + (1+c_T) \frac{2\norm{e}_2}{\sqrt{1-\delta}} \\
    &\leq  (1 + c_T) \frac{\sqrt{1 + \delta}}{\sqrt{1 - \delta}} \norm{  x_{S^c} }_2 + (1+c_T) \frac{2\norm{e}_2}{\sqrt{1 -\delta}} \\
    &= (1 + c_T) \sqrt{\frac{{1 + \delta}}{{1 - \delta}}} \norm{ (x - x^i)_{S^c} }_2 + (1+c_T) \frac{2\norm{e}_2}{\sqrt{1 -\delta}} \\
    &\leq (1 + c_T) \sqrt{\frac{{1 + \delta}}{{1 - \delta}}} \norm{  r^i_{\Gamma^c} }_2 + (1+c_T) \frac{2\norm{e}_2}{\sqrt{1 -\delta}} \numberthis \label{eq:ineq1} \, .
\end{align*}
The first relation once again follows from the triangle inequality.
The second relation follows from the fact that $\supp(x_{S^c}) \in \Msupports^+$ (since $\supp(x) \in \Msupports^+$), and therefore, $A_{S^c} x_{S^c}$ can be upper-bounded using the model-RIP.
The third follows from the fact that $x_i$ supported on $S^c$ is zero because $S$ fully subsumes the support of $x^i$.
The final relation follows from the fact that $S^c \subseteq \Gamma^c$ (see line \ref{line:cosampsupportupdate} in the algorithm).

Note that the support $\Gamma$ is defined as in Lemma \ref{lemma:headiht_rip}.
Therefore, we can use \eqref{eq:rlambdac} and bound $\norm{r^i_{\Gamma^c}}_2$ in terms of $\norm{r^i}_2$, $c_H$, and $\delta$.
Substituting into \eqref{eq:ineq1} and rearranging terms, we obtain the stated theorem.
\end{proof}

As in the analysis of AM-IHT, suppose that $e = 0$ and $\delta$ is very small.
Then, we achieve geometric convergence, i.e., $\alpha < 1$, if the approximation factors $c_T$ and $c_H$ satisfy
\begin{equation}
(1 + c_T) \sqrt{1 - c_H^2} < 1 \, , \qquad \textnormal{or equivalently, } \qquad c_H^2 > 1 - \frac{1}{(1 + c_T)^2}\, .
\label{eq:headtail_cosamp}
\end{equation}
Therefore, the conditions for convergence of AM-IHT and AM-CoSaMP are identical in this regime.
As for AM-IHT, we relax this condition for AM-CoSaMP in Section \ref{sec:boosting} and show that geometric convergence is possible for \emph{any} constants $c_T$ and $c_H$.
{"config": "arxiv", "file": "1406.1579/approxmodelcosamp.tex"}