Sparse Data and High Dimensionality

Why Does This Exist?

One-hot encode a column with 50,000 merchants and you get two problems in one object. People treat them as one and reach for one fix. Separating them is the work.

Sparsity is a storage and statistics problem. Most cells are zero — a fact about memory layout, and about how little evidence each column carries.

Dimensionality is a geometry problem. Too many columns relative to rows, and the space behaves in ways your two-dimensional intuition gets wrong.

A wide one-hot block gives you both, as do a document-term matrix and a user-item table. But a dense 512-dimensional embedding is high-dimensional and not sparse; a mostly-zero table with six columns is sparse and fine.

Think of It Like This

How It Actually Works

Sparsity is arithmetic

A sparse matrix stores only the non-zeros. CSR keeps three arrays — values, column indices, and a pointer marking where each row starts — so a row of 50,000 zeros costs almost nothing. CSC does the same by column.

Run the numbers: they decide whether the job runs. A $1{,}000{,}000 \times 50{,}000$ matrix has $5 \times 10^{10}$ cells, so dense float64 is 400GB. At 0.1% density that's 50 million non-zeros; CSR stores 12 bytes each plus a pointer per row, so about 604MB.

Three ordinary operations destroy that. Subtracting a column mean turns every zero into $-\mu$, so standardisation with centring asks for the 400GB — hence StandardScaler refusing sparse input unless you pass with_mean=False. .toarray() is the same, requested explicitly. Imputing the zeros with missing_values=0 overwrites every structural zero; those zeros meant "not this category".

There's a statistics half: a category in 12 rows out of a million gives its coefficient 12 rows of evidence, and you have 50,000 of them.

Dimensionality is geometry

Add columns and the volume grows exponentially while your row count sits still. The usual gloss is "the data gets sparse", which is true and not the part that hurts.

The sharp version: in high dimensions, distances become nearly equal. For a query point and a cloud of others, the ratio between the farthest distance and the nearest tends toward 1. Neighbours don't get further away; they stop being distinguishable from strangers. That breaks KNN, K-means, DBSCAN and any RBF kernel.

Two facts make it concrete. Take a unit hypercube and keep 0.05 clear of every face: in two dimensions that inner region holds $0.9^2 = 81\%$ of the volume, in a hundred it holds $0.9^{100}$, or 0.0027%. Almost every point is jammed against a boundary. And the cosine between two random high-dimensional vectors has mean 0 with standard deviation about $1/\sqrt{d}$, so at $d = 1000$ a random pair is near-certain to sit within 0.1 of orthogonal.

Then the consequences. Sample complexity: covering a space to fixed resolution needs rows growing exponentially in $d$. Overfitting: once columns outnumber rows, a linear model fits any label vector exactly, shuffled ones included. Rank deficiency: with $p > n$ the rank is at most $n$, so an unregularised solve is ill-posed (vector spaces and rank).

What actually fixes it

Five options; you often want two. Select on frequency, variance or importance (feature selection). Project with PCA on dense data or TruncatedSVD on sparse (dimensionality reduction). Embed a short dense vector per category (vector embeddings). Regularise, since L1 and L2 make $p > n$ solvable. Change model: gradient-boosted trees take wide sparse input without complaint, because a split is a threshold on one column and never a distance.

Worked example

Draw 500 uniform random points, pick one query point, measure the farthest distance over the nearest. At 2 dimensions the ratio is 41.73: the nearest point is 40 times closer than the farthest. At 10 it's 5.65. At 100 it's 1.36 — the farthest of 500 points is only a third further away than the closest.

A KNN classifier then picks the five smallest of 500 numbers that sit within a third of each other. Noise decides the winners.

Show Me the Code

1import numpy as np2
3rng = np.random.default_rng(0)4
5
6def far_over_near(dim: int, n: int = 500) -> float:7    """Farthest over nearest distance, from one query point to n uniform random points."""8    points = rng.random((n, dim))9    query = rng.random(dim)10    d = np.linalg.norm(points - query, axis=1)11    return float(d.max() / d.min())12
13print(2, round(far_over_near(2), 2))      # -> 2 41.7314print(10, round(far_over_near(10), 2))    # -> 10 5.6515print(100, round(far_over_near(100), 2))  # -> 100 1.36

Nothing changed but the width. The collapse from 41.73 to 1.36 is a property of the space, not anything you did wrong.

Watch Out For

The Quick Version

• Two problems, one object. Sparsity is storage and statistics; dimensionality is geometry. Fix them separately.
• A $1{,}000{,}000 \times 50{,}000$ matrix is 400GB dense and about 604MB at 0.1% density in CSR.
• Centring, .toarray() and imputing structural zeros each destroy sparsity. Use with_mean=False or MaxAbsScaler.
• The real damage in high dimensions is that distances become nearly equal: farthest over nearest tends to 1.
• Measured on 500 random points: 41.73 at two dimensions, 5.65 at ten, 1.36 at a hundred.
• At 100 dimensions only 0.0027% of a hypercube sits clear of its faces. Once columns outnumber rows, a linear model fits any labels exactly.
• Select, project, embed, regularise, or switch model. Trees cope with wide sparse input; distance methods don't.

What to Read Next

• Categorical Encoding is where most of this arrives.
• Dimensionality Reduction is the projection route, PCA and TruncatedSVD included.
• Feature Selection is the cheaper route: fewer columns, not transformed ones.
• Vector Embeddings trades a wide sparse block for a short dense one that keeps meaning.
• Text Feature Representation is the sparse matrix you'll meet most.
• Vectors, Matrices and Tensors is the shape and storage groundwork.
• Definitions worth a look: Sparse Matrix, Curse of Dimensionality, and Cosine Similarity.