On Linear Separability of the MNIST Handwritten Digits Dataset

Ákos Hajnal

cs.LGMar 13, 2026

On Linear Separability of the MNIST Handwritten Digits Dataset

Authors: Ákos Hajnal

Organizations: Laboratory of Parallel and Distributed Systems Institute for Computer Science and Control (SZTAKI) Hungarian Research Network (HUN-REN) · John von Neumann Faculty of Informatics Óbuda University Budapest, Hungary

Abstract

The MNIST dataset containing thousands of handwritten digit images is still a fundamental benchmark for evaluating various pattern-recognition and image-classification models. Linear separability is a key concept in many statistical and machine-learning techniques. Despite the long history of the MNIST dataset and its relative simplicity in size and resolution, the question of whether the dataset is linearly separable has never been fully answered -- scientific and informal sources share conflicting claims. This paper aims to provide a comprehensive empirical investigation to address this question, distinguishing pairwise and one-vs-rest separation of the training, the test and the combined sets, respectively. It reviews the theoretical approaches to assessing linear separability, alongside state-of-the-art methods and tools, then systematically examines all relevant assemblies, and reports the findings.

Figures & tables

Figure 1: Samples from the MNIST dataset. First and last three images of the training (first row) and the test set (second row) are shown. Sub-captions indicate the digit (label) and the index of the sample in the series.

digit (samples)	1 (6742)	2 (5958)	3 (6131)	4 (5842)	5 (5421)	6 (5918)	7 (6265)	8 (5851)	9 (5949)
0 (5923)	Yes	Yes	Yes	Yes	Yes	Yes	Yes	Yes	Yes
1 (6742)		Yes	Yes	Yes	Yes	Yes	Yes	Yes	Yes
2 (5958)			No	Yes	Yes	Yes	Yes	No	Yes
3 (6131)				Yes	No	Yes	Yes	No	Yes
4 (5842)					Yes	Yes	Yes	Yes	No
5 (5421)						Yes	Yes	No	Yes

Table 1: Pairwise linear separability of the MNIST training set

digit (samples)	1 (7877)	2 (6990)	3 (7141)	4 (6824)	5 (6313)	6 (6876)	7 (7293)	8 (6825)	9 (6958)
0 (6903)	Yes	Yes	Yes	Yes	Yes	Yes	Yes	Yes	Yes
1 (7877)		Yes	Yes	Yes	Yes	Yes	Yes	Yes	Yes
2 (6990)			No	Yes	Yes	Yes	Yes	No	Yes
3 (7141)				Yes	No	Yes	Yes	No	Yes
4 (6824)					Yes	Yes	Yes	Yes	No
5 (6313)						Yes	Yes	No	Yes

Table 2: Pairwise linear separability of of the combined MNIST training and test set

digit (samples)	1 (1135	2 (1032)	3 (1010)	4 (982)	5 (892)	6 (958)	7 (1028)	8 (974)	9 (1009)
0 (980)	Yes	Yes	Yes	Yes	Yes	Yes	Yes	Yes	Yes
1 (1135)		Yes	Yes	Yes	Yes	Yes	Yes	Yes	Yes
2 (1032)			Yes	Yes	Yes	Yes	Yes	Yes	Yes
3 (1010)				Yes	Yes	Yes	Yes	Yes	Yes
4 (982)					Yes	Yes	Yes	Yes	Yes
5 (892)						Yes	Yes	Yes	Yes

Table 3: Pairwise linear separability of the MNIST test set

pair (all samples)	0–1 (2115)	0–2 (2012)	0–3 (1990)	0–4 (1962)	0-5 (1872)	0–6 (1938)	0–7 (2008)	0–8 (1985)	0–9 (1989)
Zhong’s method [ 6 ]	4.95s	7.91s	7.18s	6.99s	6.05s	5.9s	7.44s	6.85s	6.9s
CVXPY feasibility	1.1s	2.0s	1.2s	1.1s	1.2s	1.2s	0.9s	1.5s	1.4s

Table 4: Performance comparison of pairwise linear separability tests of digit 0 in the MNIST test set

digit execution time	1	2	3	4	5	6	7	8	9
0	12.3s 9.9s 1.1s	11.9s 14.5s 2.0s	10.8s 13.6s 1.2s	10.2s 11.2s 1.1s	10.8s 12.4s 1.2s	11.1s 13.9s 1.2s	11.1s 12.8s 0.9s	11.9s 14.5s 1.5s	10.9s 12.2s 1.4s
1		11.2s 14.3s 1.1s	9.8s 11.6s 0.7s	6.8 8.6 0.8s	6.6s 8.5s 0.6s	9.5s 10.9s 0.9s	7.2s 7.7s 0.6s	13.0s 16.6s 0.7s	6.4s 9.5s 0.8s
2			24.7s 28.4s 1.1s	12.7s 13.7s 1.1s	13.0s 16.1s 1.1s	12.7s 15.9s 1.7s	13.6s 17.3s 1.1s	22.6s 27.4s 0.9s	13.6s 16.1s 0.9s
3				10.4s 13.2s 1.2s	23.5s 23.7s 1.1s	11.9s 13.0s 1.1s	13.3s 15.7s 1.1s	23.3s 28.9s 1.2s	12.7s 17.7s 1.5s
4					9.7s 12.0s 1.1s	11.2s 13.1s 0.9s	9.6s 13.0s 0.8s	10.9s 11.4s 1.0s	18.0s 22.8s 1.0s
5						12.3s 17.6s 1.0s	11.3s 12.5s 1.0s	15.9s 18.6s 1.1s	12.0s 13.9s 0.8s

Table 5: Execution times of pairwise linear separability tests of the MNIST training (first row in the cell), combined (second row) and the test set (third row). (Boldface numbers denote non-separable pairs.)

digit (positive samples)	0 (5923)	1 (6742)	2 (5958)	3 (6131)	4 (5842)	5 (5421)	6 (5918)	7 (6265)	8 (5851)	9 (5949)
1-vs-rest linear separability (negative samples)	No (54077)	No (53258)	No (54042)	No (53869)	No (54158)	No (54579)	No (54082)	No (53735)	No (54149)	No (54051)

Table 6: One-vs-rest linear separability of the MNIST training set

digit (positive samples)	0 (6903)	1 (7877)	2 (6990)	3 (7141)	4 (6824)	5 (6313)	6 (6876)	7 (7293)	8 (6825)	9 (6958)
1-vs-rest linear separability (negative samples)	No (63097)	No (62123)	No (63010)	No (62859)	No (63176)	No (63687)	No (63124)	No (62707)	No (63175)	No (63042)

Table 7: One-vs-rest linear separability of the combined MNIST training and test set

digit (positive samples)	0 (980)	1 (1135)	2 (1032)	3 (1010)	4 (982)	5 (892)	6 (958)	7 (1028)	8 (974)	9 (1009)
1-vs-rest linear separability (negative samples)	Yes (9020)	Yes (8865)	Yes (8968)	Yes (8990)	Yes (9018)	No (9108)	Yes (9042)	Yes (8972)	No (9026)	No (8991)

Table 8: One-vs-rest linear separability of the MNIST test set

digit execution time	0	1	2	3	4	5	6	7	8	9
training set	130s	209s	95s	122s	114s	89s	140s	128s	99s	112s
training+test	158s	189s	115s	148s	139s	114s	155s	179s	116s	143s
test set	9.5s	10.1s	20.8s	19.3s	10.2s	22.6s	11.3s	11.2s	17.5s	21.5s

Table 9: Execution times of the one-vs-rest linear separability tests of the MNIST training, combined (training+test), and the test sets. (Boldface numbers denote non-separable cases.)

Linear Classification

See all 19 papers

Directional Linear Separability of Neural Representations: Geometry and Transformations
Jun 7, 2026Yi Wei, Xuan Qi, Suorong Yang +1Neural Representation Geometry Linear Classification
DITEN University of Genoa, Genoa, Italy · State Key Laboratory of Novel Software Technology School of Artificial Intelligence Nanjing University, Jiangsu, China
Relocation of compact sets in $\mathbb{R}^n$ by diffeomorphisms and linear separability of datasets in $\mathbb{R}^n$
Apr 23, 2026Xiao-Song Yang, Xuan Zhou, Qi ZhouNeural Network Expressivity
School of Mathematics and Statistics, Huazhong University of Science and Technology, 1037 Luoyu Road, 430074 Wuhan, P.R. China · Hubei Key Laboratory of Engineering Modeling and Scientific Computing, Huazhong University of Science and Technology, Wuhan 430074, P.R. China
A Geometrical Approach to Constructing Neural Networks for Perfect Training-set Classification
Oct 12, 2026Akos HajnalNeural Network Memorization Image Classification
Laboratory of Parallel and Distributed Systems Institute for Computer Science and Control (SZTAKI) · John von Neumann Faculty of Informatics Obuda University Budapest, Hungary

Jun 7, 2026J/K move · Enter open · S save

Directional Linear Separability of Neural Representations: Geometry and Transformations

Yi Wei, Xuan Qi, Suorong Yang, Furao Shen

DITEN University of Genoa, Genoa, Italy · State Key Laboratory of Novel Software Technology School of Artificial Intelligence Nanjing University, Jiangsu, China

Neural Representation Geometry Linear Classification

Open paper AskPDF arXiv

Neural networks build representations through affine maps and nonlinear activations. Injective affine maps preserve linear separability, raising the problem of how they prepare data for nonlinear improvement and how much gain can be guaranteed before complete separation. We introduce the directional linear separability measure (D-LSM), which quantifies unavoidable competing-sample intrusion over affine halfspaces retaining every target sample, characterize its supporting geometry, and prove invariance under injective affine embeddings. For gated activations including ReLU, GELU, and SiLU, pre-activation projection bounds yield sufficient conditions for preserving all previous exclusions and recovering additional samples, with a gain bound determined by the certified recovery count. Under an aggregate-tube condition, an explicit affine construction realizes recovery with sufficient width, scaling conditions, and simultaneous multiclass guarantees through a shared layer. Exact controlled experiments compare certified and realized gains, assess certificate coverage, and exhibit bound attainment before complete separation and in affine-tube constructions. In learned Vision Transformer (ViT) representations, a feasible lower-bound estimator yields earlier post-GELU saturation certificates of exact separability, while boundary transport numerically supports affine invariance.

Abstract

Linear Classification

Explore similar work

Directional Linear Separability of Neural Representations: Geometry and Transformations

Relocation of compact sets in Rn\mathbb{R}^nRn by diffeomorphisms and linear separability of datasets in Rn\mathbb{R}^nRn

A Geometrical Approach to Constructing Neural Networks for Perfect Training-set Classification

Relocation of compact sets in $\mathbb{R}^n$ by diffeomorphisms and linear separability of datasets in $\mathbb{R}^n$