Sample Complexity in Manifold Learning
Yunqian Ma, Yun Fu · 2011
Manifold Learning may be defined as a collection of methods and associated analysis motivated by the hypothesis that high dimensional data lie in the vicinity of a low dimensional manifold. A rationale often provided to justify this hypothesis (which we term the “manifold hypothesis”) is that high dimensional data, in many cases of interest, are generated by a process that possesses few essential degrees of freedom. The manifold hypothesis is a way of circumventing the “curse of dimensionality,” i. e. the exponential dependence of critical quantities such as computational complexity (the amount of computation needed) and sample complexity (the number of samples needed), as a function of the dimensionality of data. Some other hypotheses which can allow one to avoid the curse of dimensionality are sparsity (i. e. the assumption that that the number of non-zero coordinates in a typical data point is small) and the assumption that data is generated from a Markov random field in which the number of hyper-edges is small.