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 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 without being sparse, and a mostly-zero table with six columns is sparse without being wide. Name which half hurts before choosing the fix.

This page separates the two and fixes each on its own terms. Reducing width on dense data belongs to dimensionality reduction, choosing the columns to keep belongs to feature selection, and replacing categories with short dense vectors belongs to vector embeddings.

The one idea you need first: a sparse matrix stores only the non-zeros, as values plus their positions, instead of every cell. A $1{,}000{,}000 \times 50{,}000$ table of mostly zeros therefore costs megabytes rather than hundreds of gigabytes, until an innocent-looking operation materialises every zero and the bill comes due at once.

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, because they decide whether the job runs at all. A $1{,}000{,}000 \times 50{,}000$ matrix holds $5 \times 10^{10}$ cells, so dense float64 needs 400 GB. At 0.1 percent density there are 50 million non-zeros; at 12 bytes each plus one pointer per row, CSR needs about 604 MB. Same information, a factor of 660 apart.

Three ordinary operations destroy that. Subtracting a column mean turns every zero into $-\mu$, so centring standardisation asks for the 400 GB, which is why scalers refuse sparse input unless told to skip the mean. .toarray() is the same disaster requested explicitly. Imputing the zeros overwrites every structural zero, and those zeros meant "not this category".

There is a statistics half too. A category appearing in 12 rows out of a million gives its coefficient 12 rows of evidence, and you hold 50,000 such categories. Rare columns are noisy columns, whatever the storage format.

Dimensionality is geometry

Add columns and the volume grows exponentially while your row count sits still. The usual gloss says "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 of the farthest distance to the nearest tends toward 1. Neighbours do not move further away; they stop being distinguishable from strangers. That breaks KNN, K-means, DBSCAN, and any RBF kernel, and the name for the condition is the curse of dimensionality.

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$ percent of the volume, while in a hundred it holds $0.9^{100}$, which is 0.0027 percent. 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 sits near-certain 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, as vector spaces and rank shows from the maths side.

What actually fixes it

Five options, and you often want two. Select on frequency, variance, or importance. Project with PCA on dense data or truncated SVD on sparse. Embed a short dense vector per category. 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. Distance methods need the width reduced first, and cosine similarity compares direction rather than magnitude when magnitude is the noisy part.

Worked example

Draw 500 uniform random points, pick one query point, and divide the farthest distance by the nearest. At 2 dimensions the ratio is 41.73: the nearest point sits 40 times closer than the farthest. At 10 it is 5.65. At 100 it is 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, and precision at 5 barely moves against random selection. Nothing changed but the width. The collapse from 41.73 to 1.36 is a property of the space, not anything you did wrong.

Code

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

Nothing changed but the width argument. The collapse from 41.73 to 1.36 is measured, not asserted, and the seed fixes it so your run prints the same three numbers.

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 400 GB dense and about 604 MB at 0.1 percent 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 distance concentration: 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 percent 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 do not.

What to Read Next

• SQL for Feature Extraction
• Streaming and Real-Time Data