In machine learning, modeling dependencies between variables often requires estimating a covariance matrix $\Sigma$ or its inverse, the precision matrix $\Lambda$. When dealing with $d$-dimensional spaces, a full covariance matrix contains $O(d^2)$ parameters. This quadratic scaling creates a severe bottleneck:
- Storage: Storing a dense matrix for millions of parameters becomes memory-prohibitive.
- Computation: Inverting $\Sigma$ or calculating its determinant—operations required for evaluating Gaussian likelihoods, sampling, or performing natural gradient updates—demands $O(d^3)$ time.
To bypass this, practitioners often resort to a mean-field approximation, restricting $\Sigma$ to a diagonal matrix. While this drops the computational cost to $O(d)$, it forces an assumption of absolute independence, leaving the model completely blind to correlations. Low-rank plus diagonal covariance modeling offers a elegant middle ground, capturing the most critical correlations without paying the quadratic or cubic toll.
The Intuition: Splitting Variance Across Scales
The core idea is to parameterize the covariance matrix by splitting variance into two distinct scales:
$$\Sigma = D + V V^T$$
where $D \in \mathbb{R}^{d \times d}$ is a positive diagonal matrix, and $V \in \mathbb{R}^{d \times r}$ is a tall, low-rank "loading" matrix with rank $r \ll d$.
This formulation has an intuitive physical interpretation rooted in classical factor analysis, a connection leveraged early on by Saul et al. in Modeling Acoustic Correlations by Factor Analysis. The diagonal matrix $D$ represents independent, coordinate-specific noise or baseline variance for each dimension. The low-rank term $V V^T$ captures the global, shared factors that drive the primary axes of correlation across dimensions. By adjusting the rank $r$, we can smoothly trade off between the simplicity of a diagonal model ($r=0$) and the full expressive power of a dense covariance matrix ($r=d$).
Why It Works: Linear-Time Matrix Operations
The low-rank plus diagonal structure is powerful because it allows us to compute matrix inversions and determinants in linear time with respect to the high dimension $d$. This efficiency relies on two fundamental matrix identities.
The Woodbury Matrix Identity
To compute the precision matrix $\Sigma^{-1}$, we do not need to invert the full $d \times d$ matrix directly. Instead, the Woodbury identity allows us to shift the inversion to the smaller latent space of rank $r$:
$$(D + V V^T)^{-1} = D^{-1} - D^{-1} V (I_r + V^T D^{-1} V)^{-1} V^T D^{-1}$$
Because $D$ is diagonal, its inverse $D^{-1}$ is trivial to compute in $O(d)$ time. The only matrix inversion required is for the inner term $(I_r + V^T D^{-1} V)$, which is an $r \times r$ matrix. The total computational complexity drops from $O(d^3)$ to $O(r^3 + r^2d)$, which scales linearly with the dimensionality $d$ when $r$ is small.
Sylvester’s Determinant Theorem
Evaluating Gaussian densities also requires computing the log-determinant $\log |\Sigma|$. Sylvester's theorem allows us to compute this via the smaller $r \times r$ matrix:
$$|D + V V^T| = |D| \cdot |I_r + V^T D^{-1} V|$$
Again, $|D|$ is simply the product of the diagonal elements ($O(d)$), and the remaining determinant is computed on an $r \times r$ matrix ($O(r^3)$).
Applications Across the Machine Learning Landscape
This linear-time parameterization has become a foundational tool across diverse domains where high-dimensional uncertainty or correlation must be modeled efficiently.
Generative Modeling and Variational Inference
In deep directed generative models like Variational Autoencoders (VAEs), Rezende et al. demonstrated in Stochastic Backpropagation and Approximate Inference in Deep Generative Models that the covariance of the approximate posterior can be parameterized via a diagonal matrix plus a low-rank update. This allows the model to capture rich dependencies in high-dimensional latent spaces while keeping the optimization computationally tractable. More recently, Modi et al. utilized this structure in Batch, match, and patch: low-rank approximations for score-based variational inference to scale score-based variational inference to high dimensions without incurring quadratic memory costs.
Bayesian Deep Learning
Estimating uncertainty over the weights of neural networks requires navigating massive parameter spaces. To move beyond restrictive mean-field assumptions, Mishkin et al. introduced SLANG in SLANG: Fast Structured Covariance Approximations for Bayesian Deep Learning with Natural Gradient, which uses a diagonal-plus-low-rank structure to approximate the precision matrix within a natural gradient descent framework. This captures critical weight correlations during training. Extending this paradigm, Tomczak et al. integrated the low-rank plus diagonal covariance structure with the Local Reparameterization Trick in Efficient Low Rank Gaussian Variational Inference for Neural Networks, making correlated weight sampling scalable for deep architectures like ResNets.
Online Learning and State Estimation
In streaming data scenarios, tracking parameter uncertainty requires recursive updates akin to a Kalman filter. Shestopaloff et al. developed LO-FI in Low-rank extended Kalman filtering for online learning of neural networks from streaming data (CoLLAs 2023), an extended Kalman filtering approach that maintains a diagonal-plus-low-rank precision matrix to capture parameter correlations dynamically. This allows the system to adapt rapidly to distribution shifts with linear computational complexity. A similar recursive approach for high-dimensional posterior distributions was introduced by Lambert et al. in The limited-memory recursive variational Gaussian approximation (L-RVGA) via a recursive variational Gaussian approximation.
Structured Output and Time-Series Forecasting
When predicting high-dimensional outputs, capturing spatial or temporal correlations is essential. For instance, in medical image segmentation, Monteiro et al. modeled the spatial aleatoric uncertainty of logits using a low-rank multivariate Gaussian distribution in Stochastic Segmentation Networks: Modelling Spatially Correlated Aleatoric Uncertainty, enabling the efficient generation of multiple plausible segmentation hypotheses. In the context of time series, Salinas combined recurrent neural networks with a low-rank Gaussian copula process in High-dimensional multivariate forecasting with low-rank Gaussian Copula Processes, reducing parameter complexity from quadratic to linear and enabling the simultaneous forecasting of thousands of correlated time series.