Total per iteration
implemented in time O(s), but it may be preferable to sort
the components of the vector and then select the first s at a
cost of O(s log s).
sample Update. This step is dominated by the cost of the
multiplication of F with the s-sparse vector ak.
Table 1 summarizes the cost of each step for the cases in
which the standard and fast multiply is used.
Finally, we may analyze the storage requirements of the
algorithm. Aside from the sampling matrix storage requirement, the algorithm constructs only one vector of length N,
the signal proxy. The sample vectors u and v have length m,
and thus require O(m) storage. Since the signal approximations are sparse, they can be stored using sparse data structures which require at most O(s log N) storage. Similarly, the
index sets that appear require only O(s log N) storage. The
total working storage is therefore O(N).
The following result summarizes these observations.
Theorem 1 (Resource Requirements). Each iteration
of CoSaMP requires O() time, where bounds the cost of a
multiplication with the matrix F or F*. The algorithm uses
working storage O(N).
3. 3. Error reduction bound
The theoretical analysis of the CoSaMP algorithm is based on
an estimate for how much the algorithm reduces the approximation error in each iteration. This result demonstrates that
the algorithm makes significant progress whenever the error
is substantially larger than a certain baseline value. We call
this baseline the unrecoverable energy n in the signal:
The unrecoverable energy is due to the noise in the samples and the fact that the signal is not exactly sparse. For a
detailed discussion, see Section 2. 5 of Needell and Tropp. 19
Theorem 2 (Error Reduction). For each iteration k ≥ 0,
the signal approximation ak is s-sparse and
The main consequence of Theorem 2 is the fact that, after
log2(||x||2/h) iterations, the approximation error is no greater
than h + 20n. See Needell and Tropp18, 19 for more discussion.
The statement of Theorem A depends on a simple upper
bound for the l2 term in the unrecoverable energy:
This estimate is a consequence of Lemma 7 of Gilbert. 15
4. RELa TED WoRK
CoSaMP is inspired by algorithmic ideas and analytic techniques that have appeared previously. We briefly summarize
the major algorithmic approaches and compare them with
CoSaMP. This work can be classified in three rough categories: convex relaxation, 4, 11 greedy pursuits, 12, 20, 24 and combinatorial algorithms. 8, 14–16
The convex optimization methods1, 10 attempt to reconstruct signals by solving the mathematical program
where we assume that ||e|| 2 ≤ e. The intuition behind minimizing the l1 norm is that this norm promotes sparsity, and
so the solution to this program should approximate a compressible signal well. Candès et al. 3 establish that each minimizer a of Equation 6 satisfies
whenever F has restricted isometry constant d4s ≤ 0.2. These
restricted isometry constant requirements continue to be
improved. 2, 13 The error bound for CoSaMP is equivalent with
Equation 7, up to the precise value of the constants.