Dynamic Subspace Estimation with Grassmannian Geodesics

Cameron J. Blocker, Haroon Raja, Jeffrey A. Fessler, Laura BalzanoarXiv 2023 · DOI · arXiv

Abstract

Dynamic subspace estimation, or subspace tracking, is a fundamental problem in statistical signal processing and machine learning. This paper considers a geodesic model for time-varying subspaces. The natural objective function for this model is non-convex. We propose a novel algorithm for minimizing this objective and estimating the parameters of the model from data with Grassmannian-constrained optimization. We show that with this algorithm, the objective is monotonically non-increasing. We demonstrate the performance of this model and our algorithm on synthetic data, video data, and dynamic fMRI data.

Introduction

In signal processing and machine learning, high-dimensional data is often assumed to lie on a low-dimensional subspace. While standard tools like Principal Component Analysis (PCA) excel at identifying static subspaces, real-world data—such as video streams or medical imaging—often involves subspaces that drift, rotate, or evolve over time. Traditional tracking methods frequently rely on sudden "jumps" between subspaces or require extensive hyperparameter tuning.

Blocker et al. address this by modeling the path of a time-varying subspace as a geodesic on the Grassmannian manifold. A geodesic represents the "straightest" possible path between two points on a curved surface, providing a natural framework for tracking continuous movement without the "smearing" effects seen in static models.

Methods

The proposed model parameterizes the subspace $U(t)$ at time $t$ using the following expression: $$U(t) = H \cos(\Theta t) + Y \sin(\Theta t)$$ where $H$ is the starting point, $Y$ is the direction of travel, and $\Theta$ is a diagonal matrix representing the principal angles or "speed" of movement.

Conceptual visualization of a geodesic path on the Grassmannian manifold.

To estimate these parameters, the authors developed a Block Coordinate Descent (BCD) algorithm. The algorithm alternates between two main steps:

  1. Joint $(H, Y)$ Update: Employs a Procrustes-like step using a Singular Value Decomposition (SVD) to update the starting point and direction.
  2. $\Theta$ Update: Uses a Majorize-Minimize (MM) scheme to handle the non-convex trigonometric terms. By minimizing a quadratic surrogate function that upper-bounds the complex loss, the algorithm ensures a monotonic decrease in reconstruction error.

Results and Discussion

The model was evaluated across synthetic, video, and fMRI datasets. A significant finding in synthetic experiments was the identification of a sharp "phase transition" related to the number of samples required for recovery.

Average geodesic error as a function of rank ($k$) and sample points ($T$), highlighting the $T=2k$ phase transition.

Key Findings

  • Phase Transition: To accurately recover a moving subspace of rank $k$, at least $T = 2k$ samples are required. This provides a practical heuristic for data collection and model selection.
  • Denoising Performance: In high-noise video scenarios (e.g., "Curtain" and "Waterfall" datasets with $\sigma = 110$), the geodesic model outperformed standard rank-$k$ and rank-$2k$ SVDs by effectively filtering out noise that did not align with the temporal geodesic path.
  • fMRI Efficiency: On Oscillating Steady-State Imaging (OSSI) fMRI data, a rank-1 geodesic model captured scanner drift and physiological artifacts as effectively as more complex, unconstrained models, offering better interpretability.
  • Permutation Testing: To validate the geodesic assumption, the authors compared model loss on ordered vs. scrambled data. The significant loss spike on scrambled data confirmed that the geodesic structure is an inherent feature of the temporal data.

Conclusion

This work introduces a robust, monotonic algorithm for tracking subspaces on the Grassmannian manifold. While the current batch algorithm assumes known timepoints and a single geodesic segment, it provides a strong foundation for future developments. Potential extensions include learning "knots" for piecewise geodesic paths and developing streaming versions of the algorithm for real-time applications.

Summary updated

Abstract

Dynamic subspace estimation, or subspace tracking, is a fundamental problem in statistical signal processing and machine learning. This paper considers a geodesic model for time-varying subspaces. The natural objective function for this model is non-convex. We propose a novel algorithm for minimizing this objective and estimating the parameters of the model from data with Grassmannian-constrained optimization. We show that with this algorithm, the objective is monotonically non-increasing. We demonstrate the performance of this model and our algorithm on synthetic data, video data, and dynamic fMRI data.
BibTeX
@misc{blocker2023dynamic,
  author = {Cameron J. Blocker and Haroon Raja and Jeffrey A. Fessler and Laura Balzano},
  title = {{Dynamic Subspace Estimation with Grassmannian Geodesics}},
  year = {2023},
  eprint = {2303.14851},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2303.14851},
}
Figure