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 ∈ 3Tv, 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∣∣0 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