# zbMATH — the first resource for mathematics

##### Examples
 Geometry Search for the term Geometry in any field. Queries are case-independent. Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact. "Topological group" Phrases (multi-words) should be set in "straight quotation marks". au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted. Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff. "Quasi* map*" py: 1989 The resulting documents have publication year 1989. so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14. "Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic. dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles. py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses). la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

##### Operators
 a & b logic and a | b logic or !ab logic not abc* right wildcard "ab c" phrase (ab c) parentheses
##### Fields
 any anywhere an internal document identifier au author, editor ai internal author identifier ti title la language so source ab review, abstract py publication year rv reviewer cc MSC code ut uncontrolled term dt document type (j: journal article; b: book; a: book article)
Geometry on probability spaces. (English) Zbl 1187.68270

Summary: Partial differential equations and the Laplacian operator on domains in Euclidean spaces have played a central role in understanding natural phenomena. However, this avenue has been limited in many areas where calculus is obstructed, as in singular spaces, and in function spaces of functions on a space X where X itself is a function space. Examples of the latter occur in vision and quantum field theory. In vision it would be useful to do analysis on the space of images and an image is a function on a patch. Moreover, in analysis and geometry, the Lebesgue measure and its counterpart on manifolds are central. These measures are unavailable in the vision example and even in learning theory in general.

There is one situation where, in the last several decades, the problem has been studied with some success. That is when the underlying space is finite (or even discrete). The introduction of the graph Laplacian has been a major development in algorithm research and is certainly useful for unsupervised learning theory.

The approach taken here is to take advantage of both the classical research and the newer graph theoretic ideas to develop geometry on probability spaces. This starts with a space X equipped with a kernel (like a Mercer kernel) which gives a topology and geometry; $X$ is to be equipped as well with a probability measure. The main focus is on a construction of a (normalized) Laplacian, an associated heat equation, diffusion distance, etc. In this setting, the point estimates of calculus are replaced by integral quantities. One thinks of secants rather than tangents. Our main result bounds the error of an empirical approximation to this Laplacian on $X$.

##### MSC:
 68Q32 Computational learning theory 68T05 Learning and adaptive systems
##### Keywords:
Laplacian operator; graph Laplacian
##### References:
 [1] Aronszajn, N.: Theory of reproducing kernels. Trans. Am. Math. Soc. 68, 337–404 (1950) · doi:10.1090/S0002-9947-1950-0051437-7 [2] Belkin, M., Niyogi, P.: Laplacian eigenmaps for dimensionality reduction and data representation. Neural Comput. 15, 1373–1396 (2003) · Zbl 1085.68119 · doi:10.1162/089976603321780317 [3] Belkin, M., Niyogi, P.: Convergence of Laplacian eigenmaps. In: Neural Information Processing Systems, vol. 19, pp. 129–136 (2007) [4] Belkin, M., De Vito, E., Rosasco, L.: Random estimates of operators and their spectral properties for learning. Working paper [5] Bhatia, R.: Matrix Analysis. Graduate Texts in Mathematics, vol. 169. Springer, New York (1997) [6] Blanchard, G., Bousquet, O., Zwald, L.: Statistical properties of kernel principal component analysis. Mach. Learn. 66, 259–294 (2007) · Zbl 05193781 · doi:10.1007/s10994-006-6895-9 [7] Bougleux, S., Elmoataz, A., Melkemi, M.: Discrete Regularization on Weighted Graphs for Image and Mesh Filtering. Lecture Notes in Computer Science, vol. 4485, pp. 128–139. Springer, Berlin (2007) [8] Chung, F.R.K.: Spectral Graph Theory. Regional Conference Series in Mathematics, vol. 92. SIAM, Philadelphia (1997) [9] Coifman, R., Lafon, S., Lee, A., Maggioni, M., Nadler, B., Warner, F., Zucker, S.: Geometric diffusions as a tool for harmonic analysis and structure definition of data: diffusion maps. Proc. Natl. Acad. U.S.A. 102, 7426–7431 (2005) · doi:10.1073/pnas.0500334102 [10] Coifman, R., Maggioni, M.: Diffusion wavelets. Appl. Comput. Harmon. Anal. 21, 53–94 (2006) · Zbl 1095.94007 · doi:10.1016/j.acha.2006.04.004 [11] Cucker, F., Smale, S.: On the mathematical foundations of learning. Bull. Am. Math. Soc. 39, 1–49 (2001) · Zbl 0983.68162 · doi:10.1090/S0273-0979-01-00923-5 [12] Cucker, F., Zhou, D.X.: Learning Theory: An Approximation Theory Viewpoint. Cambridge University Press, Cambridge (2007) [13] De Vito, E., Caponnetto, A., Rosasco, L.: Model selection for regularized least-squares algorithm in learning theory. Found. Comput. Math. 5, 59–85 (2005) · Zbl 1083.68106 · doi:10.1007/s10208-004-0134-1 [14] De Vito, E., Rosasco, L., Caponnetto, A., De Giovannini, U., Odone, F.: Learning from examples as an inverse problem. J. Mach. Learn. Res. 6, 883–904 (2005) [15] Gilboa, G., Osher, S.: Nonlocal operators with applications to image processing. UCLA CAM Report 07-23, July 2007 [16] Koltchinskii, V., Giné, E.: Random matrix approximation of spectra of integral operators. Bernoulli 6, 113–167 (2000) · Zbl 0949.60078 · doi:10.2307/3318636 [17] Pinelis, I.: Optimum bounds for the distributions of martingales in Banach spaces. Ann. Probab. 22, 1679–1706 (1994) · Zbl 0836.60015 · doi:10.1214/aop/1176988477 [18] Smale, S., Yao, Y.: Online learning algorithms. Found. Comput. Math. 6, 145–170 (2006) · Zbl 1119.68098 · doi:10.1007/s10208-004-0160-z [19] Smale, S., Zhou, D.X.: Shannon sampling and function reconstruction from point values. Bull. Am. Math. Soc. 41, 279–305 (2004) · Zbl 1107.94007 · doi:10.1090/S0273-0979-04-01025-0 [20] Smale, S., Zhou, D.X.: Shannon sampling II. Connections to learning theory. Appl. Comput. Harmonic Anal. 19, 285–302 (2005) · Zbl 1107.94008 · doi:10.1016/j.acha.2005.03.001 [21] Smale, S., Zhou, D.X.: Learning theory estimates via integral operators and their approximations. Constr. Approx. 26, 153–172 (2007) · Zbl 1127.68088 · doi:10.1007/s00365-006-0659-y [22] von Luxburg, U., Belkin, M., Bousquet, O.: Consistency of spectral clustering. Ann. Stat. 36, 555–586 (2008) · Zbl 1133.62045 · doi:10.1214/009053607000000640 [23] Yao, Y., Rosasco, L., Caponnetto, A.: On early stopping in gradient descent learning. Constr. Approx. 26, 289–315 (2007) · Zbl 1125.62035 · doi:10.1007/s00365-006-0663-2 [24] Ye, G.B., Zhou, D.X.: Learning and approximation by Gaussians on Riemannian manifolds. Adv. Comput. Math. 29, 291–310 (2008) · Zbl 1156.68045 · doi:10.1007/s10444-007-9049-0 [25] Zhou, D., Schölkopf, B.: Regularization on discrete spaces. In: Pattern Recognition, Proc. 27th DAGM Symposium, Berlin, pp. 361–368 (2005)