So I programmed a simple Perceptron algorithm to classify images from the MNIST dataset. My goal is to tell apart what image is a zero and what image is a one. First I trained my algorithm by extracting features from the images, which in essence resulted in converting the images into a two dimensional feature space where I then found a decision boundary by training on this model.
This yielded a test error of about $1\% $. Then I went on to train the algorithm on my whole images, so essentially I have a model $$o(x) = w^Tx + \theta$$ where $x$ is a $28^2$ large vector representing the images. What really surprises me is that the test error in this case is almost $0$.
At first I looked at my training error, which yielded exactly $0\%$, so I thought maybe the algorithm is just overfitting on the training data really badly if implemented in this way, but the test error tells a whole other story.
My expectation was, that the algorithm should do really bad in such a high dimensional space. Is it feasible that the perceptron algorithm (or basically gradient descent on a linear model $w^Tx + \theta$) does so well on this problem? I am pretty new to Machine Learning so any help would be greatly appreciated.