In classical statistics, we often assume that high-dimensional data points—like the pixels in a video or the readings from a sensor network—lie on a fixed, low-dimensional linear subspace. If you imagine a 3D room, the data might all fall on a single 2D sheet of paper. Standard tools like Principal Component Analysis (PCA) are designed to find that paper.
But in the real world, the paper is rarely still. As Cameron J. Blocker and Jeffrey A. Fessler describe in Dynamic Subspace Estimation with Grassmannian Geodesics, the underlying structure of data often drifts, rotates, or bends over time. A security camera's background changes as shadows move; a mobile user's interference patterns shift as they walk. This phenomenon is known as non-stationarity or concept drift.
To handle this, researchers have developed a suite of algorithms that don't just find a subspace, but track it as it evolves.
The Geometry of Shifting Data
To track a moving subspace, we need a way to represent the "space of all possible subspaces." This is known as the Grassmannian manifold. Instead of treating a subspace as a static matrix, algorithms like GROUSE (Grassmannian Rank-One Update Subspace Estimation), introduced by Benjamin Recht in Online identification and tracking of subspaces from highly incomplete information, treat it as a point on this curved manifold.
When a new data point arrives, these algorithms perform a small step—an incremental gradient descent—along the surface of the Grassmannian. This allows the model to "follow" the data's rotation in real-time. Kyle Gilman and Laura Balzano extended this logic to multi-dimensional arrays (tensors) with TOUCAN, enabling the tracking of complex signals even when most of the data is missing.
Robustness Amidst the Noise
Tracking becomes significantly harder when the data is "messy." In video surveillance, for instance, the "low-rank" background is constantly obscured by "sparse" moving objects (outliers).
Praneeth Narayanamurthy has shown in New Results for Provable Dynamic Robust PCA that we can actually turn the temporal evolution of the subspace to our advantage. By assuming the subspace changes slowly, algorithms like NORST and s-ReProCS can tolerate a much higher density of outliers than static methods. They essentially use the previous frame's subspace as a "prior" to help filter out the noise in the current frame.
Similarly, Albert Akhriev and Andrea Simonetto developed methods that are robust to both sparse outliers (moving cars) and dense measurement noise (sensor jitter), achieving massive speedups by processing data trial-by-trial rather than in batches (Pursuit of Low-Rank Models of Time-Varying Matrices Robust to Sparse and Measurement Noise).
Detecting Abrupt Transitions
While some subspaces drift slowly, others jump. A camera might be bumped, or a new category of data might emerge in a stream. Xiaolin Huang addressed this in Online Robust Principal Component Analysis with Change Point Detection by incorporating statistical hypothesis testing. When the algorithm detects that the incoming data no longer fits the current low-rank model, it triggers a "reset," allowing the system to quickly latch onto the new subspace structure.
In the context of clustering, Li Liu introduced EDSSC (Dynamic Sparse Subspace Clustering for Evolving High-Dimensional Data Streams), which tracks the "birth and death" of entire data categories. This is crucial for applications like social media monitoring, where new topics of conversation appear and disappear dynamically.
Stability and Theoretical Guarantees
A major challenge in streaming PCA is stability. If the algorithm updates its subspace too aggressively, the representation becomes jittery, making downstream tasks (like classification) difficult. David Woodruff and Samson Zhou formalize this as "consistent low-rank approximation" in Consistent Low-Rank Approximation, providing algorithms that guarantee a high-quality fit while minimizing the "recourse" (the amount the subspace rotates) between steps.
This builds on early foundational work by Dima Kuzmin, whose Randomized PCA Algorithms with Regret Bounds proved that online algorithms could achieve performance nearly as good as the best subspace chosen in hindsight, with a computational cost that scales only logarithmically with the data's dimension.
By moving from static snapshots to continuous tracking, these researchers have enabled AI systems to maintain a coherent "view" of a world that is constantly in motion.