The name is absent

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.5)

X

satisfies ||ж — ж||₂ < C_Ne + C^,∕_cσ⅛(≈) with overwhelming probability. C_n and C⅛ are
the noise and approximation error amplification constants, respectively; e is an upper

<<   35   36   37   38   39   40   41   >>

More intriguing information