Random Matrices Are Too Damn Large !

This morning, we saw that we could have fast reconstruction solvers that are not even specific to the sparsity constraint on the unknown. But one of the requirement had that the measurement matrix had to be a gaussian matrix. The main battleground for hardware makers and sensor designers is really to examine what sort of measurement matrix allows for seamless recovery. Sometimes, the measurement operator is known, sometimes, it is up for grabs. In a recent preprint mentioned here on Nuit Blanche [1], the authors developed a framework that re-evaluates compressive sensing with a newer mathematical slant. One of their very valid points is listed as follows:  

Storage and speed. 

Random matrices, popular in traditional CS, besides being inapplicable in many applications (most Type I problems), are also slow and require (large) storage. This yields slow recovery and limits the maximum signal size, which severely affects computations and, more importantly, sparsity structure. Section 10 discusses this aspect and also shows that simply addressing the speed and storage problems via fast transforms and non-random matrices is not sufficient to achieve improved recovery compared to what multilevel sampling of non-universal matrices can offer.

and later:

Storage/speed: Is non-random/orthogonality enough?

Random matrices have another important practical drawback: they require (large) storage and lack fast transforms. This limits the maximum signal resolution and yields slow recovery. For example, a 1024×1024 experiment with 25% subsampling of a random Gaussian matrix would require 2 Terabytes of free memory and O(10^12) time complexity, making it impractical at best

This is a good point and the reason why the single pixel camera, while inspirational, has remained limited to a niche market or that approaches like a tensor based projection made up of lower dimensional random vectors should be looked into. In about a few hours here on Nuit Blanche and nearly 10 years after the first papers on compressive sensing, we will try to provide a different solution to that issue. Let us also point out that this issue is not just for sensors and hardware makers. This week we saw that Big Data could be transformed in Smaller Data thanks to random projections. 

[1] http://nuit-blanche.blogspot.fr/2014/07/entropic-uncertainty-relations-in.html

Version 2 is: On asymptotic structure in compressed sensing by Bogdan Roman, Anders Hansen, Ben Adcock

This paper demonstrates how new principles of compressed sensing, namely asymptotic incoherence, asymptotic sparsity and multilevel sampling, can be utilised to better understand underlying phenomena in practical compressed sensing and improve results in real-world applications. The contribution of the paper is fourfold:

First, it explains how the sampling strategy depends not only on the signal sparsity but also on its structure, and shows how to design effective sampling strategies utilising this.

Second, it demonstrates that the optimal sampling strategy and the efficiency of compressed sensing also depends on the resolution of the problem, and shows how this phenomenon markedly affects compressed sensing results and how to exploit it.

Third, as the new framework also fits analog (infinite dimensional) models that govern many inverse problems in practice, the paper describes how it can be used to yield substantial improvements.

Fourth, by using multilevel sampling, which exploits the structure of the signal, the paper explains how one can outperform random Gaussian/Bernoulli sampling even when the classical l1 recovery algorithm is replaced by modified algorithms which aim to exploit structure such as model based or Bayesian compressed sensing or approximate message passaging. This final observation raises the question whether universality is desirable even when such matrices are applicable.

Examples of practical applications investigated in this paper include Magnetic Resonance Imaging (MRI), Electron Microscopy (EM), Compressive Imaging (CI) and Fluorescence Microscopy (FM). For the latter, a new compressed sensing approach is also presented.

Image Credit: NASA/JPL/Space Science Institute
N00225783.jpg was taken on July 07, 2014 and received on Earth July 07, 2014. The camera was pointing toward METHONE, and the image was taken using the CL1 and CL2 filters.

Join the CompressiveSensing subreddit or the Google+ Community and post there !

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.