Diffusion maps and wavelets
I just took a look at the latest issue of the Applied and Computational Harmonic Analysis Journal, and was surprised to see a seemingly out of place emphasis on Markov kernels. This month’s release is a special issue focusing on diffusion maps and diffusion wavelets, new research directions which hold promise for dimensional reduction, pattern recognition, and general dealing with high dimensional data. I couldn’t get any further than the first pages of the first paper, but the ideas sound genuinely new, exciting, and above all useful. The ingenious idea that seems to be at the heart of these methods is to represent your data using a symmetric graph structure with a symmetric, positive weighting kernel 
which encodes the affinity of your data points. Then you can associated a Markov kernel 
with a random walk on this graph, where 
and 
. Then encodes information on the local geometry of the graph, and this information can be ‘diffused’ by taking successive powers of : the authors point out this can be viewed as an analog of the process of integrating a differential equation to obtain global information from local information. Analysis of the eigenfunctions and values of this kernel gives you useful information on your data. As an example of the power of this methodology, consider the interpretation of clustering on a graph in the context of a random walk: a cluster is a region which the walk leaves with low probability. So if we use 
to determine the subgraphs of our data sets which can be considered clusters, increasing 
gives us larger(?) clusters. This seems like a generalization of the concept of MRAs.
Sweet stuff. See http://www.math.yale.edu/~sl349/tutorials/diffusion/diffusion_top.html for an online synopsis of the article.
Possibly relevant posts:
- The future is now! (2/26/2007)
- Self-avoiding walks (3/8/2005)
- spectral graph theory and two CS applications (5/4/2008)