Monday Morning Algorithm 9: Implementation of Sparse Measurement Matrices for Compressive Sampling

Ok, so it's not Monday, at least I thought about the algorithm on Monday Morning so there. Last week I mentioned the work of Radu Berinde and Piotr Indyk on Sparse Recovery Using Sparse Random Matrices ( an older version of this paper is here). Since this is a potentially ground breaking work with regards to the hardware implementation of Compressive Sampling, I decided to implement a non-optimized version of the measurement matrix construction of the paper. As usual if you find a mistake please let me know. Also all the codes produced in the Monday Morning Algorithm Series can be found here.

clear
% Algorithm implementing the Sparse Measurement Matrix
% construction of Radu Berinde and Piotr Indyk in
% "Sparse Recovery Using Sparse Random Matrices"
% d is the number of ones per column
% m is the number of rows
% n is the number of columns
% generally m should be much less than n
% n is limited by (m,d) or
% factorial(m)/(factorial(d)*factorial(m-d))
% Written by Igor Carron
d=3
% m rows
m=5;
% n columns
n=10;
% with these parameters it works with n=10
% but it does not work with n greater than 10
A=zeros(m,n);
jj = 0;
for i=1:n
while sum(A(:,i),1)~=d | jj==47
jj=0;
A(:,i)=zeros(m,1);
for j=1:d
A(round((m-1)*rand(1,1))+1,i)=1;
end
v1 = diag(A(:,i))'*ones(m,n);
w = A - v1;
for j=1:i-1
if w(:,j)== zeros(m,1)
jj = 47;
end
end
end
end
% Measurement Matrix is A

Some people might think there is an error in j = 47, they think it is j =42. They are wrong. Also while this is a binary matrix, it can be used with non-binary objects. [ Update: I have made it a function and it is available here. It is working as nicely as the normal measurement matrices on the example set I used it on].

Credit Photo: NASA/JPL/ Space Science Institute, Saturn and Titan on June 9, 2006.

Compressed Sensing: Can we do Source Separation with Compressed Measurements ?

While Blind Source Separation can use sparsity in order to decompose signals in high dimensions, one wonders how this relates to Compressed Sensing /Compressive Sampling. Compressed Sensing is enabled by Sparsity and one then wonders how sampling could take advantage of that and provide the ability to solve the blind source separation problem.

A first step in that direction is taken by Thomas Blumensath and Mike Davies in Compressed Sensing and Source Separation

Separation of underdetermined mixtures is an important problem in signal processing that has attracted a great deal of attention over the years. Prior knowledge is required to solve such problems and one of the most common forms of structure exploited is sparsity. Another central problem in signal processing is sampling. Recently, it has been shown that it is possible to sample well below the Nyquist limit whenever the signal has additional structure. This theory is known as compressed sensing or compressive sampling and a wealth of theoretical insight has been gained for signals that permit a sparse representation. In this paper we point out several similarities between compressed sensing and source separation. We here mainly assume that the mixing system is known, i.e. we do not study blind source separation. With a particular view towards source separation, we extend some of the results in compressed sensing to more general overcomplete sparse representations and study the sensitivity of the solution to errors in the mixing system.

Credit photo: NASA/JPL , Titan's South Pole on December 20th, 2007.

Compressed Sensing: A Method for Large-Scale l1-Regularized Least Squares

An Efficient Method for Compressed Sensing in Proceedings International Conference on Signal Processing
by Seung-Jean Kim, Kwangmoo Koh, Michael Lustig, and Stephen Boyd. The abstract reads

Compressed sensing or compressive sampling (CS) has been receiving a lot of interest as a promising method for signal recovery and sampling. CS problems can be cast as convex problems, and then solved by several standard methods such as interior-point methods, at least for small and medium size problems. In this paper we describe a specialized interior point method for solving CS problems that uses a preconditioned conjugate gradient method to compute the search step. The method can efficiently solve large CS problems, by exploiting fast algorithms for the signal transforms used. The method is demonstrated with a medical resonance imaging (MRI) example.

We talked about l1_ls when it came out. It looks like we have an improvement. The l1_ls package and an explanation of what it does is here: l1_ls.pdf. I think at some point there should be a benchmark on recovery with very large problems with all the different algorithms available. For instance, for the calibration of the random lens imager, we need to solve for very large problems.

Sparsity Based Blind Source Separation

Here is a nice introduction paper to Morphological Diversity using Sparse Constraints. It is entitled Blind Source Separation: the Sparsity Revolution by Jerome Bobin, Jean-Luc Starck, Yassir Moudden, Jalal Fadili. The abstract reads:

Over the last few years, the development of multi-channel sensors motivated interest in methods for the coherent processing of multivariate data. Some specific issues have already been addressed as testified by the wide literature on the so-called blind source separation (BSS) problem. In this context, as clearly emphasized by previous work, it is fundamental that the sources to be retrieved present some quantitatively measurable diversity. Recently, sparsity and morphological diversity have emerged as a novel and effective source of diversity for BSS. We give here some essential insights into the use of sparsity in source separation and we outline the essential role of morphological diversity as being a source of diversity or contrast between the sources. This paper overviews a sparsity-based BSS method coined Generalized Morphological Component Analysis (GMCA) that takes advantages of both morphological diversity and sparsity, using recent sparse overcomplete or redundant signal representations. GMCA is a fast and efficient blind source separation method. In remote sensing applications, the specificity of hyperspectral data should be accounted for. We extend the proposed GMCA framework to deal with hyperspectral data. In a general framework, GMCA provides a basis for multivariate data analysis in the scope of a wide range of classical multivariate data restorate. Numerical results are given in color image denoising and inpainting. Finally, GMCA is applied to the simulated ESA/Planck data. It is shown to give effective astrophysical component separation.

It's funny I did not see a reference to Non-Negative Matrix Factorization and especially its sparse implementation which seems to be a very close subject. I wonder if they yield similar results. The GMCA webpage is here with attendant Matlab code.

Compressed Sensing: Sparse Measurement Matrices

Radu Berinde and Piotr Indyk just released Sparse Recovery Using Sparse Random Matrices ( a newer version of this paper is at MIT-CSAIL-TR-2008-001 while an implementation of these matrices is here). The abstract reads:

We consider the approximate sparse recovery problem, where the goal is to (approximately) recover a high-dimensional vector x from its lower-dimensional sketch Ax. A popular way of performing this recovery is by finding x# such that Ax = Ax#, and |x#|_1 is minimal. It is known that this approach “works” if A is a random dense matrix, chosen from a proper distribution. In this paper, we investigate this procedure for the case where A is binary and very sparse. We show that, both in theory and in practice, sparse matrices are essentially as “good” as the dense ones. At the same time, sparse binary matrices provide additional benefits, such as reduced encoding and decoding time.

Wow. Simple sparse measurement matrices, I know a few people who are going to be happy.

Compressed Sensing: Would Hierarchical Compressed Sensing Make Sense ?

Recently, I mentioned a connection between compressed sensing and the visual cortex through a model that uses random projections and the work of Ali Rahimi and Benjamin Recht on Random Features as an Alternative to the Kernel Trick. Thomas Serre responded with the following:

Yes I have tried simple linear classifiers (eg LDA or Least Square Regularization, Nearest neighbor, etc) and they do work well (pretty much as well as SVM, especially with more training data).....Let me bring one point though. I do not think the "random projection" aspect of our approach is what makes it work well. What is really key in the architecture is the ideas of invariance and hierarchy, both of which are absent from the random projection literature.

They are absent for the moment, but time will come. For instance, the current work by Marco Duarte, Mark Davenport, Michael Wakin, Jason Laska, Dharmpal Takhar, Kevin Kelly, and Richard Baraniuk in Multiscale random projections for compressive classification provides a similar decomposition to the primary visual cortex at several scales. As Marco Duarte points out in the comment section:

This is to say that the random measurements are obtained at different resolutions to get the projections of the different regularizations of the target image.

And while traditionally shift invariance is provided by going in the Fourier domain as in Shift-invariant sparse coding for audio classification by Roger Grosse, Rajat Raina, Helen Kwong, and Andrew Ng, Thomas Serre's model of the primary visual cortex provides a similar robustness to shift/scale/rotation invariance through the use of a hierarchical model. The only hierarchical model I know of in Compressed Sensing is the one using the now infamous random filters as described by Joel Tropp, Michael Wakin, Marco Duarte, Dror Baron, and Richard Baraniuk in Random Filters For Compressive Sampling And Reconstruction.I have not seen any follow-up of that fascinating work but the results seem promising yet they remain in 1-D. In light of all this, it begs the question: Would hierarchical compressed sensing make sense ?


Photo credit: NASA JPL, 2007 WD5 will not hit Mars on Jan 30, it's a shame.

Human Cognition and Biological Regulation of the Neural Network: Advances in X-fragile Syndrome and Alzheimer and a Machine Learning Contest

Wow.

Some people don't realize it but as we stand, we currently do not understand why people with Down Syndrome have lower cognitive ability. Talk about something important, we can detect if an embryo has this condition, but we don't know why they will on average have a lower than average cognitive ability. Similarly, in the X-fragile syndrome, that is linked to Autism, we also don't know why people have lower cognitive abilities. This seems to change according to some new findings by Kimberly Huber and her team :

Dr. Huber previously co-discovered that mice genetically engineered to lack Fmr1 have a defective signaling system in the brain that controls learning in the hippocampus. This system relies on a chemical messenger called glutamate, which under normal circumstances causes nerve cells to make proteins and change their electrical firing patterns in response to learning situations. Without a properly working Fmr1 gene, the glutamate signaling system malfunctions. In 2007 she and colleagues at UT Southwestern found that acetylcholine, another specific signaling chemical, affects the same protein-making factory that glutamate does....

“We suggest that treatment that affects the acetylcholine system might be a supplement or alternative to drugs targeting the glutamate pathway,” Dr. Huber said.

In the current study, she and postdoctoral researcher Dr. Jennifer Ronesi investigated a protein, called Homer, which serves as a kind of structural support for the glutamate system. The Homer–glutamate support system is disconnected in Fragile X syndrome. Dr. Huber’s group discovered that this disconnection results in an inability of brain cells to make the new proteins important for learning and memory.

So while BERT and ERNI seem to be important in controlling brain development, Homer is central to enabling the learning process, who knew ? :-) In light of this finding, I hope that at some point we get a consistent story on why statins seem to be doing a great job for recovering cognitive abilities. In some unrelated story, a

new study documents a dramatic and unprecedented therapeutic effect in an Alzheimer’s patient: improvement within minutes following delivery of perispinal etanercept, which is etanercept given by injection in the spine. injection of perispinal etanercept, which is etanercept given by injection in the spine.

If you think you have a good machine learning scheme, you might want to try it out on the Neuron Modeling Challenge organized by EPFL. The deadline is beginning of February and they give out cash rewards, something like 10 000 swiss francs, or about 6091 euros and like a million dollars these days :-)

Photo Credits: Wikipedia.

Compressed Sensing: On-Line Structural Damage Detection

I nearly missed that one:
Julien Cortial, Charbel Farhat, Leonidas Guibas and Manjunath Rajashekhar examined a way for comparing sensor data and computational models on the spot in Compressed Sensing and Time-Parallel Reduced-Order Modeling for Structural Health Monitoring using a DDDAS.

The abstract reads:

This paper discusses recent progress achieved in two areas related to the development of a Dynamic Data Driven Applications System (DDDAS) for structural and material health monitoring and critical event prediction. The first area concerns the development and demonstration of a sensor data compression algorithm and its application to the detection of structural damage. The second area concerns the prediction in near real-time of the transient dynamics of a structural system using a nonlinear reduced-order model and a time-parallel ODE (Ordinary Differential Equation) solver.

This is an interesting match between computational simulations, actual data and sensor network. As reported in the paper, the main issue is really that too many sensors would weigh too much for the plane example. While incipient fault detection is a subject of considerable interest and while it seems that this technique can detect it with less data than the full set, the compressed sensing step still requires the full set of data to be collected and the reconstruction step would take a looong time compared to the dynamics of the plane and may not be an optimal choice of strategy in this case. The hole in that wing reminded me of another one.

France: Efficacite des transferts de technologie ?

[Today I am going to post in French on an issue of technology transfer in France that I feel is not working well.]

On parle souvent de compétitivité de l'industrie francaise mais rarement du transfert de connaissance de la recherche a l'industrie. Il semble que ce transfert soit moins qu'optimal pour etre gentil. Je pensais faire un post long, mais non, donc voila:

Quelque chose m'embete et je ne comprends pas. Albert Fert, prix Nobel 2007 est a l'origine de la découverte de la Magnétorésistance géante en 1988 qui a ouvert la voie aux disques durs a grande capacité. Comment cela fait il qu'aucune entreprise francaise ne soit leader dans la confection de disques durs ? Je comprends que dans certains pays on puisse produire certains produits a bas prix mais la raison intrinseque de l'existence de brevet est de pouvoir protéger l'inventeur pendant quelque temps de facon a faire evoluer une découverte ou une idée en un produit. Comment cela se fait-il que personne en France n'ait essayé de prendre avantage de cette découverte ?

Peut-on et doit-on rapprocher cette question a une autre question: La disparition de chercheurs aventureux au sein de l'industrie francaise ? Je ne sais pas.

A not so good translation of this entry can be found here.

Graph source : Wikipedia

Compressed Sensing: Near-ideal model selection by L1 minimization, Machine Learning: Sparse coding, Search and Rescue: InternetSAR

Emmanuel Candes and Yaniv Plan just released this preprint on Near-ideal model selection by L1 minimization. The abstract reads:

We consider the fundamental problem of estimating the mean of a vector y = X \beta + z where X is an n x p design matrix in which one can have far more variables than observations and z is a stochastic error term|the so-called `p higher than n' setup. When \beta is sparse, or more generally, when there is a sparse subset of covariates providing a close approximation to the unknown mean vector, we ask whether or not it is possible to accurately estimate X \beta using a computationally tractable algorithm. We show that in a surprisingly wide range of situations, the lasso happens to nearly select the best subset of variables. Quantitatively speaking, we prove that solving a simple quadratic program achieves a squared error within a logarithmic factor of the ideal mean squared error one would achieve with an oracle supplying perfect information about which variables should be included in the model and which variables should not. Interestingly, our results describe the average performance of the lasso; that is, the performance one can expect in an overwhelming majority of cases where X\beta is a sparse or nearly sparse superposition of variables, but not in all cases. Our results are nonasymptotic and widely applicable since they simply require that pairs of predictor variables be not overly collinear.

The main contribution of the paper is to show that the Lasso works under some conditions and bound on the sparsity level of the signal 'that is, for generic signals, the sparsity can grow almost linearly with the sample size. '

On a unrelated note Lieven Vandenberghe and Joachim Dahl just released version 0.9.2 of CVXOPT: A Python Package for Convex Optimization. An interesting aspect of it is the linking possibilities to OpenOffice spreadsheets.

In the sparse coding world, these three papers got my attention: Shift-invariant sparse coding for audio classification by Roger Grosse, Rajat Raina, Helen Kwong, and Andrew Y. Ng, Self-taught learning: Transfer learning from unlabeled data by Rajat Raina, Alexis Battle, Honglak Lee, Benjamin Packer and Andrew Y. Ng. and Efficient sparse coding algorithms by Honglak Lee, Alexis Battle, Rajat Raina, and Andrew Y. Ng. I'll have to implement some of these in my Monday Morning Algorithm series at some point.

This past year saw some new search and rescue operations that used the knowledge of people through the internet. Somebody involved in the latest search for Steve Fowsett has decided to centralize this type of activity on one site: InternetSAR. An interview with the creator of the site can is here, thanks to a podcast by the folks at AVweb. I blogged several entries on Jim Gray's search and I think that it actually goes beyond having human watching and interpreting satellite photos as I have pointed out before, but this is a good and noteworthy effort in the right direction.

Credit photo: Armagh Observatory, Map of asteroids in the inner part of the Solar System.