Data Science Part 22: Compressed Sensing and Sparse Recovery

 

The traditional approach samples above the Nyquist rate which is a value twice the highest frequency of a given signal. Here, we can compress the data using transform coding, and we have lots of work to throw away, in fact around 90% off all of the coefficients, and we perform the most computation at the sensor. This is a brick wall to the performance of modern acquisition systems. This comes back to this picture:

.

The Shannon/Nyquist sample is the worst case bound for any bandlimited signal. However, it is too pessimistic for some classes of signals and does not exploit the sparsity/compressibility of a signal. We seek the direct sensing of compressible information. In compressed sensing, sparse signals can be recovered from a small number of nonadaptive (fixed) linear measurements. We will measure linear projection onto random basis where the data is not sparse M ≈ K log(N/K) << N, where the random "white noise" is universally incoherent, and mild "over-sampling" in analog. Random projections are also highly asymmetrical, with the most computation at the receiver. 

In compressed sensing, we replace sample by the more general encoder based on a few linear projections or inner product. N is the number of samples/signals and K is the number of size-bound wavelet coefficients. M is the number of measurements. These "random" projections are universal for any compressible or sparse signal class. 

Now an inner product space is basically just a vector space that also has an inner product. Conjugate symmetry indicates that <v1, v2> also must equal <v2, v1>. The linearity in the first argument indicates that <αv1 + βv2, v3i> = α<v1, v3> + β<v2, v3>, also called the sesquilinear form.  Positive definite indicates <v, v> >= 0 and only equal to 0 if v = 0. In Real-valued vectors, the inner product is defined as

which is the sum of pairwise products. It's an integral for Complex-valued functions over time range.

In Compressed Sensing decoding, our goal is to find x given y and it is an ill-posed inverse problem. We can try to search over subspace of explanations to measurements and find the "most likely" explanation. Universality is accounted for during optimization. We can also perform linear program decoding. 

Compressed Sensing changes the rules of data acquisition game. It exposes deduced sparsity information to reduce the amount of measurements. Universality indicates that we have the same random projections for any compressible signal class, and simplifies hardware and algorithm design as a result. Processing results in information scalability, where we can make random projections with sufficient statistics. Some random projections are made by decoding, estimation, recognition, and detection, and using information scalability, there are far fewer measurements required for detection and recognition. 

Machine learning features linear models in the form y = Φx + n where compressive signal preocessin is more of a signal acquisition approach. X is the unknown signal, x is the matrix relating linear terms, y is the measurements, and n is the noise. We want to design a matrix Φ that is compatible with the sensing hardware and a recovery algorithm that provides a solid estimation of x. Φ is given to us in machine learning whereas we need to estimate Φ in compressive sensing. 

It is taking a high dimensional signal and reconstructing this signal even with a lot of sparsity, based on advances in sparse optimization with a few compressed or random measurements. Again, being J-sparse indicates having K non-zeros. In compressed sensing we want to find the sparsest vector s that is consistent with the measurements y = CΨs = Θs, thus trying to minimize the cardinality of s. 

Now let's describe the optimal computation of random projections. We got an image encoded by pulse width modulation on a random basis, and low cost, fast, sensitive optical detection for cost purposes. We can finally send the compressed, encoded image data for reconstruction. We can also utilize the approximate message passing algorithm, which will be discussed in more detail later. 

Through these techniques, we con obtain a slightly blurrier yet "good" version of these images. 

Hyperspectral imaging collects and processes information from across the electromagnetic spectrum, which processes different information of images at various different wavelengths. The applications of this include medical imagine, geology, astronomy, and remote sensing.  

Coded aperture snapshot spectral imagine, or CASSI, can capture data through a 2 dimensional focal plane, where dispersion shifts frequencies differently. It is just another amp-based reconstruction algorithm. 

For a radio telescope, a parabola that is 105 m wide focuses radio waves in which we want improved imaging. The image measurement process can be VERY noisy and we often want to recover an image. We have to construct a matrix on the fly and image reconstruction took a week, and subtract the interference. Just some examples of approximate message passing. 

Before compressed Sensing, given measurements y, we want to successfully find the signal X. The classical solution is the least squares method, denoted by the equations

and

. However this method isn't the most efficient. Another problem is that small L2 doesn't imply sparsity, and that there are infinitely many solutions X̂.

An ideal approach ℓ0 is too exploit the sparsest one. Out of infinitely many solutions X̂, seek the sparsest one where ||x|| is the number of nonzero entries. However, there are many problems of using ℓ0. It's not very robust and has a high combinatorial complexity. 

Alternatively, we can try to seek the one with the smallest ℓ1 norm. The L0 and L1 functions are below:

. If number of measurements  >= c * number of nonzeroes or M >= cK then we have a perfect reconstruction with high probability at approximately c ≈ 3. (M >= cK, c ≈ 3). This is the linear programming implementation. 

Suppose x is sparse in basis Ψ. Then we can write Can write 𝑥 = ΨΘ where the sparsifying basis Ψ ∈ ℝ𝑁×𝑁 and the sparse coefficients ∈ ℝ𝑁. 

We can also account for noise measurements, n, as 𝑦 = Φ𝑥 + 𝑛 = ΦΨ𝜃 +  𝑛. Then we can solve for θ, which is argmin||θ||1, where y = ΦΨ𝜃 then finally use 𝑥 = ΨΘ to solve for x. The least squares algorithm unfortunately doesn't induce sparsity, since the ℓ0  minimization is too slow and the ℓ1 minimization is computationally tractable, but has somewhat more measurements. 

Now, it's time to discuss the variations in Sparse Recovery. Recall that in the linear program in approximately infinitely many solutions we have to seek the one with the smallest ℓ1 norm. However, we might have too much measurement noise. 

|

V

We must explain the LASSO situation which is indicative of the unexplained part of the measurements,

 which forces us to try to decide a well chosen Lagrangian parameter λ:

which accounts for the tradeoff between the sparsity signal x and the unexplained measurements y − Φx. When λ is close to infinite, we get some l1 optimization where we basically select the largest signal. λ approaching 0 makes the unexplained portions of the measurements essentially irrelevant which means we get the unhelpful x hat of 0. The best option is to select a medium value of   λ for LASSO.

An example of this is the Compressive Sampling matching pursuit or CoSamp. It's an iterative algorithm by Needell and Tropp. It works as follows: 

In iteration j find K-sparse signal estimate: Xj = prune (bk). Compute the residual r = y - Φ𝑥j. Compute the error ΦTr and the best 2K-support set of error Ω = 𝑒2K. Merge the support sets 𝑇 = Ω ∪ supp(xj). The final least squares calculation is formulated as follows: