# Subspace approximation with outliers

arXiv: https://arxiv.org/abs/2006.16573 · HTML: https://mlsanity.com/paper/2006.16573/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jun 2020.

## Built on by (most cited first, 1 of 1)

- [On Subspace Approximation and Subset Selection in Fewer Passes by MCMC Sampling](https://mlsanity.com/paper/2103.11107/) (2021)

## Abstract (arXiv)

The subspace approximation problem with outliers, for given n points in d dimensions x1,ldots, xn ∈ Rd, an integer 1 ≤ k ≤ d, and an outlier parameter 0 ≤ α ≤ 1, is to find a k-dimensional linear subspace of Rd that minimizes the sum of squared distances to its nearest (1-α)n points. More generally, the ℓp subspace approximation problem with outliers minimizes the sum of p-th powers of distances instead of the sum of squared distances. Even the case of robust PCA is non-trivial, and previous work requires additional assumptions on the input. Any multiplicative approximation algorithm for the subspace approximation problem with outliers must solve the robust subspace recovery problem, a special case in which the (1-α)n inliers in the optimal solution are promised to lie exactly on a k-dimensional linear subspace. However, robust subspace recovery is Small Set Expansion (SSE)-hard. We show how to extend dimension reduction techniques and bi-criteria approximations based on sampling to the problem of subspace approximation with outliers. To get around the SSE-hardness of robust subspace recovery, we assume that the squared distance error of the optimal k-dimensional subspace summed over the optimal (1-α)n inliers is at least δ times its squared-error summed over all n points, for some 0 < δ ≤ 1 - α. With this assumption, we give an efficient algorithm to find a subset of poly(k/ε) log(1/δ) loglog(1/δ) points whose span contains a k-dimensional subspace that gives a multiplicative (1+ε)-approximation to the optimal solution. The running time of our algorithm is linear in n and d. Interestingly, our results hold even when the fraction of outliers α is large, as long as the obvious condition 0 < δ ≤ 1 - α is satisfied.