MOSAIC: Closed-Form Riemannian Streaming Updates on a Low-Rank Covariance Bundle

Abstract

We study fixed-memory compression of non-stationary, high-dimensional data streams using a moving low-rank Gaussian covariance model. Because different coordinate representations can describe the same covariance, the retained state is formulated on a quotient-bundle geometry rather than as a simple product of a subspace and covariance matrix. While this geometry is established, MOSAIC contributes an efficient streaming specialization that exploits the rank-one structure of each incoming sample. For covariance adaptation, MOSAIC derives an exact affine-invariant geodesic update that avoids matrix square roots and full matrix exponentials, reducing each update to quadratic cost in the retained rank. The update automatically adjusts its response according to how surprising a sample is under the current model: ordinary observations are incorporated conservatively, while unusually informative observations receive stronger adaptation. It also preserves positive definiteness for any finite positive step size, unlike a simple Euclidean approximation, which is stable only over a restricted range. For subspace tracking, MOSAIC combines a classical Grassmannian rank-one rotation with a noise-regularized precision preconditioner. This makes the subspace update account for the variance already represented in each retained direction, improving adaptation in anisotropic and noisy settings. The accompanying geometric analysis derives the corresponding Fisher structure and explains why the regularized preconditioner is preferable to the formal natural-gradient direction near the noise floor. A frame-coherent update further avoids an additional covariance-coordinate transformation when the subspace rotates. Experiments on drifting synthetic streams show that MOSAIC reduces distortion by 28 percent relative to the best tested baseline. At rank 16, it compresses a 50,000 by 256 data stream by about 2,778 to 1 while achieving distortion within 5.8 percent of the offline optimum. Ablation studies indicate that precision preconditioning is the main source of the accuracy improvement, while the exact covariance geodesic primarily contributes stronger geometric guarantees and robustness. Implementation: https://github.com/andrew-jeremy/Compressive-Online-Learning

Keywords