Abstract
Robust Subspace Recovery (RSR) is a fundamental task in high-dimensional data analysis, yet most existing methods, such as Dual Principal Component Pursuit (DPCP), require precise prior knowledge of the subspace codimension. This paper demonstrates that a simple, parallel Projected Subgradient Method (PSGM) can recover the correct subspace even when its dimension is unknown. We prove that the optimization process possesses an "implicit bias" that naturally regularizes the solution's rank, allowing multiple independent searchers to converge and span the entire true null space without explicit orthogonality constraints.
Introduction
Robust Subspace Recovery (RSR) aims to identify a low-dimensional linear structure within a dataset corrupted by outliers. A leading approach, DPCP, works by finding the "null space" (orthogonal complement) of the data's subspace. However, standard DPCP algorithms are brittle: they require the exact codimension ($c$) as an input. Underestimating $c$ fails to capture the full subspace, while overestimating it often leads to degenerate solutions. In real-world scenarios, such as hyperspectral imaging, the intrinsic dimensionality is rarely known a priori, creating a significant bottleneck for practical application.
Methods
The proposed framework, DPCP-PSGM, introduces a surprisingly simple yet effective modification to the DPCP framework:
- Relaxed Constraints: The hard orthogonality constraints typically required when searching for multiple null-space vectors are removed.
- Overestimation and Parallelization: Instead of searching for exactly $c$ vectors, the algorithm searches for $c'$ vectors, where $c'$ is a "safe overestimate" of the true codimension. Each vector is solved for independently and in parallel using a Projected Subgradient Method (PSGM).
- Random Initialization: Vectors are initialized randomly on a unit sphere rather than using standard spectral initialization (SVD-based). This allows the different parallel instances to explore the search space more freely.
Key Insights: The Power of Implicit Bias
The core theoretical contribution is the proof that these independent, randomly initialized searchers will "implicitly" cooperate. Even without being forced to stay orthogonal, the geometry of the non-convex landscape biases the vectors toward the true null space. This phenomenon acts as a form of "implicit rank regularization," achieving what typically requires complex mathematical penalties like the nuclear norm. Random initialization is a key feature here; it prevents the searchers from getting stuck in the same local minima and allows them to eventually "fill out" the entire null space.
Experimental Results
The authors evaluated DPCP-PSGM on both synthetic and real-world datasets:
- Simulated Data: In tests with up to 70% outliers, the proposed method maintained high accuracy in estimating the true codimension. In contrast, traditional methods like RSGM failed when the exact dimension was not provided.
- Hyperspectral Imaging (HSI): On the Washington DC Mall AVIRIS dataset, the method achieved an F1-score of ~0.99 for outlier detection. Standard DPCP methods, when given an incorrect codimension overestimate, failed completely with F1-scores of 0.
Conclusion and Future Work
This work shows that simple optimization algorithms can exhibit sophisticated behaviors like rank regularization through implicit bias. While the method requires a "safe overestimate" ($c'$) of the codimension, it significantly relaxes the requirements for prior knowledge in RSR. Future research may focus on optimizing convergence speeds for finite data cases and reducing the memory overhead associated with high-dimensional parallel instances.
Summary updated