CS: Question about CS and MPI and RFIDs, Matrix Completion, CS in Traffic, Generalizations of the Linearized Bregman Method

On the LinkedIn Compressive Sensing Group discussion, two members asked questions on the potential use of CS in their fields, if you have any ideas you may want to share your knowledge with them. Just for kicks, the group now has 167 members. While we are on te subject of stats, if you check on the right hand side of this site, you'll notice that 517 people are receiving this entry either through their feedreaders or by e-mail, this number doesn't include the people coming to the site directly! But let us come back to the two discussions on the LinkedIn group:

David Skinner asked the interesting question:

Looking for compressive sensing applications to parallel computing

I am interested in the application of new techniques in compressive sensing to produce synopses of communication traces in parallel computing codes. If you know of software or existing research that could aid in generating compact summaries of traces and profiles of MPI based applications I would be glad to hear about them and discuss their use. I have found work on trace compression using these techniques, but they treat each information stream serially. There is an opportunity to compress information across MPI tasks as well (many tasks have similar traces) but have not found prior work in this area.

For what it's worth, David is behind the Integrated Performance Monitoring utility from which the graph above is extracted. The discussion is here. It looks to me that the work in heavy hitters/sketching might seem relevant.

Leon Palafox has this other question :

Compressive Sensing in Accelerometer and RFID Network

I am looking into Compressive Sensing for a solution of a sensor network in order to reduce the sampling rate input of each sensor that by this moment is too high.

The discussion is here. Clearly this is an issue that comes back often, we talked about this in this entry and a recent paper also tried to paint a clear picture of the issues in Sparse Event Detection in Wireless Sensor Networks using Compressive Sensing by Jia Meng, Husheng Li, and Zhu Han,

In the comment section of this entry, Andrea Montanari mentioned that:

...we [Raghunandan Keshavan, Andrea Montanari, and Sewoong Oh ] made available a C version of the matrix completion algorithm, at the same URL: http://www.stanford.edu/~raghuram/recon/index.html

It is pretty fast...

Rahul Garg also let me know that he and Rohit Khandekar will soon post an implementation of GraDes featured in Gradient Descent with Sparsification: An iterative algorithm for sparse recovery with restricted isometry property.

The ever interesting blog on compressed sensing (in Chinese) by Lianlin Li featured the following interesting application of Compressive Sensing:

Traffic Monitoring by David Johnson (entry is here on Lianlin Li's blog)

Lilian Li also noted this interesting paper (translation of his post is here) :

Optimal PSF modeling for weak lensing : complexity and sparsity by Stephane Paulin-Henriksson, A. Refregier, Adam Amara. The abstract reads:

Context. We address the issue of controling the systematic errors in shape measurements for weak gravitational lensing. Aims. We make a step to quantify the impact of systematic errors in modeling the point spread function (PSF) of observations, on the determination of cosmological parameters from cosmic shear. Methods. We explore the impact of PSF fitting errors on cosmic shear measurements using the concepts of complexity and sparsity. Complexity, introduced in a previous paper, characterizes the number of degrees of freedom of the PSF. For instance, fitting an underlying PSF with a model of low complexity produces small statistical errors on the model parameters, although these parameters could be affected by large biases. Alternatively, fitting a large number of parameters (i.e. a high complexity) tends to reduce biases at the expense of increasing the statistical errors. We attempt to find a trade-off between scatters and biases by studying the mean squared error of a PSF model. We also characterize the model sparsity, which describes how efficiently the model is able to represent the underlying PSF using a limited number of free parameters. We present the general case and give an illustration for a realistic example of a PSF modeled by a shapelet basis set. Results. We derive a relation between the complexity and the sparsity of the PSF model, the signal-to-noise ratio of stars and the systematic errors in the cosmological parameters. By insisting that the systematic errors are below the statistical uncertainties, we derive a relation between the number of stars required to calibrate the PSF and the sparsity of the PSF model. We discuss the impact of our results for current and future cosmic shear surveys. In the typical case where the sparsity can be represented by a power-law function of the complexity, we demonstrate that current ground-based surveys can calibrate the PSF with few stars, while future surveys will require hard constraints on the sparsity in order to calibrate the PSF with 50 stars.

We seem to come back often to this issue of calibrating PSFs with few images/targetd :-). Let us hope the blog doesn't go down for maintenance today.

And finally, we have : Analysis and Generalizations of the Linearized Bregman Method by Wotao Yin. The abstract reads:

This paper reviews the Bregman methods, analyzes the linearized Bregman method, and proposes fast generalization of the latter for solving the basis pursuit and related problems. The analysis shows that the linearized Bregman method has the exact penalty property, namely, it converges to an exact solution of the basis pursuit problem if and only if its regularization parameter $\alpha$ is greater than a certain value. The analysis is based on showing that the linearized Bregman algorithm is equivalent to gradient descent applied to a certain dual formulation. This result motivates generalizations of the algorithm enabling the use of gradient-based optimization techniques such as line search, Barzilai-Borwein steps, L-BFGS, and nonlinear conjugate gradient steps. In addition, the paper discusses the selection and update of $\alpha$. The analysis and discussions are limited to the l1-norm but can be extended to other l1-like functions.