CS: Replica Method for Sparse Representation of White Gaussian Noise slides, Spherical polar Fourier EAP and ODF reconstruction Via Compressed Sensing in Diffusion MRI and a studentship

Ori Shental just sent me his presentation slides for the paper that got me started in this study of the "compressibility" of the realization fo gaussian noise, The presentation's title is Replica Method for Sparse Representation of White Gaussian Noise with Application to Noisy Compressed Sensing.

here is a new paper that showed up on my radar screen: Spherical polar Fourier EAP and ODF reconstruction Via Compressed Sensing in Diffusion MRI by Sylvain Merlet, Jian Cheng, Aurobrata Ghosh and Rachid Deriche. The abstract reads:

In diffusion magnetic resonance imaging (dMRI), the Ensemble Average Propagator (EAP), also known as the propagator, describes completely the water molecule diffusion in the brain white matter without any prior knowledge about the tissue shape. In this paper, we describe a new and efficient method to accurately reconstruct the EAP in terms of the Spherical Polar Fourier (SPF) basis from very few diffusion weighted magnetic resonance images (DW-MRI). This approach nicely exploits the duality between SPF and a closely related basis in which one can respectively represent the EAP and the diffusion signal using the same coefficients, and efficiently combines it to the recent acquisition and reconstruction technique called Compressed Sensing (CS). Our work provides an efficient analytical solution to estimate, from few measurements, the diffusion propagator at any radius. We also provide a new analytical solution to extract an important feature characterising the tissue microstructure: the Orientation Distribution Function (ODF). We illustrate and prove the effectiveness of our method in reconstructing the propagator and the ODF on both noisy multiple q-shell synthetic and phantom data.

and here is an abstract: Predicting Catastrophes in Nonlinear Dynamical Systems by Compressive Sensing by Wen-Xu Wang, Rui Yang, Ying-Cheng Lai, Vassilios Kovanis, and Celso Grebogi. The abstract reads:

An extremely challenging problem of significant interest is to predict catastrophes in advance of their occurrences. We present a general approach to predicting catastrophes in nonlinear dynamical systems under the assumption that the system equations are completely unknown and only time series reflecting the evolution of the dynamical variables of the system are available. Our idea is to expand the vector field or map of the underlying system into a suitable function series and then to use the compressive-sensing technique to accurately estimate the various terms in the expansion. Examples using paradigmatic chaotic systems are provided to demonstrate our idea.

Finally, here is s PhD studentship with Toshiba and University of Bristol:

DHPA PhD Vacancy Compressive Sensing

Industrial DHPA PhD Studentship Vacancy

An Industrial PhD Studentship funded by the ESPRC through the 2011 Dorothy Hodgkin Postgraduate Award Scheme (DHPA) is available in the Centre for Communications Research (CCR) at the University of Bristol in collaboration with Toshiba Research Europe Ltd (TREL).

The project is entitled “Compressive sensing for M2M applications including healthcare and smart energy”. Compressive sensing is the exploitation of certain characteristics of a signal such that less sampled data (less than Nyquist rate) can be used to reconstruct the signal. In the context of this proposal, compressive sensing is especially useful in reducing the required amount of sensor data to be acquired, such that these can be wirelessly transmitted at a low rate. As the data cannot be reconstructed in the normal way, it will also provide a means of protecting the privacy of the user. In this project, the student will look at ways of designing compressive sensing algorithm to exploit sparsity in M2M data such as biomedical signals or smart energy sensor data. However, the design will have to take special care such that irregularity in the signals which could be vital, will not be lost in the sensing process. Additionally, the student will look at algorithms to best reconstruct the compressed data.

In a nutshell, the project considers the following problems:

• Compressive sensing of M2M sensor data to achieve low rate sampling while capturing all vital irregularities in the signals,

• Design compressive sensing algorithms which are able to protect M2M sensor data from eavesdroppers or wireless sniffers,

• Optimising the reconstruction of compressed M2M data to remove noise and recover the original signal,

• Study implications of applying compressed sensing in a practical M2M environment such as healthcare and smart energy networks.

During the PhD programme, the student may undertake a placement at TREL’s Telecommunications Research Laboratory based in Bristol; while the student would benefit from the interactions with industrial researchers as well as the experience of working in an industrial laboratory, this is not mandated and is open to discussion.

This studentship is available from October 2011 for a period of up to 4 years and is funded jointly by the EPSRC through the 2011 Dorothy Hodgkin Postgraduate Award Scheme (DHPA) and by Toshiba Research Europe Ltd. The award provides an annual stipend ca. £13,590 per annum plus an enhancement of £1,430 per annum and full payment of Overseas Tuition Fees. Due to funding restrictions this studentship is only open to students from the countries listed at the OECD website - http://www.oecd.org/dataoecd/62/48/41655745.pdf - plus Russia and Hong Kong.

We are seeking students with equivalent of a UK first class honours degree, from a reputable academic institution. We welcome candidates who have strong backgrounds in one of the following areas: electronics and electrical engineering, computer science, applied mathematics, system control, or related disciplines

The project will be supervised by Dr. Rob Piechocki of CCR, and Drs Woon Hau Chin and Zhong Fan at Toshiba Research Europe Ltd. Further details of the CCR’s work are at: www.bristol.ac.uk/ccr.

Further details of the studentship can be found at: 

http://www.rcuk.ac.uk/ResearchCareers/dhpa

Please e-mail your application to 

http://www.bristol.ac.uk/prospectus/postgraduate/2011/intro/apply.html and use this same address if you have questions or would like to have an informal discussion about the post and the research project.

The start date is as soon as possible after the 1 October 2011 and no later than 1 October 2012. This studentship is open until filled.

CS: Follow-up on "Compressible" Realization of Gaussian Noise

Emmanuel Candes just sent me the following:

Hi Igor,

I looked at your post today and it seems to me that you are learning about statistics of ordered independent normals :)

I suggest a simpler experiment. Take a long Gaussian vector with mean zero and variance 1 and assume that your dictionary is the identity. The best sparse approximation simply keeps the largest entries. Now in the spirit of your simulations, set a threshold at 0.25, say. That is, discard all the entries with magnitude less than 0.25. Since P(|Z| \lt 0.25) ~ 0.2, you will discard about 20% of the entries. You can also calculate the relative MSE, the average relative squared error. This will be about 4 10^-3.

Now as N increases in your experiment, it is no surprise that things ``get better''. In the limit where N is infinity, every vector will be 1-sparse in your dictionary. In fact as N gets exponentially large in the dimension, they will all be nearly 1-sparse.

Emmanuel

Thanks Emmanuel.

I agree with Emmanuel that asymptotically, as N grows, we have a ideal Lena problem, you know the one where one has a dictionary with an element being a full Lena. While the example of the identity dictionary is self explanatory, I am still somehow surprised at the 30 percent drop for a 1 percent accuracy shown in the previous entries. I note that this drop varies and is dependent on the solver being used. The previous entry showed the encouraging results for SL0. Here are less encouraging results for the Basis Pursuit/SPGL1.

recall that ideally, we are aiming for a figure like this one (caveat in the article, the values of N, m and k are infinite but the ratio kappa and alpha are constant).

And so the question that is interesting to consider is: given m say 250, are there solvers that can do better than SL0 for a 1 percent accuracy ? Let us recall what that figure showed for that solver:

CS: "Compressible" Realization of Gaussian Noise

I just improved the script I wrote earlier so that it would:

• produce graphs with labels
• provide a second map that features the variables used by Ori Shental in his paper

Instead of SL0, I have tried the simple basis pursuit of SPGL1 and it doesn't work, i.e. I cannot find a "compressible decomposition" of the realization of a Gaussian vector. I have not tried any other L_1 solvers (including LASSO or Dantzig Selector...) so there are ample experiments to perform here. I was also told that m might be too small and what was observed was a fluke. So instead of m = 50, I went for m =250, the effect is larger. Here are the figures for SL0:

Here is the attendant script. I used the new variable kappa = k/N and alpha = m/N. Let me summarize what the first figure says:

Given a Gaussian vector of size 250, a Gaussian dictionary made up of 2500 Gaussian realization will on average provide a decomposition of said vector with as few as 148 elements of the dictionary with a 1% error.

One can note that the second figure shows a relatively small region of interest compared to the one found by Ori in his paper. Is it a question of using a different solver ? and if so which one ? Otherwise I have also noticed that it may be dependent on m but my small computer cannot handle this. To check if this is the case, one could modify the code from

m =250;
itr = 10;
for N = m:100:2500

with

m =1000;
itr = 10;
for N = m:500:10000

CS: A Gaussian Experiment for the Week-End.

Besides reading the ArXiv batch of the week, some of y'all might be interested in digging this one further over the week-end. It started because I was intrigued by what Ori Shental stated earlier and so I went ahead and tried a small experiment. Given a Gaussian vector of size m x 1, a Gaussian dictionary of size m x N, how sparse is this Gaussian vector as a function of the elements of the dictionary ? Can I get a sparse decomposition of this Gaussian noise realization with respect to the elements of the dictionary ?

In short, we are solving for x, with y = A x, where y is the known Gaussian vector et A the dictionary. In order to investigate this, I wrote a small script that uses SL0 solver and here it is for m =50 and N varying from 1 to 600.  This is an attempt at seeing something, much like what pirates do. Obviously there are issues with the script such as for instance my criterion of 0.01, but here it is:

clear
            sigma_min = 0.00004;
            sdf=0.95;
m =50;
itr = 10;
for N = 1:600
sta(N)=0;
    for ii=1:itr;
    y = randn(m,1);
    A = randn(m,N);
    x = SL0(A, y, sigma_min,sdf);
    xsol = gt(abs(x),0.01);
    spars = sum(xsol);
    sta(N) = sta(N)+spars;
    end
    sta(N) = sta(N)/itr;
end
plot(sta)

and this is what we get running this script:

One can see rather quickly that a 50 elements Gaussian vector can be decomposed on average with 40 elements of a 100 elements dictionary. That number goes down to 35 with 300 elements or a sparsity fraction of 0.7 ! Intuitively, we are expecting that fraction to be 1, i.e. the realization of that vector to be full.

What can be improved in this script ?

CS: A precision by Ori Shental

On top what I just said in the previous entry, Ori Shental kindly added:

This work doesn't contradict in any way the well-known fact that WGN is non-compressible. In this work we discuss sparse representation of noise *realizations* given certain dictionary *realizations*. Still the indices of the non-zero entries of the sparse representation of WGN will differ from one WGN instance to another such that in order to describe the ensemble of *all* WGN realizations one would need at least as the length of the observed WGN vector (i.e. k>=m). So no real compression here, just sparse representation of noise realizations. Thus saying the noise is "compressible" (in quotation marks) is in place.

On the second part of the paper, we use this observed "compressibility" of WGN to translate the noisy CS/channel problem to a noiseless one with denser effective input, allowing us to derive some new results on the former based on already known results about the latter. Still, I share your feeling that there are a lot of other applications to this (e.g. multiplicative noise channel as you say, etc.). Another interesting task down the road is to repeat this analysis under the practical L1-norm constraint, rather than the theoretical L0-norm.

Thanks Ori

CS: Did you realize Gaussian noise could be sparse given a Gaussian dictionary ?

Well,it looks like this is the case as Ori Shental uses this fact in the following paper.

Sparse Representation of White Gaussian Noise with Application to l_0-Norm Decoding in Noisy Compressed Sensing by Ori Shental. The abstract reads:

The achievable and converse regions for sparse representation of white Gaussian noise based on an overcomplete dictionary are derived in the limit of large systems. Furthermore, the marginal distribution of such sparse representations is also inferred. The results are obtained via the Replica method which stems from statistical mechanics. A direct outcome of these results is the introduction of sharp threshold for l_0-norm decoding in noisy compressed sensing, and its mean-square error for underdetermined Gaussian vector channels.

I need to think some more about this paper as this idea of noise being "compressible" must have some other implications in the multiplicative noise case....Thanks Ori for the heads-up.