Sparse Matrices & Structured Storage
Why real-world ML data is almost always mostly zeros, and how that's exploited.
On this page
Beginner: a sparse matrix is one where almost all the entries are zero. Storing every single zero explicitly, the way a normal ("dense") matrix does, wastes enormous amounts of memory and compute the moment matrices get large.
Intermediate: instead, sparse formats store only the non-zero values and their positions. The most common, CSR (Compressed Sparse Row) and CSC (Compressed Sparse Column), are optimized for fast row or column access respectively; COO (coordinate format — a plain list of (row, col, value) triples) is simplest to construct but slowest to compute with.
Advanced: operations on sparse matrices (multiplication, addition) use specialized algorithms that only ever touch the non-zero entries — a sparse matrix with 1% of entries non-zero can be multiplied roughly 100× faster and stored roughly 100× smaller than the naive dense approach, which is often the difference between an algorithm being feasible at all and not.
When k ≪ mn (which is the normal case for real-world sparse data), the savings are dramatic — this is exactly what the diagram below computes live for a random sparsity pattern.
Dense storage always costs mn numbers, no matter how many entries are zero. COO storage costs about 3k numbers, where k is the number of non-zero entries (one value plus a row index and a column index per entry). Sparse storage is worth it exactly when it uses less memory than dense storage:
So the breakeven density is 1/3 — if fewer than a third of the entries are non-zero, COO already wins on raw memory, and formats like CSR (which drop the redundant row index down to one integer per row instead of per entry) push that breakeven point even lower, often to a few percent density in practice for large matrices. This is why "sparse" in ML code doesn't mean "mostly zero" in some vague sense — it means the actual non-zero fraction has crossed a concrete, computable threshold below which switching formats is a strict win.
Where this is used: recommender-system interaction matrices (user × item, almost always <1% dense), sparse feature encodings (one-hot / bag-of-words text features), graph adjacency matrices for large graphs, and sparse gradients in embedding-table training — in every case the memory and compute savings from picking the right sparse format are the difference between an algorithm running on one machine and needing a cluster.
Only the highlighted cells are stored at all in a sparse format — everything else costs zero memory.
SciPy's sparse matrices support most of the same operations (@, addition, slicing) as dense NumPy arrays — the sparsity is handled transparently underneath.
import numpy as np
from scipy import sparse
dense = np.zeros((1000, 1000))
dense[np.random.randint(0, 1000, 500), np.random.randint(0, 1000, 500)] = 1.0
sparse_csr = sparse.csr_matrix(dense)
print(dense.nbytes) # 8,000,000 bytes
print(sparse_csr.data.nbytes + sparse_csr.indices.nbytes + sparse_csr.indptr.nbytes)
# a small fraction of that -- only non-zeros (plus lightweight index arrays) are stored
# Matrix-vector multiply works transparently on the sparse version, much faster:
v = np.random.rand(1000)
result = sparse_csr @ v- One-hot encodings and TF-IDF matrices in NLP are almost entirely zeros — a vocabulary of 100,000 words means each document vector has at most a few hundred non-zero entries.
- Graph adjacency matrices for real-world networks (social graphs, the web) are extremely sparse — most pairs of nodes are not directly connected — which is exactly why graph neural network libraries are built around sparse matrix operations.
- Recommender system user-item matrices (section 1.10) are sparse by construction — most users haven't rated most items.
- Converting a large sparse matrix to dense (
.toarray()) "just to check something" — this can exhaust memory instantly on matrices that were only ever tractable in sparse form. - Using COO format for repeated arithmetic — it's meant for construction; convert to CSR/CSC before doing heavy computation.
Going deeper
Sparse matrix multiplication (SpMM) and sparse matrix-vector multiplication (SpMV) are fundamentally harder to parallelize efficiently on GPUs than dense GEMM (section 1.5) — the irregular memory access pattern of "only touch the non-zeros" doesn't map cleanly onto Tensor Cores, which is an active area of systems research (block-sparse formats, structured sparsity) specifically aimed at closing this gap.
At the master level: structured sparsity (e.g. pruning entire blocks or channels of a neural network rather than individual scattered weights) trades a small amount of compression ratio for dramatically better real hardware speedups — unstructured sparsity often looks great on paper (fewer non-zero parameters) but delivers little real-world speedup because hardware isn't built to exploit arbitrary sparsity patterns efficiently.