High-dimensional data surrounds us, from video streams and network traffic to medical imaging. Fortunately, this data is rarely as complex as its raw dimensions suggest; it typically concentrates around low-dimensional linear structures called subspaces. However, real-world data collection is messy. Sensors fail, occlusions occur, and channels drop packets, leaving us with highly incomplete observations where the vast majority of entries are missing.
The traditional workflow for handling missing data relies on a two-step "complete-then-analyze" paradigm: first, impute the missing values using zero-filling or matrix completion, and then perform downstream tasks like tracking or clustering. This approach is computationally expensive and prone to error.
A powerful alternative has emerged: bypassing full data reconstruction entirely. By leveraging the underlying geometry of low-dimensional spaces, we can track, detect, and cluster data directly from sparse, fragmented observations.
The Geometry of Incompleteness
To understand why we can skip full data completion, consider what a missing entry represents geometrically. If a data point in a three-dimensional space is missing its $z$-coordinate, we do not observe a point; instead, we observe a line parallel to the $z$-axis. If it is missing both its $y$ and $z$ coordinates, we observe a plane.
In general, an incomplete observation restricts the true data point to an affine space. If we know that the complete data points must lie on a low-dimensional subspace, finding that subspace becomes a matter of identifying a low-dimensional linear structure that intersects all of these observed affine spaces.
A naive approach to this problem is zero-filling—replacing all missing entries with zeros. As shown by Benjamin Recht et al. in High-dimensional Matched Subspace Detection when data are missing, zero-filling introduces severe systematic errors. It pulls the data vectors toward the origin along the unobserved dimensions, distorting their geometric alignment and rendering subspace detection unreliable. Instead of filling gaps with arbitrary constants, robust methods use the geometry of the subspace itself to guide the estimation.
Online Subspace Tracking via Geometric Imputation
When data arrives continuously as a stream, we must track the underlying subspace in real time. This is the core mechanism of the GROUSE (Grassmannian Rank-One Update Subspace Estimation) framework introduced by Laura Balzano et al. in Online Identification and Tracking of Subspaces from Highly Incomplete Information.
Instead of optimizing over a massive, incomplete data matrix, GROUSE views the set of all possible low-dimensional subspaces as a smooth geometric surface known as a Grassmannian manifold. When a new, heavily undersampled vector arrives, the algorithm performs two steps:
- Projection-Based Imputation: It projects the observed coordinates of the incoming vector onto the current estimate of the subspace. This projection provides a mathematically rigorous prediction of what the missing entries should be, given our current knowledge of the system.
- Manifold Gradient Descent: It computes the residual between the observed components and their projections, using this error to take an incremental step along the Grassmannian manifold via gradient descent, updating the subspace estimate.
This projection-based imputation serves as a fundamental bridge between optimization and pure linear algebra. In On GROUSE and incremental SVD, Stephen J. Wright 0001 et al. proved that if you take the classical Incremental Singular Value Decomposition (iSVD) algorithm—originally designed for complete data—and modify it to impute missing values using the current subspace estimate while resetting the singular values at each step, it becomes mathematically equivalent to GROUSE.
Sparse Subspace Clustering Without Completion
In many practical scenarios, data does not lie within a single subspace, but rather within a union of multiple low-dimensional subspaces. For example, trajectories of different moving objects in a video sequence form distinct linear structures. Grouping these points into their respective categories is the goal of Sparse Subspace Clustering (SSC).
Standard SSC relies on the self-expressiveness property: each data point can be efficiently represented as a sparse linear combination of other data points belonging to the same subspace. Missing entries break this property because we cannot compute standard inner products between incomplete vectors.
To solve this, Congyuan Yang et al. developed algorithms in Sparse Subspace Clustering with Missing Entries that incorporate the missingness pattern directly into the sparse optimization framework, moving past the need for prior matrix completion.
The theoretical justification for why this works was established by Manolis C. Tsakiris et al. in Theoretical Analysis of Sparse Subspace Clustering with Missing Entries. The authors proved that the optimal strategy is to project the data points onto the specific observation pattern (the mask of known entries) of the point currently being analyzed. This operation preserves the underlying linear relationships within each specific subspace while ignoring unobserved dimensions, providing deterministic guarantees for perfect clustering.
This aligns with the fundamental insight formalized by Wenqi Wang et al. in On deterministic conditions for subspace clustering under missing data: clustering data into correct subspaces is a fundamentally easier mathematical problem than reconstructing the missing data entries themselves.
Sample Complexity and Global Integration
How many observations do we actually need to successfully estimate a subspace from incomplete data?
For signal detection, Benjamin Recht et al. demonstrated that a signal's energy within a subspace can be accurately quantified even when a vast majority of its components are missing. The required number of observed entries scales as $O(r \log r)$, where $r$ is the intrinsic dimension of the subspace, rather than the ambient dimension of the full data space.
For non-stationary environments where the underlying subspaces change over time, Praneeth Narayanamurthy proved in Provable Subspace Tracking From Missing Data and Matrix Completion that combining projected least squares with mini-batch SVD updates provides full theoretical guarantees for tracking dynamic subspaces from incomplete streams.
[Incomplete Data Blocks] ──> [Local Subspaces] ──> [Subspace Stitching] ──> [Global Range Space]
When data is highly fragmented across different sensors or observation windows, we can use a technique called subspace stitching. As detailed by Shahana Ibrahim et al. in Mixed Membership Graph Clustering via Systematic Edge Query, subspace stitching is a recursive procedure that integrates local subspaces derived from partially observed data blocks into a unified global range space. By piecing together these local geometric fragments, the global low-dimensional structure is recovered without ever requiring a full observation of the underlying high-dimensional matrix.
Key Foundational Work
High-dimensional Matched Subspace Detection when data are missing (2010) — contributed 4 concept elements to this direction.
Online identification and tracking of subspaces from highly incomplete information (2010) — contributed 1 concept elements to this direction.
Dimension reduction for censored regression data (1999) — contributed 1 concept elements to this direction.