Subspace Approximation with Outliers

Amit Deshpande, Rameshwar Pratap

TL;DR

This paper introduces an efficient, linear-time algorithm for the subspace approximation problem with outliers. By assuming a mild condition on the ratio between "inlier error" and "total error," the authors bypass known computational hardness barriers (SSE-hardness) to provide a $(1+\epsilon)$-multiplicative approximation for $\ell_p$ norms and general M-estimators.

What Problem Does This Paper Address?

In data science, we often want to find a low-dimensional "best fit" (a $k$-dimensional subspace) for a high-dimensional dataset—think Principal Component Analysis (PCA). However, standard PCA is notoriously sensitive to outliers. If even a few points are far away from the main cluster, the resulting subspace can be wildly inaccurate.

The "Robust Subspace Approximation" problem tries to fix this by finding a subspace that minimizes the distance to the "best" $(1-\alpha)n$ points, effectively ignoring the $\alpha n$ outliers. While this sounds simple, it is computationally brutal. A special case called "Robust Subspace Recovery" (where inliers lie perfectly on a subspace) is known to be Small Set Expansion (SSE)-hard, meaning we likely can't find an efficient algorithm without making strong assumptions about the data.

Methods

The authors propose a sampling-based approach to build a weak coreset. A weak coreset is a small subset of the original data points whose span contains a subspace that is nearly as good as the optimal one.

The core technique is adaptive sampling:

  1. Initial Sampling: Start by picking points with probability proportional to their squared length (or $p$-th power of length).
  2. Iterative Refinement: In each subsequent round, sample new points with probability proportional to their distance from the current subspace.
  3. The "Aha" Assumption: To get around the SSE-hardness, the authors assume that the error of the optimal subspace on the inliers is at least a $\delta$ fraction of the total error on all points (including outliers). This $\delta$ parameter essentially quantifies how much the outliers "confuse" the model.

By repeating this sampling process for a number of rounds related to $\log(1/\delta)$, the algorithm "drags" the candidate subspace toward the optimal inlier subspace.

Datasets

Not discussed in the paper. This is a purely theoretical paper focused on providing provable algorithmic guarantees and complexity bounds. No experimental evaluations on real-world or synthetic datasets were performed.

Key Insights and Ideas

  • Bypassing Hardness: The most significant insight is identifying the $\delta$-error ratio assumption. It provides a "knob" to turn: if the inliers are somewhat noisy (high $\delta$), the problem becomes easier; if the inliers are perfectly on a plane (low $\delta$), we hit the SSE-hard wall.
  • Linear Complexity: The algorithm’s running time is $O(nd \cdot \text{poly}(k, 1/\epsilon, \log(1/\delta)))$. This is "input sparsity" time, meaning it scales linearly with the number of points and dimensions, making it theoretically viable for massive datasets.
  • Generalization to M-Estimators: The authors show their sampling technique isn't just for squared distances ($\ell_2$). It works for any $\ell_p$ norm and even robust loss functions like Huber loss or Tukey’s biweight, which are commonly used in robust statistics to dampen the influence of extreme values.
  • Affine Extension: They provide a clever trick for the "affine" case (where the subspace doesn't have to pass through the origin). Since they don't know which points are inliers, they can't calculate the inlier mean. Instead, they sample a small set of points and brute-force all possible partitions to estimate the true mean.

Key Results

  • Multiplicative Approximation: The algorithm finds a subspace $V$ such that the error is at most $(1+\epsilon)$ times the optimal error.
  • Bi-criteria Approximation: In some cases, the algorithm produces a subspace of slightly higher dimension than $k$ (a bi-criteria result) to achieve the $(1+\epsilon)$ error bound.
  • Robustness to Large $\alpha$: Interestingly, the results hold even when the fraction of outliers $\alpha$ is very large (e.g., 90% outliers), provided the $\delta$ condition is still satisfied.

Limitations and Future Work

  • The $\delta$ Dependency: The algorithm's complexity and the size of the coreset depend on $1/\delta$. If the inliers are extremely "clean" relative to the outliers, $\delta$ becomes very small, and the algorithm becomes less efficient.
  • Theoretical vs. Practical: While the running time is linear in $n$ and $d$, the "polynomial" factors involving $k, \epsilon,$ and $\log(1/\delta)$ can be quite large in practice.
  • Future Directions: The authors suggest that their work could be extended to more complex clustering problems with outliers or to online settings where data arrives in a stream. Additionally, implementing these algorithms to see how they perform against heuristics like RANSAC in practice remains an open task for the community.

Summary updated

BibTeX
@inproceedings{deshpande2020subspace,
  author = {Amit Deshpande and Rameshwar Pratap},
  title = {{Subspace Approximation with Outliers}},
  booktitle = {COCOON},
  year = {2020},
  doi = {10.1007/978-3-030-58150-3\_1},
}
Figure