The name is absent

19

coefficient magnitudes decay under a power law with scaling exponent — r. We are
interested in recovering these signals exactly, with as few measurements as possible.

The first half of CS is the definition of a special linear, nonadaptive measurement
scheme. For a given ^-sparse signal x ∈ 3T^v, the measurements can be represented
mathematically as

y = Φx = φφθ.                          (2.1)

The matrix Φ is of size MxN, with M < N. The measurement process is nonadaptive
in that Φ does not depend in any way on the signal x. We would like the matrix
Φ to have the property that no two /с-sparse signals can result in having the same
measurements y. Mathematically speaking, Φ must be an injective mapping for k-
sparse signals. It has been shown that with high probability, random matrices of
i.i.d Gaussian (white noise) or ±1 entries (from a uniform Bernoulli distribution)
satisfy this property for sufficiently large M [8,9]. Other possible choices include
ranndonly permuted vectors from standard orthonormal bases, or random subsets of
basis vectors, such as Fourier or Walsh-Hadamard bases.

The second half of CS is recovering a signal x from the measurements y = Φx.
This is an ill-posed problem, since an infinite number of potential solutions all will
admit the given measurements. However we will choose as x the one that has the
sparsest representation. To find this we perform the optimization

x = arg min ∣∣x∣∣₀ s.t. y = Φx.                        (2.2)

X

This optimization of the ∕⅛ pseudo-norm (∣∣^∣∣o is the number of non-zero elements of
æ) finds, among all signals that satisfy the linear measurements, the signal that has
the fewest number of non-zero elements. Such an optimization is combinatorial and

<<   34   35   36   37   38   39   40   >>

More intriguing information