## Thursday, March 29, 2012

### Sparse Measurement Matrices: What are they good for ?

In GraphLab workshop, Why should you care ? I listed a series of measurements matrices that are sparse as they may hold the key for faster reconstruction algorithms once you use Cloud computing. The underlying idea is that by being sparse, the solvers would use that property and the  GraphLab framework to sparsify the computations and optimally put them on several CPUs. With that in mind, I listed the following ensembles:
Let us note that these families of matrices involve matrices with both types of elements: 0/1 and real numbers. On the numerical side, here the obvious pros for these measurement matrices:

Sparse measurement matrices are indeed useful when it comes to numerical issues but the real question remains: Is there any other part of the process for which these matrices are useful ? How do they instantiate in real hardware and why would you map a sparse measurement matrix to a particular sensor or measurement process ?

Whenever you think of compressive sensing, on the acquisition part, you have to think about its main function: Multiplexing. Hence the reasoning for sparse measurement matrices resides in asking what are the pros and cons of sparse multiplexing, here is a list:

Cons:
• In the case of coded aperture or any DMD based system like the single pixel camera: Less luminosity is detected with each measurement yielding (Poisson) noise issues.
• Coefficients must generally be of 0 or 1 in order to have an immediate application (some families of sparse measurement matrices fulfill that condition however)
• If the multiplexing technology is not accurate enough, any (multiplicative noise) error on one coefficients will result immediately on larger errors.
Pros

• Storage of the measurement matrix is reduced thereby enabling instances of these mixing matrices on some embedded sensor without much design for accessing coefficients of the matrix,
• If the multiplexing technology is accurate enough, there are fewer errors possible on the coefficients (and therefore less multiplicative noise)
• Potentially less measurements
• Some families of sparse measurement matrices have 0/1 coefficients and therefore can have an immediate application
• Measurements are less likely to have clipping issues thereby enabling low dynamic range sensors
• By reducing the number of elements being multiplexed, one keeps the linearity of the function being investigated and keep automated mixing operation to a low count. Let us take the example of the Pooling design ([1][2]), fewer elements being mixed means a smaller likelihood of nonlinearity between reagents and fewer robotic mixing operations

References:
[1] QUAPO : Quantitative Analysis of Pooling in High-Throughput Drug Screening a presentation by Raghu Kainkaryam (a joint work with Anna Gilbert, Paul Shearer and Peter Woolf).