Is this known as a fact or from some analysis that the MNIST data-set is almost as if its sampled from some low (~10?) dimensional manifold? Is there a locally linear embedding to a low-dimensional space?  Of course I don't expect the data will be exactly on some low dimensional manifold; there will be some noise.
About the MNIST data-set
reference request;machine learning;data mining;data sets
The short answer is: I don't know.VisualizationsThere's been lots of work on visualizing the MNIST data set, in 2 dimensions, and even in 3 dimensions.For instance, here's an embedding into 2D space using a neighbor embedding visualization technique (a highly nonlinear embedding):Credit: Zhirong Yang, Jaakko Peltonen, and Samuel Kaski.  See their page on MNIST visualization.However, the NE embedding is not linear.  It doesn't try to be a linear map from the image space ($\mathbb{R}^{768}$) to the plot ($\mathbb{R}^2$).  Rather, it tries to preserve the topology: it tries to make images that are nearby (e.g., in L2 metric) be near each other in the visualization.See also this blog article for exploration of different ways of embedding MNIST into two or three dimensions, including both linear embeddings (e.g., PCA) and nonlinear embeddings.Here's another visualization of doing PCA to 2 dimensions on MNIST:Credit: taken from this nice blog postOne thing that is clear from those visualizations is that if you do PCA onto two or three dimensions, the result is not linearly separable.  It's not even close to linearly separable.Even if you look at just two different digits and apply 2-dimensional PCA to project linearly onto the two principal components, the result is again not even close to linearly separable:Credit: the same blog postSo at least 2 dimensions don't seem to be enough to distinguish 4's from 9's.In contrast, PCA onto 2 dimensions does give you something that's pretty close to linearly separable: it's enough to distinguish some other pairs of digits pretty well with a linear classifier, but not perfectly -- to get best accuracy, you need more than a linear classifier and more than 2 dimensions.Read the rest of that blog post to see what happens when you try to do a locally linear embedding to project all MNIST digits onto 2 dimensions.  You'll see that, while there are some commonalities, the result doesn't look good enough to get high accuracy.A note of cautionWe need to be careful about what you mean by lay on a manifold.  Of course, if you consider all the ways to write a 7 (say), those 7's will all lie on some manifold in $\mathbb{R}^{768}$.  I doubt that manifold is going to be a linear subspace (i.e., a hyperplane).If you allow arbitrarily nonlinear manifolds, it's not clear that it is useful or meaningful to ask what is the dimension of this manifold.  For instance, consider a mapping that maps each digit to $\mathbb{R}$ (1 dimension), e.g., all 0 digits get mapped to 0, all 1 digits get mapped to 1, all 2 digits get mapped to 2, and so on.  This is clearly possible in principle, but the mapping is extremely nonlinear.  Would you consider this evidence that the digits lie on a 1-dimensional manifold?  Probably not.  This highlights the challenge in making our intuition more precise.So you need to make sure you are asking the right question.Measuring dimensionality by learningOne way to think about this is to look for an embedding $f:\mathbb{R}^{768} \to \mathbb{R}^d$ into some lower-dimensional space ($d$-dimensional space), with the two properties that:The embedding $f$ is nice in some fashion -- it need not be linear, but hopefully it is continuous or locally linear or something like that.Enough information is preserved that we can still classify which digit it is, based on the result of the embedding.  In other words, given an image $x$ of an image, we should be able to tell which image it is given only $f(x)$: the result $f(x)$ of the embedding should be enough for a classifier to tell which digit it is, with about as high accuracy as would be possible given the original image.People have studied this.  For instance, people have built autoencoders, which are basically a way to use a deep neural network to build an embedding $f$ such that you can still reconstruct the image with reasonable accuracy.  You can train an autoencoder on the MNIST digits to build an embedding $f$ that maps to a lower-dimensional space, then train a classifier that tries to label the digits based on the result of the embedding.  The following paper looks at one approach to that, on the MNIST data set:Wei Wang, Yan Huang, Yizhou Wang, Liang Wang.  Generalized Autoencoder: A Neural Network Framework for Dimensionality Reduction.  IEEE Conference on Computer Vision and Pattern Recognition, 2014, pp.490--497.They build autoencoders that map to a 30-dimensional data space, and where a simple classifier achieve an error rate of 4-5%.  For MNIST, 4-5% error rate is very high: the state of the art is an error rate of 0.5% or so, when training a classifier on the original images.  So this means that, as far as we know, if you try to map down to 30 dimensions, a lot of information is still preserved, but a significant amount is lost: you lose enough information that the classifier's error rate increases by an order of magnitude.In short, 30 dimensions doesn't seem to be enough, at least for an embedding built in this way.The other caveat is that the embeddings built in this way use a multi-linear neural network, and thus might still be fairly nonlinear.  If you demand a particularly smooth/nice embedding, this result might not be relevant.