20
therefore impractical. Instead, we consider the optimization
x — arg min ∣[rr∣∣ι s.t. y = Фж, (2.3)
X
where the tγ norm of a signal is defined as the sum of the absolute values of its
components:
lkllι = Ekd∙ (2.4)
i
When the signal x is sparse in another reconstruction basis Φ (such as wavelets), the
reconstruction algorithm substitutes x = Φ6, in the constraint in equation (2.3) and
solve for the minimum Zl-norm of θ instead. Equation (2.3) is a convex optimization
that can be formulated as a linear program known as basis pursuit [55]. There also
exists a range of alternative reconstruction techniques based on greedy, stochastic,
and variational algorithms [56]. The major ones used in this thesis are the SPGLl
algorithm [57] and the minimization of total variation (min-TV) [9,58]. The attractive
property of CS Φ matrices is that this polynomial-time optimization procedure, under
the CS measurement scheme, yields perfect recovery of /.(-sparse signals when Φ takes
O(fclog(V∕fc)) measurements.
If x is not sparse, but can be represented well by its к largest components in some
basis, then the error of the reconstructed signal x is only a constant times the error
between x and its fc-term approximation. Or if the measurements у are corrupted
by noise, then the solution to the alternative Z⅛ minimization, known as basis pursuit
with inequality constraints (BPIC) [59]
x = arg min ∣∣τ∣∣ι s.t. ∖∖y — Φx∣∣2 < ∈, (2.5)
X
satisfies ||ж — ж||2 < CNe + C,∕cσ⅛(≈) with overwhelming probability. Cn and C⅛ are
the noise and approximation error amplification constants, respectively; e is an upper