The Challenge of "Dirty" Data in Subspace Clustering
Subspace clustering is a fundamental machine learning technique used to find low-dimensional structures within high-dimensional datasets. It is highly effective for tasks like identifying different moving objects in a video or grouping similar handwritten digits. The state-of-the-art approach, Sparse Subspace Clustering (SSC), works by expressing each data point as a sparse linear combination of other points in the dataset.
However, SSC has a critical vulnerability: it assumes the features are mostly "clean" or only contaminated by light Gaussian noise. In real-world scenarios, data is often "dirty." A dataset might contain 100 useful features alongside 50 completely irrelevant ones—perhaps due to sensor malfunctions, unrelated metadata, or background noise. Because these irrelevant features can have large magnitudes, they easily overwhelm the sparse recovery process, causing standard algorithms to fail entirely.
A Two-Fold Solution: The Robust Dantzig Selector
To tackle this "high-dimensional, big but dirty" data problem, the authors propose a novel framework that makes subspace clustering resilient to irrelevant features. Their solution relies on two key innovations:
1. The Robust Inner Product
Standard clustering relies on the dot product, which sums all feature-wise multiplications to measure similarity between data points. The authors replace this with a truncated robust inner product.
When comparing two vectors, the algorithm multiplies their components, sorts the results, and simply discards the largest $D_1$ values (where $D_1$ is an estimated upper bound on the number of irrelevant features). The intuition is straightforward: irrelevant features are likely to produce massive outlier values in the product. By throwing the largest values away, the algorithm recovers a "clean" estimate of the true similarity between points. You don't need to know which features are irrelevant, only how many might be.
2. The Dantzig Selector
Replacing the standard inner product in a Lasso-style formulation (like Lasso-SSC) creates a non-convex optimization problem that is computationally difficult to solve. To maintain efficiency, the authors adapt the Dantzig Selector instead of the Lasso.
Because the Dantzig Selector is essentially a linear program, it does not require the data's "covariance" matrix to be positive semidefinite. This mathematical property allows the authors to plug in their robust inner products while keeping the optimization problem convex, well-behaved, and easy to solve.
Theoretical Guarantees and Key Results
The authors provide strong theoretical backing for their method, proving that as long as the underlying subspaces are sufficiently "incoherent" (not too similar to one another) and the number of irrelevant features isn't overwhelmingly high, the algorithm is guaranteed to satisfy the Subspace Detection Property. This property ensures the algorithm will never mistakenly cluster points from different subspaces together.
The paper validates these claims through extensive numerical simulations using synthetic data:
- Superior Robustness: In simulations with an ambient dimension of $D=200$, the Robust Dantzig Selector maintained perfect clustering even when injected with 20+ irrelevant features. In stark contrast, standard SSC and Lasso-SSC began to fail almost immediately upon the introduction of irrelevant dimensions.
- Phase Transitions: The experiments revealed a clear "white region" of success across different tuning parameters. The method only broke down when the number of irrelevant features became exceptionally large (around $D_1 = 40$ in their specific test setup).
- Dimension Scaling: As predicted by their theoretical proofs, the valid range for the tuning parameter $\lambda$ shrinks as the underlying subspace dimension $d$ increases.
Limitations and Future Directions
While a significant step forward, the method has a few limitations. Most notably, it requires the user to provide an upper bound ($D_1$) on the number of irrelevant features; if this bound is significantly inaccurate, performance may degrade.
Additionally, the current theoretical proofs rely on a fully random model for the subspaces. Extending these guarantees to "semi-random" models (where subspaces are fixed but points are random) remains a difficult challenge because the robust inner product is not rotation-invariant. Finally, while linear programming is efficient, solving a separate optimization for every single data point can be computationally heavy for massive datasets, suggesting a need for faster, approximate solvers in future work.
Summary updated