r ≥ | T supp(x)|,
The last consequence of the restricted isometry property
that we will need measures how much the sampling matrix
inflates nonsparse vectors. Its proof uses arguments from
Proposition 3 (Energy Bound). Suppose F verifies the
upper inequality of ( 3), viz.
Then, for every signal x,
5. 2. iteration invariant: sparse case
In proving Theorem 2, we first operate under the assumption
that the signal x is exactly s-sparse. We remove this assumption later.
Theorem 3 (Sparse Error Reduction). Assume x is s-sparse.
For each k ≥ 0, the signal approximation ak is s-sparse, and
Remark 3. This bound assumes the least-squares step in the
algorithm is performed without error. In Section 5 of Needell
and Tropp, 19 we study how many iterations of a least-squares
solver are needed to make the resulting error negligible. We
show that, if we use conjugate gradient for the estimation step
of CoSaMP, then initializing the least-squares algorithm with
the current approximation ak− 1, then Theorem 3 still holds.
The proof of the iteration invariant, Theorem 3 involves a
sequence of short lemmas, one for each step in the algorithm.
We fix an iteration k, and let a = ak− 1 be the signal approxima-
tion at the beginning of the iteration. We define the residual
as r = x − a, which must be 2s-sparse since both a and x are
s-sparse. We also observe that the vector v of updated sam-
ples can be interpreted as noisy samples of the residual:
The first step in the algorithm is the identification step,
in which a set of components is found corresponding to
locations where the residual signal has a lot of energy. This
is summarized by the following lemma which is proven in
Needell and Tropp. 19
Lemma 1 (Identification). The set W = supp(y2s), where
y = F*v is the signal proxy, contains at most 2s indices, and
Next, the algorithm merges the support of the current
estimate a with the new selection of components. The following simple lemma shows that components of the signal
x outside this set have small energy.
Lemma 2 (Support Merger). Let W be a set of at most 2s indices. The set T = W supp(a) contains at most 3s indices, and
The estimation step in the algorithm obtains values
for coefficients in the set T by solving a least-squares
problem. The next result bounds the error of this
Lemma 3 (Estimation19). Let T be a set of at most 3s indices,
and define the least-squares signal estimate b by the formulae
where u = Fx + e. Then
Proof. Note first that
Using the expression u = Fx + e and the fact
The cardinality of T is at most 3s, and x is s-sparse, so
Proposition 1 and Corollary 1 imply that
Combine the bounds to reach
Finally, invoke the hypothesis that d3s ≤ d4s ≤ 0.1.
Lemma 4 (Pruning19). The pruned approximation bs satisfies
At the end of the iteration, the new approximation is formed
by setting ak = bs. The sequence of lemmas above allows us to