Bummer, We ain't going to Mars

NASA Selects Proposals for Future Mars Missions and Studies. We are not one of them.

Nothing short of a revolution, part 3 : It does not need to be nonlinear

And then something happened in 1999: Emmanuel Candès and David Donoho noticed that with curvelets, one did not need an adaptive or a nonlinear scheme to converge on images with edges[1]. This is important because as stated before, the only way people were using wavelets and related functions (ridgelets,...) was through a nonlinear scheme, i.e. compute all the wavelet or fourier coefficients first and then do a threshold on them in order keep only the largest ones. While in the wavelet case, i.e. in 1-d, the issue is not really a big deal, it becomes a nightmare when you try to use this type of technique in multidimensional spaces. If you have to compute all the moments of an integral equation and then remove the ones that are too small (because wavelets sparsify certain integral kernel), you have barely made progress over the state of the art like fast multipole methods. So for the first time since the arrival of wavelets, there is hope that there is a linear process by which one can produce a sparse representation of a function or set of data. Ok so now we have a way to get a truely sparse approximation of a function using basis pursuit, we have tons of nice families of functions to do this and we now know that in order to find a sparse representation of a function we don't need a nonlinear scheme, why is this related to compressed sensing ?....

References

[1] Curvelets - a surprisingly effective nonadaptive representation for objects with edges. Curves and Surfaces, L. L. Schumaker et al. (eds), Vanderbilt University Press, Nashville, TN. Compressed Postscript (ps.gz) / (pdf)

Nothing short of a revolution. Part deux: Pursuing a dream

With the wavelet bang came another realization and then something odd happened. In 1994, Donoho and Chen published a paper that summarized the state of the affairs on approximation:

- The realization that now, with wavelets of all kinds being added daily on top of the old approximating polynomials, there are too many functions to be used to decompose a signal and there is no good way in figuring out which one is the best to use. The situation is so bad that you can write an entire dictionnary of different wavelet names.

- Some signals are a composition of various functions and distributions (diracs,...), so it does not make sense to decompose them with respect to only one family of function. If you use only one type of decomposing function, you will not get a sparse decomposition. Take for instance the case of Gibbs phenomenon where one tries to approximate a dirac with a bunch of sines and cosines.

- Most decomposition algorithms are based on a least square approach. In other words, the criterion with which one decides whether a series of approximation has converged in based on a $L_2$ distance or the euclidian distance. The definition of a scalar product is therefore essential but no one knows why some scalar products work better than other. In the end, many formulation of a variety of engineering problems rely on so-called weak formulation such as the finite element method but sometimes, no one knows really why they should be using these methods. Case in point, albeit a non traditional one: Neutron and Radiation Transport. There are many weak formulation of the linear transport equation even though we know that it has distribution as eigenfuctions. Yet neither the scalar product of the weak formulation ($L_2$) nor the one induced by the scalar product of the eigendistribution can constrain any of the solution to be positive (an initial requirement) or have a direct physical meaning.

- If the scalar product is induced by the decomposing family of function, then how can one try to decompose a function simultaneously along different set of functions ?

- The $L_2$ distance criterion never converges toward a local approximation. The approximation will have many coefficients that are very close to each other. There will be no way to apply a blind threshold to these coefficients because each and everyone of them count in the minimization of the criterion.

- The problem that you have always wanted to solve is an $L_0$ problem not an $L_2$. The $L_0$ is the criterion is really about the sparsity of the approximation.

- $L_0$ problem is NP-complete so there is no way you can figure a solution in your lifetime on average.

Donoho and Chen showed that if you were to solve an $L_1$ problem instead of an $L_0$, the solution was likely very close to the $L_1$. Solving an $L_1$ problem is akin to performing linear programming or an optimization. Because of its over reliance on least square approach, the whole engineering field could be shattered as a result. Yet, the method by which one can obtain a solution are significantly time consuming at that time that it was not likely to make a dent in the weak formulation business anytime soon. The lingering thought is still that it will eventually prevail and change our views on how to solve engineering problems in the future. At some point, even Google was using some code word related to the $L_1$ approach to find future employees :-). There needs to be other stepping stones to reach the final climax of this story though.

Nothing short of a revolution. Part I: When a scam can kill you

This story is about the revolution brought about by compressed sensing or compressive sampling. It is a beautiful story as far as I can tell and I will try to parse it in three or four parts. I write it as an outsider and I therefore hope to be forgiven if I missing names.

It all started with the (re)discovery of wavelets by Jean Morlet and the work of people like Alex Grossman. The field was expanded by people like Yves Meyer, Stephane Mallat, Ingrid Daubechies and many others. As pointed out in the text about Jean Morlet, it all started badly:

...Until now, his only reward for years of perseverance and creativity in producing this extraordinary tool was an early retirement from Elf...

Elf was not fearing knowledge or fearing to be more competitive but rather the company had been hit with a scandal that nearly shattered a government and a presidency. The avions renifleurs affair (sniffer planes) made most of the management at ELF very cautious/squeamish about any type of extraordinary scientific announcement. So when Morlet came in and told people about wavelets, they had him retire. While the story is cute, it took a good ten years before wavelets became of interest in the generic engineering literature.

As an engineer myself, the turning point for making these functions useful was when Dave Donoho started to make available a series of routines on the internet so that other researchers could reproduce his own published material (David Donoho wants his research to be reproducible because he thinks that publication is not scholarship but merely an advertisement for it). The Wavelab toolbox was revolutionary because, in effect, since most of these wavelet functions were not analytic (they are mostly defined as a solution to a recurence relation) most engineers had to first build something to get to see a "wavelet" function. And while there were wavelets built from spline functions by Chui, Goswami and Chan these never really took off in the literature. Wavelets are now routinely used in every areas of engineering and have joined Fourier analysis in the series of tools engineers and scientists use in their daily lives. They have changed the face of applied harmonic analysis and change our ways we look at signals such as image, voice, etc. However, the revolution only starts here. The bigger boom came from another area of mathematics...

Reflecting on a moving view

I recently flew on a small shuttle plane between College Station and Houston and wanted to see what the view looked like in a panorama. Stitching several photos together using Autopano Pro, this is what I eventually saw from 4,000 feet. This is a little bit different than say 112,000 feet since the angle to the scence of interest makes it difficult to patch images together. When the camera is close to the land, the movement of the plane changes quite rapidily the angle to the scene and it then becomes difficult for the software to patch images together.

Thought compression - part deux: A python perspective

Since I last wrote about thought compression, the Hutter prize was launched and somebody has already found a way to earn part of that prize. The concept is to find a compression algorithm that compresses a 100 MB from Wikipedia in a lossless fashion to less than 17 MB. 17 MB is the benchmark value for the best "dumb" compressors like zip...The idea is that using relationships between words, one is very likely to be able to compress further a text as opposed to relying on a smart but really dumb way of compressing words of a dictionary based on the frequency use. In the end, the sense is that artificial intelligence can benefit from this because it would permit the "comparison" between statements using distances such as the ones devised by Rudi Cilibrasi.

While compressing text is fine, another area of compression still impresses me. The use of a very expressive programming language that nearly reads like pseudo-code. Python continues on providing examples as to why it falls in this category of expressive languages. For instance, the p2p example was nice but others are similarly intriguing like:

- the pageRank algorithm

- an IRC bot

- a Markov Chain Monte Carlo solver (MCMC solver) or

- Autonomous car programming in the past and in the present.

The MCMC code one is more intriguing than anything else. Because of their ability to compute multidimensional integrals, MCMC methods have allowed the use of Bayesian statistics and Bayesian programming in problems of inferences, a hallmark of artificial intelligence that the Hutter prize is seeking to enable.

Diabetes and Central Nervous System breakthrough

A recent study shows that Diabetes seems to be linked to the nervous system. This is indeed a surprise. However, the most surprising fact is that it was not discovered earlier as it is known that mental illness is linked to diabetes. More specifically, according to several studies dating back fifty years ago we could see the following :

... based on a retrospective review of medical data for 569 randomly selected patients with the two disorders admitted to a state psychiatric hospital between 1940 and 1950—before antipsychotic medications were available-found that metabolic disturbances were significantly greater in those patients than among the general population...

We are slowly getting there

For the past two months, we have been talking to one of the maker of Autopano Pro so that we could process a very large panorama of about 609 images (each of which is 3.2 Mpixels large). The current beta release (version 1.3 RC 3) still has a memory leakage problem for very large panoramas like this one. This monster is about 2 GB large. One of the smaller panorama can be found here. Others can be found here.

Google can save your life

In a recent study, it was shown that good professionals could use Google in problems with hard to figure diagnostics. This is hardly a big discovery to the average person. On the other hand, I know first hand, of somebody who used Google and figured from the first three hits that he was having a big problem that could only be readily remedied by not staying in a high altitude environment and aiming straight for a hospital for treatment.

A C compiler for GPUs

While GPU programming might be fun on its own, the 4 to 5 times increase in speed is not likely to draw a whole slew of people into it. One of the reason may be that if you have to learn a different language, you might as well go straight for an FPGA instead. NVIDIA seems to have figured this out and they just came up with a bridge between the general community and GPU by announcing CUDA a C compiler for GPUs.