How to prove that the manifold assumption is correct? In machine learning, it is often assumed that a data set lies on a smooth low-dimensional manifold (the manifold assumption), but is there any way to prove that assuming certain conditions are satisfied, then the data set is indeed (approximately) generated from a low-dimensional smooth manifold?
For example, given a data sequence $\{\mathbf{X}_1 \ldots \mathbf{X}_n\}$ where $\mathbf X_i \in \mathbb{R}^d$ (say the sequence of face images with different angles) and a corresponding label sequence $\{ y_1 \ldots y_n\}$ where $y_1 \preceq y_2 \ldots \preceq y_n$  (say the angles of the face sequence). Suppose when $X_i$ and $X_{i+1}$ are very close, their labels $y_i$ and $y_{i+1}$ are also very close, we can imagine that it is likely that $\{\mathbf{X}_1 \ldots \mathbf{X}_n\}$ lie on a low-dimensional manifold. Is this true? If so, how can we prove it? Or what conditions does the sequence need to satisfy so that the manifold assumption can be proven to be true?
 A: Any finite set of points can fit on any manifold (theorem reference needed, I cant remember what the theorem is, I just remember this fact from uni). 
If one does not want all points to be identified, then the lowest possible dimension is 1.
Take as a simple example, given N 2d points, there exists some N - 1 order polynomial where all N points lie on that polynomial.  Therefore we have a 1d manifold for any 2d dataset. I think the logic for arbitrary dimensions is similar.
So, that's not the issue, the real assumptions are on the structure/simplicity of the manifold, particularly when treating connected Riemannian manifolds as metric spaces. Ive read papers on this manifold hocus pocus, and found if you read carefully some pretty huge assumptions emerge!
The assumptions made are when the induced definition of "closeness" is assumed to "preserve the information in our dataset", but since this not formally defined in Information Theoretic terms, the resulting definition is pretty ad hoc and quite a huge assumption indeed. In particlar the problem seems to be that "closeness" is preserved, i.e. two close points, stay close, but that "farness" is not, and so two "far" points do not stay far.
In conclusion I would be very wary of such trickery in machine learning unless its known the dataset is indeed naturally euclidean, e.g. visual pattern recognition. I would not consider these approaches appropriate for more general problems.
A: It quickly becomes apparent, by looking at many accounts of the "manifold assumption," that many writers are notably sloppy about its meaning. The more careful ones define it with a subtle but hugely important caveat: that the data lie on or close to a low-dimensional manifold.
Even those who do not include the "or close to" clause clearly adopt the manifold assumption as an approximate fiction, convenient for performing mathematical analysis, because their applications must contemplate deviations between the data and the estimated manifold.  Indeed, many writers later introduce an explicit mechanism for deviations, such as contemplating regression of $y$ against $\mathrm x$ where $\mathrm x$ is constrained to lie on a manifold $M^k\subset \mathbb{R}^d$ but the $y$ may include random deviations.  This is equivalent to supposing that the tuples $(\mathrm x_i, y_i)$ lie close to, but not necessarily on, an immersed $k$-dimensional manifold of the form
$$(\mathrm x,f(x)) \in M^k \times \mathbb{R} \subset \mathbb{R}^d\times \mathbb{R}\approx \mathbb{R}^{d+1}$$
for some smooth (regression) function $f:\mathbb{R}^d\to \mathbb{R}$.  Since we may view all the perturbed points $(\mathrm x,y)=(\mathrm x,f(\mathrm x)+\varepsilon)$, which are merely close to the graph of $f$ (a $k$ dimensional manifold), as lying on the $k+1$-dimensional manifold $M^k\times \mathbb R$, this helps explain why such sloppiness about distinguishing "on" from "close to" may be unimportant in theory.
The difference between "on" and "close to" is hugely important for applications.  "Close to" allows that the data may deviate from the manifold.  As such, if you choose to estimate that manifold, then the typical amount of deviation between the data and the manifold can be quantified.  One fitted manifold will be better than another when the typical amount of deviation is less, ceteris paribus.

The figure shows two versions of the manifold assumption for the data (large blue dots): the black manifold is relatively simple (requiring only four parameters to describe) but only comes "close to" the data, while the red dotted manifold fits the data perfectly but is complicated (17 parameters are needed).
As in all such problems, there is a tradeoff between the complexity of describing the manifold and the goodness of fit (the overfitting problem).  It is always the case that a one-dimensional manifold can be found to fit any finite amount of data in $\mathbb{R}^d$ perfectly (as with the red dotted manifold in the figure, just run a smooth curve through all the points, in any order: almost surely it will not intersect itself, but if it does, perturb the curve in the neighborhood of any such intersection to eliminate it).  At the other extreme, if only a limited class of manifolds is allowed (such as straight Euclidean hyperplanes only), then a good fit may be impossible, regardless of the dimensions, and the typical deviation between data and the fit may be large.
This leads to a straightforward, practical way to assess the manifold assumption: if the model/predictor/classifier developed from the manifold assumption works acceptably well, then the assumption was justified.  Thus, the appropriate conditions sought in the question will be that some relevant measure of goodness of fit be acceptably small.  (What measure?  It depends on the problem and is tantamount to selecting a loss function.)
It is possible that manifolds of different dimension (with different kinds of constraints on their curvature) may fit the data--and predict held-out data--equally well.  Nothing can be "proven" about "the underlying" manifold in general, especially when working with large, messy, human datasets.  All we can usually hope for is that it the fitted manifold is a good model.
If you do not come up with a good model/predictor/classifier, then either the manifold assumption is invalid, you are assuming manifolds of too small a dimension, or you haven't looked hard enough or well enough.
