×

Diffusion maps. (English) Zbl 1095.68094

Summary: We provide a framework based upon diffusion processes for finding meaningful geometric descriptions of data sets. We show that eigenfunctions of Markov matrices can be used to construct coordinates called diffusion maps that generate efficient representations of complex geometric structures. The associated family of diffusion distances, obtained by iterating the Markov matrix, defines multiscale geometries that prove to be useful in the context of data parametrization and dimensionality reduction. The proposed framework relates the spectral properties of Markov processes to their geometric counterparts and it unifies ideas arising in a variety of contexts such as machine learning, spectral graph theory and eigenmap methods.

MSC:

68T05 Learning and adaptive systems in artificial intelligence
68T30 Knowledge representation
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Hoff, P. D.; Raftery, A. E.; Handcock, M. S., Latent space approaches to social networks analysis, J. Amer. Statist. Assoc., 97, 1090-1098 (2002) · Zbl 1041.62098
[2] Szummer, M.; Jaakkola, T., Partially labeled classification with Markov random walks, Neural Inf. Process. System, 14, 945-952 (2001)
[3] F. Chung, Spectral Graph Theory, in: CBNS-AMS, vol. 92, Amer. Math. Soc., Providence, RI; F. Chung, Spectral Graph Theory, in: CBNS-AMS, vol. 92, Amer. Math. Soc., Providence, RI · Zbl 0867.05046
[4] J. Shi, J. Malik, Normalized cuts and image segmentation, in: Proc. IEEE Conf. CVPR, 1997, pp. 731-737; J. Shi, J. Malik, Normalized cuts and image segmentation, in: Proc. IEEE Conf. CVPR, 1997, pp. 731-737
[5] Brin, S.; Page, L., The anatomy of a large-scale hypertextual web search engine, Computer Networks and ISDN Systems, 30, 1-7, 107-117 (1998)
[6] L. Page, S. Brin, R. Motwani, T. Winograd, The PageRank citation ranking: Bringing order to the web, Technical report, Stanford University, 1998; L. Page, S. Brin, R. Motwani, T. Winograd, The PageRank citation ranking: Bringing order to the web, Technical report, Stanford University, 1998
[7] White, S.; Smyth, P., Algorithms for estimating relative importance in networks, (Proc. 9th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining (2003), ACM Press), 266-275
[8] Haveliwala, T., Topic-sensitive PageRank: A context-sensitive ranking algorithm for web search, IEEE Trans. Knowl. Data Eng., 15, 4, 784-796 (2003)
[9] Kleinberg, J., Authoritative sources in a hyperlinked environment, J. ACM, 46, 5, 604-632 (1999) · Zbl 1065.68660
[10] R. Lempel, S. Moran, The stochastic approach for link-structure analysis (SALSA) and the TKC effect, in: Proc. 9th Int. World Wide Web Conf., 2000, pp. 387-401; R. Lempel, S. Moran, The stochastic approach for link-structure analysis (SALSA) and the TKC effect, in: Proc. 9th Int. World Wide Web Conf., 2000, pp. 387-401
[11] Belkin, M.; Niyogi, P., Laplacian eigenmaps for dimensionality reduction and data representation, Neural Comput., 13, 1373-1397 (2003) · Zbl 1085.68119
[12] M. Belkin, Problems of learning on manifolds, Ph.D. dissertation, August 2003; M. Belkin, Problems of learning on manifolds, Ph.D. dissertation, August 2003
[13] Kac, M., Can one hear the shape of a drum? Part II, Amer. Math. Monthly, 73, 4, 1-23 (1966) · Zbl 0139.05603
[14] A. Nahmod, Geometry of operators and spectral analysis, Ph.D. dissertation, Yale University, October 1991; A. Nahmod, Geometry of operators and spectral analysis, Ph.D. dissertation, Yale University, October 1991 · Zbl 0739.47003
[15] Safarov, Y.; Vassiliev, D., The Asymptotic Distribution of Eigenvalues of Partial Differential Operators (1996), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI · Zbl 0870.35003
[16] R.R. Coifman, S. Lafon, A.B. Lee, M. Maggioni, B. Nadler, F. Warner, S. Zucker, Geometric diffusions as a tool for harmonic analysis and structure definition of data, Proc. Natl. Acad. Sci. (2004), submitted for publication; R.R. Coifman, S. Lafon, A.B. Lee, M. Maggioni, B. Nadler, F. Warner, S. Zucker, Geometric diffusions as a tool for harmonic analysis and structure definition of data, Proc. Natl. Acad. Sci. (2004), submitted for publication · Zbl 1405.42043
[17] R.R. Coifman, M. Maggioni, Diffusion wavelets, Appl. Comput. Harmon. Anal. (2004), in press; R.R. Coifman, M. Maggioni, Diffusion wavelets, Appl. Comput. Harmon. Anal. (2004), in press · Zbl 1095.94007
[18] Donoho, D. L.; Grimes, C., Hessian eigenmaps: New locally linear embedding techniques for high-dimensional data, Proc. Natl. Acad. Sci., 100, 5591-5596 (2003) · Zbl 1130.62337
[19] F. Fouss, A. Pirotte, J.-M. Renders, The application of new concepts of dissimilarities between nodes of a graph to collaborative filtering, 2004, submitted for publication; F. Fouss, A. Pirotte, J.-M. Renders, The application of new concepts of dissimilarities between nodes of a graph to collaborative filtering, 2004, submitted for publication
[20] J. Ham, D.D. Lee, S. Mika, B. Schölkopf, A kernel view of the dimensionality reduction of manifolds, Technical report TR-110, Max Planck Institute for Biological Cybernectics, July 2003; J. Ham, D.D. Lee, S. Mika, B. Schölkopf, A kernel view of the dimensionality reduction of manifolds, Technical report TR-110, Max Planck Institute for Biological Cybernectics, July 2003
[21] Roweis, S. T.; Saul, L. K., Nonlinear dimensionality reduction by locally linear embedding, Science, 290, 2323-2326 (2000)
[22] Stein, E. M., Topics in harmonic analysis related to the Littlewood-Paley theory, Ann. Math. Stud. (1970), Princeton Univ. Press: Princeton Univ. Press Princeton, NJ · Zbl 0193.10502
[23] M. Hein, J. Audibert, U. vonLuxburg, From graphs to manifolds—Weak and strong pointwise consistency of graph Laplacians, in: Conference On Learning Theory, June 2005, pp. 470-485; M. Hein, J. Audibert, U. vonLuxburg, From graphs to manifolds—Weak and strong pointwise consistency of graph Laplacians, in: Conference On Learning Theory, June 2005, pp. 470-485 · Zbl 1095.68097
[24] A. Singer, From graph to manifold Laplacian: The convergence rate, Technical report, Yale University, 2005; A. Singer, From graph to manifold Laplacian: The convergence rate, Technical report, Yale University, 2005
[25] Z. Zhang, H. Zha, Principal manifolds and nonlinear dimension reduction via local tangent space alignement, Technical report CSE-02-019, Pennsylvania State University, 2002; Z. Zhang, H. Zha, Principal manifolds and nonlinear dimension reduction via local tangent space alignement, Technical report CSE-02-019, Pennsylvania State University, 2002
[26] Y. Weiss, Segmentation using eigenvectors: A unifying view, in: Proc. IEEE Int. Conf. on Computer Vision, 1999, pp. 975-982; Y. Weiss, Segmentation using eigenvectors: A unifying view, in: Proc. IEEE Int. Conf. on Computer Vision, 1999, pp. 975-982
[27] Pedersen, K. S.; Lee, A. B., Toward a full probability model of edges in natural images, (Nielsen, M.; Heyden, A.; Sparr, G.; Johansen, P., Proc. 7th European Conference on Computer Vision, Springer (2002), Copenhagen), 328-342, Part I · Zbl 1034.68651
[28] Huggins, P. S.; Zucker, S. W., Representing edge models via local principal component analysis, (Nielsen, M.; Heyden, A.; Sparr, G.; Johansen, P., Proc. 7th European Conference on Computer Vision, Springer (2002), Copenhagen), 384-398, Part I · Zbl 1034.68616
[29] B. Nadler, S. Lafon, R.R. Coifman, Diffusion maps, spectral clustering and reaction coordinates of stochastic dynamical systems, Appl. Comput. Harmon. Anal. (2006), this issue; B. Nadler, S. Lafon, R.R. Coifman, Diffusion maps, spectral clustering and reaction coordinates of stochastic dynamical systems, Appl. Comput. Harmon. Anal. (2006), this issue · Zbl 1103.60069
[30] Rosenberg, S., The Laplacian on a Riemannian Manifold (1997), Cambridge Univ. Press
[31] Smolyanov, O. G.; Weizsäcker, H. V.; Wittich, O., Brownian motion on a manifold as limit of stepwise conditioned standard Brownian motions, Canad. Math. Soc. Conf. Proc., 29, 589-602 (2000) · Zbl 0978.58015
[32] Pedersen, M., Functional Analysis in Applied Mathematics and Engineering (1999), CRC Press
[33] S. Lafon, Diffusion maps and geometric harmonics, Ph.D. dissertation, Yale University, 2004; S. Lafon, Diffusion maps and geometric harmonics, Ph.D. dissertation, Yale University, 2004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.