Monthly Archives: March 2010

I recently read articles on paleomagnetism. It is common to make the assumption of antipodal symmetry for the distribution of the dispersion of the directions. Two such spherical distributions (directional statistics) with such an antipodal symmetry are the Bingham and the Kent distributions. It will be worth writting the jMEF files for those ones.

Frank.

Olivier was kind enough to provide this report trip on the French computational geometry days, as known as JGA 2010. The plenary speaker slides are online and worth a check.

The Journées de Géométrie Algorithmique are the main French-speaking meeting about computational Geometry. It is an informal workshop for the members of the French Computational Geometry community. The 2010 edition hold in Marseille in March 2010.

The meeting was split into two parts: lectures from invited speakers and short talks by meeting participants. We had the great pleasure to listen to 5 high-quality lecturers: Alexander Zvonkin, from University Bordeaux 1, spoke about Belyl functions and combinatorial maps; Claire Mathieu, from Brown University, made a very interesting course about linear programming and semi-definite programming methods; Francis Clarke, from University of Lyon 1, gave a lecture about non-smooth analysis and its applications. Albert Cohen, from University Paris 6, presented some results about theory and algorithms for anisotropic triangulations, with application to images. The lectures session ended with Jonathan R. Shewchuk, from the University of California Berkeley, who spoke on theoretically guaranteed mesh generation, making a survey of the whole literature, from basic Delaunay triangulations to last results on the field.

The talks covered a large variety of Computational Geometry related topics and I will simply give a few words about some talks that appeared particularly interesting to me. Primoz Skraba, from the INRIA Geometrica team in Saclay, described a clustering algorithm using persistent homology which allows, using some stability properties of the persistent diagram, to recover the right number of clusters with good spatial stability. Jean-Daniel Boissonnat, from the Geometrica group in Sophia, presented a certified algorithm for manifold reconstruction which has a linear complexity in the ambient dimension. It uses tangential Delaunay complexes and techniques of sliver removal to achieve this result. Julie Digne, from the CMLA lab of the ENS Cachan, showed a new strategy for segmentation of the meshing of a data point set. Given a scalar function, like the mean curvature, defined on the meshing, it uses a Maximally Stable Extremal Regions method to extract level set on the meshing. Thomas Iwaszko presented his work on a new variant of the Voronoi diagrams: he generalizes the empty-ball property of the classical diagrams to any shape (actually, a union of spheres) and study the resulting diagrams.

The next JGA will be held in 2012, due to the SoGC 2011 conference taking place in France.
Frank.

Tensors are square symmetric positive-definite matrix. They are surprisingly in 1-to-1 mapping with symmetric matrices through matrix exponentiation (exp.log computed on the diagonal elements of the spectral decomposition). I said surprisingly because tensors are symmetric and therefore a proper subset of the set they are in bijection with. Yes, nobody knows what is going on at infinity, and Cantor set theory and life was not so happy due to this… Anyway, obviously symmetric matrices are closed by addition and scalar multiplication, so that it is a vector space. Now using the bjiection tensor-symmetric matrix, we deduce a vector space for tensors. Euclidean distance (or other norm induced distance) hold, and we can transpose that to distances on tensors… These are called log-euclidean metrics, for distance metrics on matrix logarithm. And yes the metric with triangle inequality is derived from Cauchy-Schwarz inner product ineq.

Spaces are beautiful lands to explore!
Frank.

Shannon entropy is said additive in the sense that the entropy of the joint distribution

H(X*Y)

is the sum of the entropies:

H(X*Y) = H(X)+H(Y).

This property is not true for the quadratic entropy (sum of squares). The Java program below checks experimentally those entropy functional properties. Frank.

Here is the Java code

/*
 (C) March 2010, Frank Nielsen
 Demonstrates that Shannon entropy is additive
 and that the quadratic entropy is not
*/
public class ShannonAdditiveEntropy
{
 //quadratic entropy
public static double Q(double [] p)
{
double res=0.0d;
for(int i=0;i < p.length;i++)
    res+= p[i]*p[i];
    
return res;     
}   
 //Shannon entropy
public static double H(double [] p)
{
double res=0.0d;
for(int i=0;i < p.length;i++)
    res+= -p[i]*Math.log(p[i]);
    
return res;     
}   
    
public static void main (String [] args)
{
int n=10,i,j;
double sump=0.0, sumq=0.0;
double [] p=new double[n];
double [] q=new double[n];
double [] pq=new double[n*n];

for(i=0;i < n;i++)
{
p[i]=Math.random(); q[i]=Math.random(); 
sump+=p[i]; sumq+=q[i];
}
// normalize to densities
for(i=0;i < n;i++)
{
    p[i]/=sump;  q[i]/=sumq;
}

for(i=0;i < n;i++)
    for(j=0;j < n;j++)
     pq[i*n+j]=p[i]*q[j];
     
System.out.println("Show that Shannon entropy is an additive entropy:");
System.out.println("H(p)="+H(p)+" H(q)="+H(q)+" H(pq)="+H(pq) );
double delta=H(pq)-H(p)-H(q);
System.out.println("Additive entropy:"+delta);
System.out.println("Show that the quadratic entropy is NOT an additive entropy:");
System.out.println("Q(p)="+Q(p)+" Q(q)="+Q(q)+" H(pq)="+Q(pq) );
double deltaq=Q(pq)-Q(p)-Q(q);
System.out.println("Not an ddditive entropy:"+deltaq);
     
}
    
}

Frank.

How do we visualize relationships in the jungle of (statistical) distances? I tried to give insights at a glance with this poster.

A long time ago, well in 1996, I investigated output-sensitive algorithms. I then designed an algorithm for peeling iteratively the convex hulls of a 2D point set. This yields the notion of depth of a point set, and is a useful index in statistics as attested by recent papers published in this area.

Here is the reference work:
Output-sensitive peeling of convex and maximal layers

The center of mass (=centroid) is defined as the center point minimizing the squared of the Euclidean distances (=variance). If one of the source point is an outlier corrupting your dataset, and if that outlier goes to infinity, then your centroid follows it can is clearly not a robust centerpoint. The median on the contrary is defined as the center point minimising the sum of Euclidean distances. It is robust as it breaks only if n/2 outlier points go to infinity. However, there is no closed form solutions.

Doing some survey, I found that since Fermat (who allegedly first ask the question for 3 points), it has been studied and rediscovered in many communities. The current labeling of this point should be Fermat-Fagnano-Weber-Torricelli-Steiner point, and I forgot many names…

History is full of insights!
Frank.