Source-linked AI summary
Online Identification and Tracking of Subspaces from Highly Incomplete Information
Laura Balzano, Robert Nowak, Benjamin Recht
TL;DR
GROUSE addresses online subspace tracking when only highly incomplete observations are available. It uses incremental gradient descent on the Grassmannian and adapts to online matrix completion, with efficient updates and strong empirical performance. The method trades tracking rate against steady-state error when a constant non-vanishing stepsize is needed for changing subspaces.
Problem
Full-dimensional measurements can be impractical, motivating subspace tracking from highly incomplete coordinate observations.
Method
GROUSE applies incremental gradient descent on the Grassmannian, using least squares, residual computations, and rank-one subspace updates.
Results
GROUSE tracks subspaces from sparse observations and achieves strong online matrix completion performance, including faster and often higher-quality reconstructions than compared methods.
Takeaways & Limitations
GROUSE provides an efficient online approach for subspace tracking and matrix completion as data arrive incrementally.
Takeaways & Limitations
For changing subspaces, a constant stepsize is needed for adaptation, but its non-vanishing value prevents zero error even in the static case.
Abstract
from arXiv · showhide
This work presents GROUSE (Grassmanian Rank-One Update Subspace Estimation), an efficient online algorithm for tracking subspaces from highly incomplete observations. GROUSE requires only basic linear algebraic manipulations at each iteration, and each subspace update can be performed in linear time in the dimension of the subspace. The algorithm is derived by analyzing incremental gradient descent on the Grassmannian manifold of subspaces. With a slight modification, GROUSE can also be used as an online incremental algorithm for the matrix completion problem of imputing missing entries of a low-rank matrix. GROUSE performs exceptionally well in practice both in tracking subspaces and as an online algorithm for matrix completion.
1 Introduction
Low-dimensional subspaces can summarize high-dimensional dynamical systems, but conventional methods require impractical full-dimensional measurements. GROUSE addresses this by identifying and tracking subspaces from highly incomplete observations while also supporting online matrix completion.
- High-dimensional dynamical systems, network traffic, environmental monitoring, and seismological activity can often be represented in low-dimensional subspaces.
- Full-dimensional data collection and processing can be difficult or infeasible, motivating random subsampling when the underlying data are redundant.
- GROUSE builds high-quality subspace estimates from very sparsely sampled vectors using an incremental gradient procedure with complexity linear in problem dimensions.
- GROUSE can be adapted to online matrix completion, recovering low-rank matrices from small streaming random subsets of entries.
2 Problem Set-up
The paper formulates online tracking of an evolving d-dimensional subspace from partial coordinate observations through an observed-coordinate cost function. In the static case, this formulation connects to matrix completion and supports an online, column-wise optimization approach.
- The target is an evolving d-dimensional subspace S[t] of R^n, observed through vector coordinates indexed by Ω_t.
- The tracking error is measured as squared Euclidean distance between the estimated subspace and each observed vector on the revealed coordinates.
- For a time-invariant subspace, the average cost function estimates the algorithm’s steady-state behavior.
- With a static subspace and finite time horizon, the tracking cost is identical to a matrix completion optimization problem.
- The paper optimizes this cost one column at a time and reports state-of-the-art matrix completion performance when measurements correspond to random matrix columns.
3 Stochastic Gradient Descent on the Grassmannian
GROUSE applies incremental gradient descent on the Grassmannian, computing a rank-one geodesic update from sparsely observed data. The method supports efficient online subspace tracking, with convergence in the static case and a tracking–steady-state-error tradeoff for changing subspaces.
- Grassmannian gradient descent: GROUSE represents subspaces with orthonormal bases and follows the gradient of the observed-data cost along short Grassmannian geodesics.The Grassmannian is the manifold of d-dimensional subspaces of R^n.
- Gradient computation: The gradient is rank one, with singular value σ = 2||r||||w||, where r is the residual and w is the least-squares solution.This makes the geodesic step directly computable from the residual and coefficient vectors.
- Geodesic update: The geodesic update preserves orthogonality without explicitly orthogonalizing U after the gradient step.The additive second-order correction keeps iterates on the Grassmannian.
- GROUSE update: Each update requires solving a least-squares problem, computing the predicted component and residual, and applying a rank-one modification to the current basis.The algorithm uses only standard linear algebra operations and requires an observed vector together with its sampled locations.
- Step-size behavior: In the static case, GROUSE converges to a stationary point under suitable stepsizes, including η_t ∝ 1/t; changing subspaces require a constant stepsize.A non-vanishing stepsize produces a tradeoff between tracking rate and steady-state error.
- Relation to full-information methods: GROUSE adapts incremental QR or SVD-style updates to incomplete observations by estimating the orthogonal component only on revealed entries.The residual can serve as an excellent proxy for orthogonal energy when measurements exceed the subspace dimension by a logarithmic factor.
4 Numerical Experiments
Experiments evaluate GROUSE for static and changing subspaces, chlorine-level tracking, and online matrix completion under incomplete observations. Results show accurate tracking, residual-based success detection, and strong reconstruction speed and quality.
- Static Subspaces: With n = 700, d = 10, and sampling density 0.17, GROUSE was evaluated on static subspace identification under noisy observations.The data model uses Gaussian subspace coefficients and additive Gaussian noise with variance ω^2.
- Static Subspaces: Smaller diminishing stepsizes produced smaller noisy steady-state errors and faster convergence within the suitable range.The convergence target was error below 10^-6; without noise, converging stepsizes reached near machine precision.
- Subspace Change Detection: The residual norm closely approximated true subspace error and provided an effective indicator of tracking success.The approximation used was ||r||/||v_t||, with accuracy supported when the sample count is sufficiently large.
- Subspace Change Detection: Using constant stepsizes, GROUSE re-estimated abruptly changed subspaces, with adaptation time depending on the stepsize magnitude.The experiment introduced three random subspace changes over 14,000 observations.
- Rotating Subspace: For a rotating subspace with δ = 10^-5, GROUSE predictions matched true projection norms except during early transients.The comparison used projections of four random vectors over time.
- Tracking Chlorine Levels: On chlorine-monitoring data, GROUSE reconstructed sensor outputs while tracking a d = 6 subspace from data with ambient dimension n = 166.The dataset contained T = 4610 vectors, and results varied with sampling fraction and constant stepsize.
- Matrix Completion Problems: For matrix completion, GROUSE completed 700 × 700 rank-10 matrices sampled at density 0.17 and was faster than competing algorithms while often achieving higher-quality reconstructions.Against NNLS on very large problems, GROUSE achieved excellent reconstruction and was twice as fast.
5 Discussion and Future Work
The discussion highlights strong empirical performance while identifying unresolved questions about GROUSE’s consistency, basin entry, and automatic step-size adaptation.
- Open theoretical questions: GROUSE’s consistency conditions remain unresolved, motivating further theoretical investigation.The discussion specifically identifies characterizing the algorithm’s trajectory from a random starting subspace as difficult.
- Empirical performance: GROUSE converges to the noise floor after at most 10 passes over the matrix columns.Figure 5 measures time to reach a desired Frobenius norm error on the hidden matrix.
- Empirical performance: Figure 6 compares GROUSE with five matrix completion algorithms and reports a separate comparison with NNLS on large random problems.
- Open theoretical questions: It is not yet clear when GROUSE’s iterates enter the basin of attraction around the global minimum.
- Future work: Automatic adaptation of the step-size to varying data remains an open direction, despite substantial gains when the parameter is optimized.The step-size is the only parameter required to run GROUSE.