Compressive Sampling

by Emamnuel J. Candès

This is the first paper I read about compressive sampling (a.k.a. compressed sensing). The main idea of CS is that we have a measure matrix Φ and a different representation matrix Ψ and they are quite different. The traditional way of signal processing would use the same matrix for measurement and representation. The Nyquist-Shannon theorem says we need a bandwidth as large as the connected support in Φ-domain. But in practice our signal is usually sparse in Ψ-domain but the sparse weights are not in a connected subset of the whole space. Therefore to apply N-S thereom, we need a large bandwidth to transmit the data. But then we might think we might miss the sparsity point.

The new findings in CS say that if the measurement Φ satisfies a certain condition, we might recover the sparse encoding in Ψ-domain with a linear programming solver:

min | x |₁ subject to ΦΨx=y

where y is the measurement of the groundtruth (i.e. Φf, where f is the original signal).

The measurement matrix Φ must satisfy the UUP (uniform uncertainty principle) or RIP (restricted isometry principle). To put it simple, it means that any subset of coordinates (cardinality less than S) under the transform of the corresponding part of Φ will keep the norm in a certain bound. This bound implies when the exact decoding will be successful. Many stochastic matrix can be candidates for Φ, e.g. Gaussian, binary, Fourier (randomly selected rows of Fourier transform), incoherent measurement (randomly selected rows of random orthoganal matrix). Experts are busy proving how few rows we need for exact decoding. That is to prove a tight upper bound for S(sparsity of Ψ-domain) with N(length of the signal) and K(number of measurements, #rows of Φ).

It can be proved that the recovered x is optimal in a sense. This idea can still be extend to the case of signal with noise.

There are research of CS in machine learning, exploiting the sparsity part. Since as SVM or RVM suggests, the classifier in the dual representation should be sparse. Therefore it seems possible to train a model in a randomly projected space without losing information. There has been work in this part. I will explore more about it later. For now we just need their idea.