Part 1: Sparse Matrix Formats and COO

A sparse matrix $A \in \mathbb{R}^{n \times d}$ has most entries zero. The sparsity ratio is: \[ \text{sparsity ratio} = \frac{\text{nnz}(A)}{n \times d} \] where $\text{nnz}(A)$ is the number of nonzeros. If this ratio is small (e.g., $< 0.1$), the matrix is sparse and should be stored specially.

Coordinate (COO) format: Store three arrays of length nnz: - row: row indices $i$ of nonzeros - col: column indices $j$ of nonzeros - val: values $A_{ij}$

Example: $A = \begin{pmatrix} 1 & 0 & 2 \\ 0 & 3 & 0 \\ 4 & 0 & 5 \end{pmatrix}$ has nnz = 5:

row = [0, 0, 1, 2, 2]
col = [0, 2, 1, 0, 2]
val = [1, 2, 3, 4, 5]

Memory: $3 \times \text{nnz}$ integers/floats (vs $n \times d$ for dense).

Part 2: Sparse Matrix-Vector Product

The sparse matvec $y = Ax$ is computed as:

y = zeros(n)
for k in range(nnz):
    y[row[k]] += val[k] * x[col[k]]

Time complexity: $O(\text{nnz})$. No nested loop over all $d$ entries.

Speedup over dense: Dense matvec is $O(n \times d)$. Sparse matvec is $O(\text{nnz})$. Speedup: $\frac{n \times d}{\text{nnz}}$. For sparse graphs with $\text{nnz} \approx n$ (constant average degree), speedup is $\sim d$ (dramatic).

Cache efficiency: COO has random-access pattern (row and column indices jump around), causing cache misses. Compressed formats (CSR, CSC) improve locality via index hierarchies, but are more complex to maintain.

Part 3: Sparse Matrices in Real Data

Text (term-document matrix): $n$ documents, $d$ terms. $A_{ij}$ = count of term $j$ in document $i$. Typical sparsity: 99%+ (most terms absent from most documents). nnz $\approx 10^7$–$10^9$ (billions of documents/terms but only millions of observed term-doc pairs).

Graphs (adjacency matrix): $n$ nodes. $A_{ij} = 1$ if edge $(i, j)$ exists, 0 otherwise. For sparse graphs, nnz $\approx n$ or $n \log n$ (constant or logarithmic average degree). Social networks, knowledge graphs, protein interaction networks all sparse. nnz $\ll n^2$.

Recommender systems (rating matrix): $n$ users, $d$ items. $A_{ij}$ = rating (or 0 if unobserved). Sparsity: 99.9%+ (users rate tiny fraction of items). nnz $\approx 10^7$–$10^8$ (billions of user-item pairs observed out of trillions possible).

Feature matrices in ML: High-dimensional text features (bag-of-words, TF-IDF), categorical one-hot encoding of large dictionaries, signal processing (wavelets have few significant coefficients). Sparsity: 95%–99.9%.

Why This Matters for ML

• Scale: Dense algorithms on billion-dimensional sparse data are infeasible (memory, time). Sparse algorithms make it routine.
• Efficiency: For sparse data, sparse algorithms are 10–1000× faster than dense (depending on sparsity ratio).
• Memory: Storing dense billion-node graph adjacency: $10^{18}$ bytes (exabyte). COO: $10^{10}$ bytes (10 GB, 100 million edges). Difference between “impossible” and “laptop-feasible.”
• Iterative methods: Conjugate gradient, GMRES, and other Krylov subspace methods require only matvecs; sparse matvec enables scalable solving of $Ax = b$ without forming explicit inverse.
• Graph algorithms: PageRank, community detection, message passing on graphs all reduce to sparse matvecs. Billions-of-node graphs are solvable via repeated sparse matvec.
• Recommendation: Collaborative filtering (matrix factorization of sparse rating matrix) is fundamental; sparse algorithms are mandatory.

ML Examples and Patterns

1. Text classification: Feature matrix is TF-IDF or one-hot bag-of-words (99%+ sparse). Ridge regression, SVM, logistic regression all solved via sparse least squares (LSQR). Without sparsity exploitation, infeasible on million-word vocabulary.
2. Graph neural networks (GNNs): Message passing computes sparse matvecs with adjacency matrix and learned weight matrix. Scales to billion-node graphs because each layer is $O(\text{nnz})$.
3. Recommender systems: Collaborative filtering factorizes sparse user-item matrix. Alternating least squares (ALS) solves per-user and per-item least squares subproblems, each on sparse matrices. Sparse algorithms are essential.
4. NLP and embeddings: Word embeddings on sparse co-occurrence matrices (positive PMI, CCA). Sparse linear algebra computes SVD or other factorizations efficiently.
5. Anomaly detection in networks: Sparse graph matrices from transaction/communication networks. Spectral methods (eigenvalues of adjacency) detect community structure; sparse eigensolvers (Lanczos) compute top eigenvectors in $O(\text{nnz} \cdot k \log k)$ for $k$ eigenvectors.

Connection to Linear Algebra Theory

• Matrix-vector product: $y = Ax$ is $O(n \times d)$ dense; $O(\text{nnz})$ sparse. Fundamental operation; the algebra is unchanged, only the implementation.
• Sparse matrix algebra: $(A + B)_{\text{nnz}} \leq \text{nnz}(A) + \text{nnz}(B)$ (sum of sparse matrices is sparse). $(AB)_{\text{nnz}}$ can be dense (product fills in). Example: if $A$ is tridiagonal, $A^2$ has entries beyond main/super/subdiagonals (“fill”).
• Sparse factorizations: LU, QR, Cholesky of sparse matrices can be sparse (with reordering to minimize fill). Sparse Cholesky of discretized Laplacian preserves sparsity; cost $O(n^{3/2})$ (not $O(n^3)$).
• Graph Laplacian: $L = D - A$ (degree matrix minus adjacency) is sparse (same sparsity as $A$). Eigenvalues/eigenvectors of $L$ determine graph connectivity; sparse eigensolvers compute them in $O(\text{nnz} \log n)$ per iteration.
• Iterative methods: CG, GMRES, LSQR all require repeated matvecs, never explicitly forming matrix inverse. Sparse matvec enables scalability; algorithm complexity is iterations $\times$ matvec cost $=$ iterations $\times O(\text{nnz})$.

Numerical and Implementation Notes

• Always check sparsity ratio before deciding: dense vs sparse. Ratio $< 0.01$ strongly suggests sparse. Ratio $> 0.1$ suggests dense despite high dimension.
• COO format is simple to construct and iterate. For many matvecs, convert to CSR (compressed sparse row) for better cache efficiency.
• Be aware of “fill” during factorization: sparse input can produce dense Cholesky. Reordering (nested dissection, approximate minimum degree) reduces fill.
• Sparse eigensolvers (Lanczos, Arnoldi) compute top $k$ eigenpairs in $O(k \times \text{iterations} \times \text{matvec cost})$ without ever forming matrix explicitly.
• For graph problems, exploit known structure (tree, planar, bounded treewidth); specialized algorithms can be superfast.

Numerical and Shape Notes

• Shapes: $A \in \mathbb{R}^{n \times d}$ with nnz $\ll n \times d$ (sparse). $x \in \mathbb{R}^d$ (dense vector). $y = Ax \in \mathbb{R}^n$ (dense output, even if $A$ sparse).
• Sparsity ratio: $\rho = \text{nnz} / (n \times d)$. Complexity scales with $1/\rho$: sparse algorithms faster by factor $1/\rho$ vs dense.
• COO space: $3 \times \text{nnz}$ (three values per nonzero: two indices, one value).
• CSR space: $2 \times \text{nnz} + n + 1$ (column indices, values, plus row pointers).

Pedagogical Significance

Sparsity is the bridge between theory and billion-scale practice in ML. Dense linear algebra assumes $O(n^2)$ or $O(n^3)$ complexity, manageable for $n \sim 10^4$. But modern data has $n, d \sim 10^6$ to $10^9$ (text, graphs). Dense algorithms fail completely. Sparse algorithms exploit structure: recognize sparsity → use tailored storage → get $O(\text{nnz})$ complexity → suddenly billion-scale is routine. This teaches structure exploitation as a universal principle: every problem has structure; recognize and exploit it or fail at scale. Students learn not to memorize algorithms but to think about problem structure first, then choose algorithms accordingly.