Covariance matrices are the bedrock of multivariate statistics and machine learning. They allow us to capture how features vary together, model uncertainty, and align data distributions. Whether you are performing Principal Component Analysis (PCA), optimizing a second-order online classifier, or tracking uncertainty in a Bayesian model, you are likely relying on a covariance matrix.
However, covariance matrices suffer from a fatal flaw: quadratic memory scaling. If your data has $d$ dimensions, a full covariance matrix requires storing $O(d^2)$ elements. In modern machine learning, where feature dimensions routinely reach hundreds of thousands or millions, this quadratic growth hits a literal "memory wall." Storing a full covariance matrix for a million features requires trillions of parameters, completely exceeding the RAM of standard hardware.
The Ubiquity of the $O(d^2)$ Bottleneck
To understand why this is such a widespread crisis, consider how different subfields encounter this exact same wall:
- Online and Continual Learning: In online learning, second-order methods track feature confidence via a covariance matrix. As noted by Tan et al., this becomes prohibitive when features scale into the millions. Similarly, in exemplar-free continual learning, storing class-specific covariance matrices to prevent catastrophic forgetting creates massive storage overhead as the number of classes grows (Goswami et al.).
- Dimensionality Reduction and Hashing: Traditional batch PCA requires calculating and storing a $O(d^2)$ sample covariance matrix before finding principal components, making it impossible to process high-dimensional streaming data like genomics (Mitliagkas et al.).
- Uncertainty Quantification: Quantifying parameter variance in stochastic gradient descent (SGD) or tracking low-rank posterior covariances in massive linear systems requires memory that dwarfs the optimization process itself (Agrawalla et al.; Hennig).
How do we bypass this bottleneck without losing the rich second-order information that covariance matrices provide? Researchers have developed three primary paradigms: structural constraints, streaming sketches, and implicit computations.
Paradigm 1: Structural Constraints
The simplest way to avoid $O(d^2)$ storage is to assume that many feature correlations are zero. The most extreme version is a diagonal covariance matrix, which reduces memory to $O(d)$. However, as discussed by Badirli et al., diagonal approximations sacrifice the model's ability to capture complex feature correlations, creating a strict trade-off between memory efficiency and representation accuracy.
To strike a better balance, Tan et al. proposed enforcing a block-diagonal covariance structure for high-dimensional online learning. By grouping related features into blocks and ignoring cross-block correlations, they maintain the ability to capture critical local interactions while keeping memory requirements manageable.
Paradigm 2: Streaming Sketches and Data Summarization
When data arrives in a continuous stream, we cannot afford to store a massive historical covariance matrix. Instead, we can maintain a compressed "sketch" of the data that preserves the essential geometric properties of the full dataset.
For example, in the context of online hashing for massive datasets, Leng demonstrated that data sketching can maintain a tiny, representative summary of data streams, bypassing the need to compute global covariance matrices entirely.
For regression tasks, Shi et al. adapted the "Frequent Directions" sketching technique to streaming ridge regression. Instead of maintaining a full $O(d^2)$ covariance matrix, their deterministic algorithm compresses the incoming data matrix on the fly, reducing the space complexity to $O(d/\epsilon)$ while providing strong relative-error guarantees. Similarly, Mitliagkas et al. introduced a block-stochastic power method for streaming PCA that achieves a minimal memory footprint of $O(kd)$ (where $k$ is the number of top principal components), making PCA feasible for millions of dimensions.
Paradigm 3: Implicit Computation and Matrix-Free Methods
Often, we don't actually need the covariance matrix itself; we only need its action on a vector, its top eigenvalues, or its inverse. Matrix-free methods allow us to compute these downstream properties without ever explicitly forming or storing the $O(d^2)$ matrix in memory.
In dimensionality reduction, Ubaru et al. combined random matrix perturbation theory with Krylov subspace methods. This approach estimates the intrinsic dimension and principal components of a dataset directly from data-vector products, completely avoiding the explicit construction of the covariance matrix.
When an inverse covariance matrix is required (such as in sparse Gaussian Graphical Models), algorithms like those explored by Hsieh et al. and Zhang et al. leverage optimization tricks like coordinate descent, thresholding, and matrix completion to navigate the high-dimensional space without choking on full-matrix storage limits. Furthermore, Li et al. bypassed slow, memory-intensive eigendecompositions in global covariance pooling by utilizing a fast, iterative Newton-Schulz algorithm, accelerating training while preserving second-order representation richness.
Conclusion
The transition from low-dimensional statistical modeling to high-dimensional deep learning has turned the covariance matrix from a cheap tool into an expensive luxury. By shifting away from explicit $O(d^2)$ storage and toward structural approximations, streaming sketches, and matrix-free implicit updates, modern algorithms allow us to retain the expressive power of second-order statistics without collapsing under their weight.