\section{Approximate Model-IHT}
\label{sec:amiht}

We now introduce our \emph{approximation-tolerant model-based
  compressive sensing} framework. Essentially, we extend the model-based compressive sensing framework to
work with approximate projection oracles, which we formalize in the definitions below.
This extension enables model-based compressive sensing in cases where optimal model projections are beyond our reach, but approximate projections are still efficiently computable. 

The core idea of our framework is to utilize \emph{two} different notions of
approximate projection oracles, defined as follows.

\begin{definition}[Head approximation oracle]
\label{def:headapproxoracle}
  Let $\Msupports, \Msupports_H \subseteq \powerset([n])$, $p \geq 1$, and $c_H \in \R$.
  Then $H : \R^n \rightarrow \powerset([n])$ is a $(c_H, \Msupports, \Msupports_H, p)$-head-approximation oracle if the following two properties hold for all $x \in \R^n$:
  \begin{description}[font=\normalfont\itshape,nosep]
    \item[Output model sparsity:] $H(x) \in \Msupportsclosure_H$.
    \item[Head approximation:] Let $\Omega' = H(x)$.
        Then $\norm{x_{\Omega'}}_p \geq c_H \norm{x_\Omega}_p$ for all $\Omega \in \Msupports$.
  \end{description}
\end{definition}
\begin{definition}[Tail approximation oracle]\label{def:tailapproxoracle}
  Let $\Msupports, \Msupports_T \subseteq \powerset([n])$, $p \geq 1$ and $c_T \in \R$.
  Then $T : \R^n \rightarrow \powerset([n])$ is a $(c_T, \Msupports, \Msupports_T, p)$-tail-approximation oracle if the following two properties hold for all $x \in \R^n$:
  \begin{description}[font=\normalfont\itshape,nosep]
    \item[Output model sparsity:] $T(x) \in \Msupportsclosure_T$.
    \item[Tail approximation:] Let $\Omega' = T(x)$.
        Then $\norm{x - x_{\Omega'}}_p \leq c_T \norm{x - x_\Omega}_p$ for all $\Omega \in \Msupports$.
  \end{description}
\end{definition}

We trivially observe that a head approximation oracle with approximation factor $c_H = 1$ is equivalent to a tail approximation oracle with factor $c_T = 1$, and vice versa.
Further, we observe that for any model $\Mmodel$, if $x \in \Mmodel$ then $\norm{x - x_\Omega}_2 = 0$ for some $\Omega \in \Msupports$. Hence, \emph{any} tail approximation oracle must be exact in the sense that the returned support $\Omega'$ has to satisfy $\norm{x - x_{\Omega'}}_2 = 0$, or equivalently, $\supp(x) \subseteq T(x)$.
On the other hand, we note that $H(x)$ does not need to return an optimal support if the input signal $x$ is in the model $\Mmodel$.

An important feature of the above definitions of approximation oracles is that they permit projections into \emph{larger} models.
In other words, the oracle can potentially return a signal that
belongs to a larger model $\Msupports' \supseteq \Msupports$.
For example, a tail-approximation oracle for the CEMD model with parameters $(k,B)$ is allowed to return a signal with parameters $(2k,2B)$, thereby relaxing both the sparsity constraint and the EMD-budget. We exploit this feature in our algorithms in Section \ref{s:emd}.

Equipped with these notions of approximate projection oracles, we introduce a new algorithm for model-based compressive sensing.
We call our algorithm \emph{Approximate Model-IHT} (AM-IHT); see Algorithm~\ref{alg:approxmodeliht} for a full description.
Notice that every iteration of AM-IHT uses \emph{both} a head-approximation oracle $H$ and a tail-approximation oracle $T$.
This is in contrast to the Model-IHT algorithm discussed above in Section~\ref{sec:counterexample}, which solely made use of a tail approximation oracle $T'$. 

\begin{algorithm}[!t]
\caption{Approximate Model-IHT}
\label{alg:approxmodeliht}
\begin{algorithmic}[1]
\Function{AM-IHT}{$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 $x^{i+1} \gets T(x^i + H(b^i))$
\EndFor
\State \textbf{return} $x^{t+1}$
\EndFunction
\end{algorithmic}
\end{algorithm}

Our main result of this section (Theorem~\ref{thm:amiht}) states the following:
if the measurement matrix $A$ satisfies the model-RIP for $\Msupports \supportplus \Msupports_T \supportplus \Msupports_H$ and approximate projection oracles $H$ and $T$ are available, then AM-IHT exhibits provably robust recovery.
We make the following assumptions in the analysis of AM-IHT:
(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.

As in IHT, we use the \emph{residual proxy} $b^i = A^T(y - A x^i)$ as the update in each iteration (see Algorithm \ref{alg:approxmodeliht}). 
The key idea of our proof is the following: when applied to the residual proxy $b^i$,  the head-approximation oracle $H$ returns a support $\Gamma$ that contains ``most'' of the relevant mass contained in $r^i$.
Before we formalize this statement in Lemma \ref{lem:resid}, we first establish the RIP of $A$ on all relevant vectors.
\begin{lemma}\label{lemma:headiht_rip}
Let $r^i = x - x^i$, $\Omega = \supp(r^i)$, and $\Gamma = \supp(H(b^i))$.
For all $x'\in\R^n$ with $\supp(x') \subseteq \Omega \cup \Gamma$ we have
\begin{equation*}
  (1 - \delta)\norm{x'}_2^2 \leq \norm{A x'}_2^2 \leq (1 + \delta)\norm{x'}_2^2 \; .
\end{equation*}
\end{lemma}
\begin{proof}
By the definition of $T$, we have $\supp(x^i) \in \Msupports_T$.
Since $\supp(x) \in \Msupports$, we have $\supp(x - x^i) \in \Msupports_T \supportplus \Msupports$ and hence $\Omega \in \Msupports_T \supportplus \Msupports$.
Moreover, $\supp(H(b^i)) \in \Msupports_H$ by the definition of $H$.
Therefore $\Omega \cup \Gamma \in \Msupports \supportplus \Msupports_T \supportplus \Msupports_H$, which allows us to use the model-RIP of $A$ on $x'$ with $\supp(x') \subseteq \Omega \cup \Gamma$.
\end{proof}

We now establish our main lemma, which will also prove useful in Section \ref{sec:amcosamp}.
A similar result (with a different derivation approach and different constants) appears in Section 4 of the conference version of this manuscript~\cite{approxSODA}.

\begin{lemma}
\label{lem:resid}
Let $r^i = x - x^i$ and $\Gamma = \supp(H(b^i))$.
Then, 
\begin{equation}
\norm{r^i_{\Gamma^c}}_2  \, \leq \,  \sqrt{1 - \alpha_0^2}\norm{r^i}_2 +
\left[\frac{\beta_0}{\alpha_0} + \frac{\alpha_0 \beta_0}{\sqrt{1-\alpha_0^2}} \right] \norm{e}_2 \, .
\label{eq:rlambdac}
\end{equation}
where
$$
\alpha_0 = c_H (1 - \delta) - \delta \qquad\text{and} \qquad\beta_0 = (1+c_H)\sqrt{1+\delta} \, . 
$$
We assume that $c_H$ and $\delta$ are such that $\alpha_0 > 0$.
\end{lemma}
\begin{proof}
We provide lower and upper bounds on $\norm*{H(b^i)}_2 = \norm{b^i_\Gamma}_2$, where $b^i = A^T(y - Ax_i) = A^T A r^i + A^T e$.
Let $\Omega = \supp(r^i)$.
From the head-approximation property, we can bound $ \norm{b^i_\Gamma}_2$ as:
\begin{align*}
\norm{b^i_\Gamma}_2 &= \norm{A_\Gamma^T A r^i + A_\Gamma^T e}_2 \\
    & \geq  c_H \norm{A_\Omega^T A r^i + A_\Omega^T e}_2 \\
    & \geq c_H \norm{A_\Omega^T A_\Omega r^i }_2 - c_H \norm{A_\Omega^T e}_2 \\
    & \geq  c_H (1 - \delta) \norm{r^i}_2  - c_H \sqrt{1 + \delta} \norm{e}_2 \, ,
\end{align*}
where the inequalities follow from Fact~\ref{fact:modelrip} and the triangle inequality.
This provides the lower bound on $\norm{b^i_\Gamma}_2$.

Now, consider $r_\Gamma$. By repeated use of the triangle inequality, we get
\begin{align*}
\norm{b^i_\Gamma}_2 &= \norm{A_\Gamma^T A r^i + A_\Gamma^T e}_2 \\
    &= \norm{A_\Gamma^T A r^i - r^i_\Gamma + r^i_\Gamma + A_\Gamma^T e}_2 \\
    &\leq \norm{A_\Gamma^T A r^i - r^i_\Gamma}_2 + \norm{r^i_\Gamma}_2 + \norm{A_\Gamma^T e}_2 \\
    &\leq \norm{A_{\Gamma \cup \Omega}^T A r^i - r^i_{\Gamma \cup \Omega}}_2 + \norm{r^i_\Gamma}_2 + \sqrt{1+\delta}\norm{e}_2 \\
    &\leq \delta \norm{r^i}_2 + \norm{r^i_\Gamma}_2 + \sqrt{1+\delta}\norm{e}_2 \, ,
\end{align*}
where the last inequality again follows from Fact~\ref{fact:modelrip}.
This provides the upper bound on  $\norm{b^i_\Gamma}_2$.

Combining the two bounds and grouping terms, we obtain the following inequality.
In order to simplify notation, we write $\alpha_0 = c_H (1 - \delta) - \delta$
and $\beta_0 = (1+c_H)\sqrt{1+\delta}$. 
\begin{equation}
\label{eq:lower_head}
\norm{r^i_\Gamma}_2 \geq \alpha_0 \norm{r^i}_2 - \beta_0 \norm{e}_2 \, .
\end{equation}
Next, we examine the right hand side of \eqref{eq:lower_head} more carefully.
Let us assume that the RIP constant $\delta$ is set to be small enough such that it satisfies $c_H > \delta/(1-\delta)$.
There are two mutually exclusive cases:

\noindent{\emph{Case 1:}} The value of $\norm*{r^i}_2$ satisfies $\alpha_0 \norm*{r^i}_2 \leq \beta_0 \norm{e}_2$.
Then, consider the vector $r^i_{\Gamma^c}$, i.e., the vector $r^i$ restricted to the set of coordinates in the complement of $\Gamma$.
Clearly, its norm is smaller than $\norm{r^i}_2$.
Therefore, we have
\begin{equation}
\norm{r^i_{\Gamma^c}}_2 \leq \frac{\beta_0}{\alpha_0} \norm{e}_2 \, . \label{eq:iht_case1}
\end{equation}
\noindent{\emph{Case 2:}} The value of $\norm*{r^i}_2$ satisfies $\alpha_0 \norm*{r^i}_2 \geq \beta_0 \norm{e}_2$.
Rewriting \eqref{eq:lower_head}, we get
\[
\norm{r^i_\Gamma}_2 \geq \norm{r^i}_2 \left(\alpha_0 - \frac{\beta_0 \norm{e}_2}{\norm{r_i}_2} \right) \, . 
\]
Moreover, we also have $\norm{r^i}_2^2 = \norm{r^i_\Gamma}_2^2 +
\norm{r^i_{\Gamma^c}}_2^2$. 
Therefore, we obtain
\begin{equation}
\norm{r^i_{\Gamma^c}}_2  \leq \norm{r^i}_2  \sqrt{1 - \left(\alpha_0 - \beta_0 \frac{\norm{e}_2}{\norm{r^i}_2} \right)^2}\, .
\label{eq:iht_case2_prelim}
\end{equation}

We can simplify the right hand side using the following  geometric
argument, adapted from~\cite{lee2010admira}.
Denote $\omega_0= \alpha_0 - \beta_0 \norm{e}_2/\norm{r^i}_2 $.
Then, $0 \leq \omega_0 < 1$ because $\alpha_0 \norm*{r^i}_2 \geq \beta_0 \norm{e}_2$, $\alpha_0 < 1$, and $\beta_0 \geq 1$.
The function $g(\omega_0) = \sqrt{1-\omega_0^2}$ traces an arc of the unit circle as a function of $\omega_0$ and therefore is upper-bounded by the $y$-coordinate of \emph{any} tangent line to the circle evaluated at $\omega_0$.
For a free parameter $0 < \omega < 1$ (the tangent point of the tangent line), a straightforward calculation yields that
\[
\sqrt{1-\omega_0^2} \leq \frac{1}{\sqrt{1-\omega^2}} - \frac{\omega}{\sqrt{1-\omega^2}} \omega_0 \; .
\]
Therefore, substituting into the bound
for $\norm{r^i_{\Gamma^c}}_2$, we get:
\begin{align*}
\norm{r^i_{\Gamma^c}}_2  &\leq \norm{r^i}_2 \left(
  \frac{1}{\sqrt{1-\omega^2}}  - \frac{\omega}{\sqrt{1-\omega^2}} \left( \alpha_0 -
    \beta_0 \frac{\norm{e}_2}{\norm{r^i}_2} \right) \right) \\
&=\frac{1-\omega\alpha_0}{\sqrt{1-\omega^2}} \norm{r^i}_2 + \frac{\omega
  \beta_0}{\sqrt{1-\omega^2}} \norm{e}_2 \; .
\end{align*}
The coefficient preceding $\norm{r^i}_2$ determines the overall convergence rate, and the minimum value of the coefficient is attained by setting
$\omega = \alpha_0$. Substituting, we obtain
\begin{equation}
\norm{r^i_{\Gamma^c}}_2 \leq \sqrt{1-\alpha_0^2} \norm{r^i}_2 +
\frac{\alpha_0 \beta_0}{\sqrt{1-\alpha_0^2}} \norm{e}_2 \, .
\label{eq:iht_case2}
\end{equation}
Combining the mutually exclusive cases \eqref{eq:iht_case1} and
\eqref{eq:iht_case2}, we obtain
\begin{equation*}
\norm{r^i_{\Gamma^c}}_2  \leq  \sqrt{1 - \alpha_0^2}\norm{r^i}_2 +
\left[\frac{\beta_0}{\alpha_0} + \frac{\alpha_0 \beta_0}{\sqrt{1-\alpha_0^2}} \right] \norm{e}_2 \, ,
\end{equation*}
which proves the lemma.
\end{proof}

\begin{theorem}[Geometric convergence of AM-IHT]
\label{thm:amiht}
Let $r^i = x-x^i$, where $x^i$ is the signal estimate computed by AM-IHT 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)\left[\delta + \sqrt{1 -\alpha_0^2}\right]\, , & \beta &= (1+c_T)\left[\frac{\beta_0}{\alpha_0} + \frac{\alpha_0 \beta_0}{\sqrt{1-\alpha_0^2}} +  \sqrt{1+\delta}\right] \, , \\
\alpha_0 &= c_H (1 - \delta) - \delta\, , & \beta_0 &= (1+c_H)\sqrt{1+\delta} \, .
\end{align*}
We assume that $c_H$ and $\delta$ are such that $\alpha_0 > 0$.
\end{theorem}
\begin{proof}
Let $a = x^i + H(b^i)$.  
From the triangle inequality, we have:
\begin{align*}
\norm{x - x^{i+1}}_2  &= \norm{x - T(a)}_2 \\
    &\leq  \norm{x - a}_2 + \norm{a - T(a)}_2 \\
    &\leq (1 + c_T) \norm{x - a}_2 \\
    &=  (1 + c_T) \norm{x - x^i - H(b^i)}_2  \\
&= (1 + c_T) \norm{r^i - H(A^T A r^i + A^T e)}_2 \numberthis \label{eq:tail_iht} \, .
\end{align*}

We can further bound $\norm{r^i - H(A^T A r^i + A^T e)}_2$ in terms of $\norm{r^i}_2$.
Let $\Omega = \supp(r^i)$ and $\Gamma = \supp(H(A^T A r^i + A^T e))$.
We have the inequalities
\begin{align*}
\norm{r^i - H(A^T A r^i + A^T e)}_2  = &~\norm{r^i_\Gamma +
  r^i_{\Gamma^c} - A_\Gamma^T A r^i + A_\Gamma^T e}_2 \\
 \leq &~\norm{A_\Gamma^T A r^i - r^i_\Gamma}_2 + \norm{r^i_{\Gamma^c}}_2 + \norm{A_\Gamma^T e}_2 \\
 \leq &~\norm{A_{\Gamma \cup \Omega}^T A r^i - r^i_{\Gamma \cup \Omega}}_2 + \norm{r^i_{\Gamma^c}}_2 + \norm{A_\Gamma^T e}_2 \\
 \leq &~\delta \norm{r^i}_2 + \sqrt{1 - \alpha_0^2}\norm{r^i}_2 + \left[\frac{\beta_0}{\alpha_0} + \frac{\alpha_0 \beta_0}{\sqrt{1-\alpha_0^2}} + \sqrt{1+\delta}\right] \norm{e}_2 \, ,
\end{align*}
where the last inequality follows from the RIP and
\eqref{eq:rlambdac}.
Putting this together with \eqref{eq:tail_iht} and grouping terms, we get 
\begin{equation}
\norm{x - x^{i+1}}_2 \leq \alpha \norm{x - x^i}_2 + \beta \norm{e}_2 \, ,
\label{eq:newbound}
\end{equation}
thus proving the Theorem. 
\end{proof}

In the noiseless case, we can ignore the second term and only focus on
the leading recurrence factor: 
$$\alpha = (1 + c_T) \left( \delta + \sqrt{1 - (c_H (1 -
    \delta) - \delta)^2} \right) .$$
For convergence, we need $\alpha$ to be strictly smaller than 1.
Note that we can make $\delta$ as small as we desire since this assumption only affects the measurement bound by a constant factor.
Therefore, the following condition must hold for guaranteed convergence:
\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_iht}
\end{equation}
Under this condition, AM-IHT exhibits geometric convergence comparable to the existing model-based compressive sensing results of~\cite{modelcs}.
AM-IHT achieves this \emph{despite using only approximate projection
oracles}.
In Section \ref{sec:boosting}, we relax condition \eqref{eq:headtail_iht} so that geometric convergence is possible for \emph{any} constants $c_T$ and $c_H$.

The geometric convergence of AM-IHT implies that the algorithm quickly
recovers a good signal estimate. Formally, we obtain:
\begin{corollary}
\label{cor:amiht}
Let $T$ and $H$ be approximate projection oracles with $c_T$ and $c_H$ such that $0 < \alpha < 1$.
Then after $t = \ceil{\frac{\log \frac{\norm{x}_2}{\norm{e}_2}}{\log \frac{1}{\alpha}}}$ iterations, AM-IHT returns a signal estimate $\widehat{x}$ satisfying
\begin{equation*}
  \norm{x - \widehat{x}}_2 \leq \left(1 + \frac{\beta}{1 - \alpha} \right) \norm{e}_2 \; .
\end{equation*}
\end{corollary}
\begin{proof}
As before, let $r^i = x - x^i$.
Using $\norm*{r^0}_2 = \norm{x}_2$, Theorem \ref{thm:amiht}, and a simple inductive argument shows that
\[
  \norm*{r^{i+1}}_2 \leq \alpha^i \norm{x}_2 + \beta \norm{e}_2 \sum_{j=0}^i \alpha^j \, .
\]
For $i = \ceil{\frac{\log \frac{\norm{x}_2}{\norm{e}_2}}{\log \frac{1}{\alpha}}}$, we get $\alpha^i \norm{x}_2 \leq \norm{e}_2$.
Moreover, we can bound the geometric series $\sum_{j = 0}^t \alpha^j$ by $\frac{1}{1-\alpha}$.
Combining these bounds gives the guarantee stated in the theorem.
\end{proof}
{"config": "arxiv", "file": "1406.1579/approxmodeliht.tex"}