Sparse Vector

A sparse vector is a vector in which most of the elements are zero, in contrast to a dense vector, in which most elements are non-zero. Google's Machine Learning Glossary defines it simply as "a vector whose values are mostly zero": for example, a 10,000-dimensional bag-of-words vector representing a 20-word phrase would have 9,980 zero values and only 20 non-zero values.^[1] Because only the non-zero elements and their positions need to be stored, sparse vectors are far more memory-efficient than dense ones when working with high-dimensional data, and they appear throughout machine learning, natural language processing, information retrieval, signal processing, and scientific computing. Understanding how to represent, store, and operate on sparse vectors is a foundational skill in applied mathematics and data science.

ELI5 (Explain like I'm 5)

Imagine you have a very long row of 1,000 lockers at school. Only 5 of them have anything inside; the rest are completely empty. Instead of walking past every single locker and writing down "empty, empty, empty..." over and over, you could just make a short list: "Locker 12 has a ball, Locker 47 has a book, Locker 213 has a hat, Locker 650 has a pencil, Locker 899 has a toy." That short list is like a sparse vector. You skip all the zeros (the empty lockers) and only keep track of the ones that matter. Computers do the same thing when most of the numbers in a list are zero: they save time and space by remembering only the non-zero values and where they are.

What is a sparse vector?

A vector v of dimension n is written as:

v = (v₁, v₂, v₃, ..., vₙ)

The vector is considered sparse when the number of non-zero entries, often denoted nnz (number of non-zeros), is much smaller than n. There is no universal threshold, but a common rule of thumb is that a vector (or matrix) is sparse when nnz is on the order of n rather than n² (for matrices) or when the fraction of non-zero elements is well below 50%. Google's glossary makes the same point about features: "a feature in which most values are zero" is a sparse feature, the opposite of a dense feature.^[1]

The sparsity of a vector is defined as:

sparsity = (number of zero elements) / (total number of elements)

Conversely, density is the fraction of non-zero elements:

density = nnz / n = 1 - sparsity

For example, a 10,000-dimensional vector with only 15 non-zero entries has a sparsity of 0.9985 (99.85%) and a density of 0.0015 (0.15%).

Why does sparsity matter?

Sparsity is not just a mathematical curiosity; it has direct practical consequences:

• Memory savings. Storing all n elements of a dense vector requires O(n) space. A sparse vector with nnz non-zeros requires only O(nnz) space (plus index overhead), which can be orders of magnitude smaller.
• Faster computation. Arithmetic operations such as dot products, addition, and matrix factorization can skip zero entries entirely, reducing time complexity from O(n) to O(nnz).
• Interpretability. In many applications, each dimension corresponds to a human-readable feature (for example, a word in a vocabulary). Sparse vectors make it straightforward to inspect which features are active.
• Scalability. Many real-world datasets are naturally sparse. User-item interaction matrices in recommendation systems may have densities below 1%. Text corpora represented as term-document matrices routinely have densities below 0.1%.

What is the difference between sparse and dense vectors?

The core distinction is straightforward: a sparse vector is mostly zeros, while a dense vector is mostly non-zeros.^[1] Sparse vectors are typically very high-dimensional (one dimension per vocabulary term or category) but store only a handful of values, whereas dense vectors, such as those produced by an embedding model, are lower-dimensional but pack meaningful values into every slot. The following table summarizes the main differences.

Scroll sideways for more →

Where do sparse vectors come from in machine learning?

Sparse vectors arise naturally in many stages of a machine learning pipeline.

One-hot encoding

One-hot encoding converts a categorical variable with k possible values into a binary vector of length k. Exactly one element is set to 1 and the remaining k - 1 elements are 0. When k is large (for instance, the number of unique zip codes or product IDs), the resulting vector is highly sparse.

Bag of words

The bag-of-words (BoW) model represents a document as a vector whose length equals the vocabulary size. Each element records how many times the corresponding word appears in the document. Because any single document uses only a small fraction of the full vocabulary, the resulting vector is extremely sparse. The scikit-learn library provides CountVectorizer for creating bag-of-words representations, and it stores the output as a SciPy sparse matrix.

TF-IDF

TF-IDF (Term Frequency-Inverse Document Frequency) extends the bag-of-words model by weighting each term according to how informative it is across the corpus. Common words like "the" and "is" receive low weights, while rare but meaningful terms receive higher weights. The resulting vector is still sparse and remains one of the most widely used representations in text classification and information retrieval.

Feature hashing

Also called the "hashing trick," feature hashing maps feature names to a fixed-size vector using a hash function. Scikit-learn's FeatureHasher uses the signed 32-bit Murmurhash3 function to determine column indices, producing a CSR sparse matrix. Feature hashing is useful when the feature space is too large to enumerate explicitly or when memory is constrained, such as in online learning scenarios.

Learned sparse embeddings

Recent advances have produced neural models that output sparse vectors with learned weights. Unlike traditional TF-IDF, these models can perform term expansion, adding weights for semantically related terms that do not appear in the original text. Two notable examples are:

• SPLADE (Sparse Lexical and Expansion Model), introduced by Naver Labs in 2021, uses a pretrained BERT model and its masked language model head to produce sparse vectors with learned term importance weights. The authors set out to learn "sparse representations for documents and queries that could inherit from desirable properties of bag-of-words models such as exact term matching and efficiency of inverted indexes."^[6] SPLADE achieves latency comparable to BM25 (within 4ms) while approaching the retrieval quality of dense neural rankers.
• BGE-M3, developed by the Beijing Academy of Artificial Intelligence (BAAI), supports dense, sparse, and multi-vector retrieval within a single model. It covers more than 100 languages and handles inputs up to 8,192 tokens. Its sparse output is generated by applying a linear layer followed by a ReLU activation to the hidden states.^[7]

Neural network activations with ReLU

Neural networks that use the ReLU activation function naturally produce sparse activations because ReLU sets all negative values to zero. In a typical hidden layer, 50% or more of the activations may be zero. This activation-level sparsity is exploited in sparse attention mechanisms and in structured pruning of network weights.

How are sparse vectors stored?

The defining idea of sparse storage is to keep only the non-zero values together with the indices that locate them, rather than materializing every zero. Storing every element of a sparse vector or matrix wastes memory, so several compressed storage formats have been developed, each making a different tradeoff between construction speed, modification flexibility, and computational performance.^[4]

Formats optimized for construction

These formats support efficient element-by-element insertion and modification. They are typically used to build a sparse structure before converting it to a computation-optimized format. The SciPy documentation advises: "To construct an array efficiently, use any of coo_array, dok_array or lil_array."^[4]

Scroll sideways for more →

COO (Coordinate) format stores each non-zero entry as a (row, column, value) triple. Sorting the entries first by row, then by column improves access speed. COO is the simplest format and converts quickly to CSR or CSC.

DOK (Dictionary of Keys) uses a hash map internally, giving O(1) lookup time for any individual element. It is well-suited for situations where the non-zero pattern is not known in advance.

LIL (List of Lists) keeps one list per row. Within each row, entries are stored sorted by column index. This format supports efficient row-wise insertion but is slower for column-wise access.

Formats optimized for computation

Once a sparse matrix is assembled, it is usually converted to one of the following formats for fast arithmetic and linear algebra. SciPy puts the rule plainly: "To perform manipulations such as multiplication or inversion, first convert the array to either CSC or CSR format," and "the CSR format is especially suitable for fast matrix vector products."^[4]

Scroll sideways for more →

CSR (Compressed Sparse Row)

CSR is the most widely used format for sparse computation. It stores three one-dimensional arrays:

• values: the non-zero entries, listed row by row.
• col_indices: the column index of each entry in the values array.
• row_ptr: an array of length (number of rows + 1) where row_ptr[i] is the index into values where row i begins.

For example, consider the 4x5 matrix:

1  0  0  0  2
0  0  3  0  0
0  0  0  0  0
0  4  0  0  5

Its CSR representation is:

values     = [1, 2, 3, 4, 5]
col_indices = [0, 4, 2, 1, 4]
row_ptr    = [0, 2, 3, 3, 5]

Row 0 starts at index 0 in values and contains entries at indices 0 and 1 (values 1 and 2). Row 2 is empty because row_ptr[2] == row_ptr[3] == 3. CSR format traces its origins to at least the mid-1960s, with the first complete description appearing in 1967.

CSR saves memory compared to dense storage when nnz < (m(n - 1) - 1) / 2 for an m x n matrix. It supports fast row slicing and efficient sparse matrix-vector multiplication (SpMV), which is a core operation in iterative solvers, gradient computation, and graph algorithms.

CSC (Compressed Sparse Column)

CSC is the transpose analogue of CSR. It stores values column by column, with row indices and column pointers. CSC is the default sparse format in MATLAB and is efficient for column slicing and solving sparse triangular systems. Many direct sparse solvers (LU, Cholesky) expect input in CSC format.

BSR (Block Sparse Row)

BSR extends CSR by replacing individual scalar entries with small dense blocks. It is well-suited for problems where non-zeros appear in regular block patterns, such as finite element discretizations with multiple degrees of freedom per node. For such problems, BSR is considerably more efficient than CSR or CSC for arithmetic operations because block operations can leverage BLAS routines.

DIA (Diagonal)

The DIA format stores the diagonals of a matrix as a 2D array of shape (number of diagonals, number of columns) plus an offset array indicating which diagonal each row represents. It is highly efficient for banded matrices but wastes memory when the non-zero pattern does not align with diagonals.

How is sparse matrix-vector multiplication (SpMV) computed?

Sparse matrix-vector multiplication (SpMV) computes y = Ax where A is a sparse matrix and x is a dense vector. SpMV is one of the most performance-sensitive operations in scientific computing and machine learning because it lies at the heart of iterative solvers (conjugate gradient, GMRES), PageRank, and neural network forward passes in sparse layers.

SpMV has very low arithmetic intensity (floating-point operations per byte of memory accessed), which makes it memory-bandwidth-bound rather than compute-bound. Optimizing SpMV therefore focuses on maximizing memory throughput through techniques such as:

• Choosing the right storage format for the matrix structure (CSR for general matrices, ELL or HYB for GPU execution).
• Reordering rows and columns to improve cache locality.
• Using vectorized (SIMD) instructions on CPUs or warp-level parallelism on GPUs.

On GPUs, the "vector kernel" approach uses multiple threads within a warp to collaboratively reduce a single sparse dot product, achieving higher utilization than scalar kernels. Research on multi-GPU SpMV shows that data transmission overhead can consume up to 53% of total SpMV time on two-GPU platforms and 63% on four-GPU platforms, making partitioning and communication-minimization strategies essential at scale.

What software libraries support sparse vectors?

Several mature libraries provide sparse vector and matrix support across programming languages.

Scroll sideways for more →

SciPy recommends building sparse structures with COO, DOK, or LIL formats, then converting to CSR or CSC for computation.^[4] As of SciPy 1.8+, the library has been transitioning from *_matrix classes to *_array classes that follow NumPy's array interface.

CuPy provides a SciPy-compatible API on the GPU, but explicit conversion is needed when moving data between CuPy and SciPy because the data resides on different devices (GPU vs. CPU).

PyTorch supports sparse tensors primarily in COO and CSR layouts.^[5] CSR tensors in PyTorch benefit from MKL (on CPU) and MAGMA (on GPU) backends for operations like SpMV. PyTorch's autograd engine can backpropagate through certain sparse operations, enabling sparse layers in trainable models.

What are sparse vectors used for?

Natural language processing

Sparse vectors are the backbone of classical NLP pipelines. Document classification, spam filtering, sentiment analysis, and topic modeling all rely on sparse term-document matrices. Even with the shift toward dense embeddings produced by transformer models, sparse representations remain valuable for keyword matching, lexical overlap scoring, and as features in ensemble systems.

Information retrieval and search

Search engines have historically relied on sparse vector models. BM25, the ranking function used by systems like Elasticsearch and Apache Lucene, scores documents based on sparse term frequency statistics. The inverted index, which maps each term to the list of documents containing it, is effectively a column-oriented sparse data structure. Modern search systems increasingly combine sparse retrieval with dense retrieval in a hybrid approach, using fusion algorithms such as Reciprocal Rank Fusion (RRF) to merge ranked lists from both methods.^[11]

Recommender systems

In collaborative filtering, the user-item interaction matrix records which users have interacted with (rated, purchased, clicked) which items. With millions of users and items, this matrix is extremely sparse because each user interacts with only a tiny fraction of available items. Sparse matrix factorization techniques decompose this matrix into lower-rank dense factors to predict missing entries. Platforms like Netflix, Spotify, and Amazon rely on such methods at scale.

Compressed sensing and signal processing

Compressed sensing exploits the fact that many signals are sparse in some transform domain (for example, the Fourier or wavelet domain). By solving an L1-regularized optimization problem (basis pursuit or LASSO), it is possible to reconstruct a signal from far fewer measurements than the Nyquist-Shannon sampling theorem would normally require.^[10] This principle is used in medical imaging (MRI acceleration), radar, and communications.

Scientific computing and simulation

Finite element methods, circuit simulation, and computational fluid dynamics all produce large sparse linear systems. The stiffness and mass matrices arising from finite element discretizations are sparse because each element interacts only with its neighbors. Efficient sparse solvers (both direct, like Cholesky or LU decomposition, and iterative, like conjugate gradient) are essential for solving these systems.^[2]

Graph and network analysis

The adjacency matrix of a graph is sparse when the graph has few edges relative to the number of possible edges. Social networks, web link graphs, and biological interaction networks are all sparse. Graph algorithms such as PageRank, community detection, and shortest-path computation operate on sparse adjacency matrices.

How does sparsity appear inside neural networks (pruning)?

Beyond sparse data representations, sparsity also appears in the structure of neural networks themselves. Weight pruning removes connections (sets weights to zero) in a trained network to reduce its size and speed up inference.

The Lottery Ticket Hypothesis, proposed by Frankle and Carlin in 2018, states that dense, randomly initialized networks contain sparse subnetworks ("winning tickets") that, when trained in isolation from the same initial weights, match the accuracy of the full network.^[8] Experiments have shown that transformer models can be pruned to remove up to two-thirds of all weights while maintaining strong performance. For BERT models specifically, researchers have found matching subnetworks at 40% to 90% sparsity on GLUE and SQuAD benchmarks.^[9]

Structured pruning removes entire neurons, attention heads, or layers rather than individual weights. This produces models that are not just theoretically sparse but practically faster on standard hardware, since dense matrix operations on smaller matrices are easier to accelerate than sparse operations on irregular patterns.

How are sparse and dense vectors combined in hybrid search?

Modern search and retrieval systems increasingly combine sparse and dense vector representations to get the best of both approaches. Sparse vectors excel at exact keyword matching and are efficient to index using inverted indices. Dense vectors, produced by neural encoders, capture semantic meaning and handle synonyms. Hybrid search fuses results from both retrieval paths, typically using a weighted combination or Reciprocal Rank Fusion.^[12]

Several vector databases support hybrid search natively:

Scroll sideways for more →

Performance considerations

Working with sparse vectors involves several practical tradeoffs.

Format selection. Use COO, DOK, or LIL for assembly, then convert to CSR or CSC for computation.^[4] Choosing the wrong format can result in orders-of-magnitude slowdowns. For example, element-wise insertion into a CSR matrix requires rebuilding its internal arrays, while the same operation in DOK takes O(1) time.

Fill-in. Some algorithms (such as LU factorization) introduce new non-zero entries ("fill-in") during computation, turning a sparse matrix into a less sparse one. Row and column reordering heuristics (approximate minimum degree, nested dissection) minimize fill-in and keep memory usage manageable.^[14]

GPU considerations. GPUs achieve high throughput on dense, regular operations. Sparse operations with irregular access patterns can underperform because of thread divergence and poor memory coalescing. The NVIDIA cuSPARSE library provides GPU-optimized SpMV in multiple formats (CSR, COO, BSR, HYB, ELL). Choosing the right format depends on the sparsity pattern of the matrix.

Sparse-dense boundary. Very low sparsity (below roughly 90%) can make sparse formats slower than dense arrays due to index overhead and indirect memory access. Profiling is recommended to determine whether sparse storage is actually beneficial for a given workload.

See also

• Sparsity
• Sparse Representation
• Sparse Attention
• Embeddings
• Bag of Words
• Word Embedding
• Feature Engineering
• Matrix Factorization
• Vector Database
• L1 Regularization

References

1. "Machine Learning Glossary." Google for Developers. https://developers.google.com/machine-learning/glossary ↩
2. Saad, Y. (2003). *Iterative Methods for Sparse Linear Systems*, 2nd edition. SIAM. ↩
3. "Sparse matrix." Wikipedia. https://en.wikipedia.org/wiki/Sparse_matrix
4. "Sparse arrays (scipy.sparse)." SciPy v1.17.0 documentation. https://docs.scipy.org/doc/scipy/reference/sparse.html ↩
5. "torch.sparse." PyTorch documentation. https://docs.pytorch.org/docs/stable/sparse.html ↩
6. Formal, T., Piwowarski, B., and Clinchant, S. (2021). "SPLADE: Sparse Lexical and Expansion Model for First Stage Ranking." *Proceedings of SIGIR 2021*. https://arxiv.org/abs/2107.05720 ↩
7. Chen, J., Xiao, S., Zhang, P., et al. (2024). "BGE M3-Embedding: Multi-Lingual, Multi-Functionality, Multi-Granularity Text Embeddings Through Self-Knowledge Distillation." https://arxiv.org/abs/2402.03216 ↩
8. Frankle, J. and Carlin, M. (2018). "The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks." *ICLR 2019*. https://arxiv.org/abs/1803.03635 ↩
9. Chen, T., Frankle, J., Chang, S., et al. (2020). "The Lottery Ticket Hypothesis for Pre-trained BERT Networks." *NeurIPS 2020*. https://arxiv.org/abs/2007.12223 ↩
10. "Compressed sensing." Wikipedia. https://en.wikipedia.org/wiki/Compressed_sensing ↩
11. "Sparse embeddings: Dense vs. sparse vector and usage with ML models." Elasticsearch Labs. https://www.elastic.co/search-labs/blog/sparse-vector-embedding ↩
12. "SPLADE for Sparse Vector Search Explained." Pinecone. https://www.pinecone.io/learn/splade/ ↩
13. "Sparse and Dense Embeddings." Zilliz Learn. https://zilliz.com/learn/sparse-and-dense-embeddings
14. Davis, T. A. (2006). *Direct Methods for Sparse Linear Systems*. SIAM. ↩