Subspace Clustering with Irrelevant Features via Robust Dantzig Selector

Chao Qu, Huan XuNeurIPS 2015 · OpenReview

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.

Data models illustrating block-wise (left) and scattered (right) irrelevant features, highlighted in yellow.

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.

A clean block-diagonal matrix indicating successful subspace clustering, where points are perfectly grouped into their respective subspaces.

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

Abstract

This paper considers the subspace clustering problem where the data contains irrelevant or corrupted features. We propose a method termed ``robust Dantzig selector'' which can successfully identify the clustering structure even with the presence of irrelevant features. The idea is simple yet powerful: we replace the inner product by its robust counterpart, which is insensitive to the irrelevant features given an upper bound of the number of irrelevant features. We establish theoretical guarantees for the algorithm to identify the correct subspace, and demonstrate the effectiveness of the algorithm via numerical simulations. To the best of our knowledge, this is the first method developed to tackle subspace clustering with irrelevant features.
BibTeX
@inproceedings{qu2015subspace,
  author = {Chao Qu and Huan Xu},
  title = {{Subspace Clustering with Irrelevant Features via Robust Dantzig Selector}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2015},
  url = {https://openreview.net/forum?id=rJbDCdZd-r},
}
Figure