Even though all the images in the MNIST dataset are centered, with a similar scale, and face up with no rotations, they have a significant handwriting variation that puzzles me how a linear model achieves such a high classification accuracy.
As far as I am able to visualize, given the significant handwriting variation, the digits should be linearly inseparable in a 784 dimensional space, i.e., there should be a little complex (though not very complex) non-linear boundary that separates the different digits, similar to the well-cited $XOR$ example where positive and negative classes can not be separated by any linear classifier. It seems baffling to me how multi-class logistic regression produces such a high accuracy with entirely linear features (no polynomial features).
As an example, given any pixel in the image, different handwritten variations of the digits $2$ and $3$ can make that pixel illuminated or not. Therefore, with a set of learned weights, each pixel can make a digit look as a $2$ as well as a $3$. Only with a combination of pixel values should it be possible to say whether a digit is a $2$ or a $3$. This is true for most of the digit pairs. So, how is logistic regression, which blindly bases its decision independently on all pixel values (without considering any inter-pixel dependencies at all), able to achieve such high accuracies.
I know that I am wrong somewhere or am just over-estimating the variation in the images. However, it would be great if someone could help me with an intuition on how the digits are 'almost' linearly separable.