Compressed Sensing: Random Thought on a Low Dimensional Embedding

One of these days I am going to have to talk about the Experimental Probabilistic Hypersurface (EPH) that Bernard Beauzamy and Olga Zeydina have been developing. One of the interesting feature of this construction is the ability to answer one of the engineers most potent problem: Given a set of experimental points dependent on a series of parameters, how do you figure if you know your phase space ? In other words, how is the knowledge acquired over time bring about some expertise about a certain area of engineering. One example case I have witnessed is Computational Fluid Dynamics (CFD): When you have a code that takes a non trivial amount of time to converge and the CFD code depends on many different parameters (friction factors for some type of turbulence model, fluid properties,...), how do you figure if you really understand your problem after having run three, ten, one hundred cases ?

The EPH approach is about building a multidimensional probability distribution based on the Maximum Entropy principle. In other words, EPH reproduce what you know about a problem but not more. It can also be used as some sort of storage device. Recently, some constructive comments were made in order to strengthen its applicability[1]. This is very interesting as I think it should be taught to any third year engineering students. I have been involved with the Robust Mathematical Modeling program set up by Bernard but mostly as a spectator so far. Initially, one of the issues I wanted to deal with was, whether there were similar techniques in the published literature. I have not found too many, at least none that were that expressive. The post by Masanao Yajima on Overview of missing data led Aleks Jakulin to kindly provide the beginning of an answer.

The other issue that should be raised is the issue of distance in the parameter space. Right now, one uses L2 but there is no good rationale for this especially when you deal with, say, an already dimensionless Reynolds Number and a Froude Number: i.e. even if you normalize them, how can one be comfortable with the metric distance used. A good solution to this issue is to import expert's knowledge through the redefinition of the norm. An example of that can found in the booming Machine Learning field ( Improving Embeddings by Flexible Exploitation of Side Information) As it turns out, some of these methods use Convex Optimization in order to produce a good distance function. In the paper on Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization by Benjamin Recht, Maryam Fazel, Pablo A. Parrilo, the building of a distance matrix was one of the few example showing the parallel between Compressed Sensing and the heuristics of the nuclear norm minimization. In the example of the nuclear norm minimization case, some element of the distance matrix are known while others are not. The nuclear norm minimization allows one to find the lowest rank approximation to this distance matrix given the known distance elements. The use of the Restricted Isometric Property from the paper [2] allows one to make some statement on the result of the nuclear norm minimization. More specifically from [2]:

Low-dimensional Euclidean embedding problems
A problem that arises in a variety of fields is the determination of configurations of points in low-dimensional Euclidean spaces, subject to some given distance information. In Multi-Dimensional Scaling (MDS), such problems occur in extracting the underlying geometric structure of distance data. In psychometrics, the information about inter-point distances is usually gathered through a set of experiments where subjects are asked to make quantitative (in metric MDS) or qualitative (in non-metric MDS) comparisons of objects. In computational chemistry, they come up in inferring the three-dimensional structure of a molecule (molecular conformation) from information about interatomic distances ....However, in many cases, only a random sampling collection of the distances are available. The problem of finding a valid EDM consistent with the known inter-point distances and with the smallest embedding dimension can be expressed as the rank optimization problem...

In other words, would the RIP-like condition impose a choice on the parameters to be chosen representative of a certain expert's knowledge in the EPH framework ?


Reference:
[1] Comments made by S. Destercke, IRSN, following Olga Zeydina's presentation at IRSN/Cadarache, July 2007, and answers by SCM (August 2007).
[2] Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization, Benjamin Recht, Maryam Fazel, Pablo A. Parrilo