Yesterday, I went to a presentation by Stephane Mallat on one of his most recent work focusing on defining a metric for objects such as images that go through some type of non-rigid deformation. In CS, we have elements of high dimensions that can be compared with the euclidian distance and for which one can apply random projections and expect similar neighborhood as in the original space.
But what happens when two objects of high dimensions are just a transformation of each other ? well not much as we rely on the euclidian distance in either the original space or in the reduced space provided by the random projections.
Mallat's approach is trying to give an answer to the following issue. Can we get a metric that allow objects that are deformation of each other to stay "close". For that he builds a nonlinear function called an invariant so that when the euclidian distance of two invariants of two very similar objects is performed, it is as close to zero as possible. For instance, the best known invariant for translation is the modulus of the Fourier transform Things get sticky when we deal with non uniform translation as all bets are off now with the modulus of the Fourier transform. Mallat's provide his insight and how he builds his invariant function for translation in the following two videos and this presentation:
I wonder how we could build similar invariants for compressed sensing measurements (i,e random projections) or on compressive sensing hardware ? It would seem to be not possible as the reason Mallat uses complex wavelets is due to the need of avoiding singularities of the modulus of the projected functions and projecting a function with random projections only brings out singularities. More on that later.