Robust Subspace Approximation in a Stream

Roie Levin, Anish Prasad Sevekari, David P. WoodruffNeurIPS 2018 · OpenReview

Overview

In machine learning, finding a low-dimensional "subspace" that accurately represents high-dimensional data is a foundational task—akin to finding the best-fitting flat surface through a cloud of points. The standard tool for this is Singular Value Decomposition (SVD), which minimizes the squared distances (L2 norm) to the subspace. However, SVD is notoriously sensitive to outliers; because it squares distances, a single distant point can drastically skew the entire subspace.

"Robust" subspace approximation addresses this by minimizing the sum of un-squared distances (an L1-like approach). While SVD is computationally straightforward, robust approximation is NP-hard. Previous approximation algorithms required multiple passes over the data or complex sampling techniques that fail in turnstile streams (where data points are continuously added or deleted) or distributed settings (where data is partitioned across servers).

This paper introduces the first "one-pass" sketching algorithm for robust subspace approximation. By utilizing oblivious dimensionality reduction, the authors enable the discovery of low-dimensional structures in massive, high-speed, or distributed datasets while remaining highly resilient to outliers.

Summary of theoretical results and comparison with prior subspace approximation algorithms.

Algorithmic Framework: Oblivious Sketching

The authors propose a two-stage algorithmic framework based entirely on oblivious linear sketching—meaning the sketching matrices are generated independently of the data itself.

1. Coarse Approximation

The algorithm first identifies a "rough" version of the subspace. It uses a Sparse Cauchy Matrix to compress the data. Just as Gaussian distributions are ideal for L2 problems, Cauchy distributions are the "secret sauce" for preserving L1-style distances. The authors also introduce a novel BootstrapCoreset procedure. This allows them to perform "residual sampling"—a technique that traditionally requires two passes—in a single pass by maintaining noisy sketches in parallel.

2. Refinement

Once a coarse subspace is established, the algorithm "zooms in" to find a $(1+\epsilon)$ optimal solution. This stage involves more sophisticated median-based embeddings and culminates in solving a small, "sketched" version of the problem using a black-box polynomial solver.

Because the sketching matrices ($Z$) are oblivious and linear ($Z(A+B) = ZA + ZB$), the sketch $Z \cdot A$ can be updated dynamically as new data arrives or is deleted, without ever storing the full matrix $A$.

Core Theoretical Insights

  • The L1/L2 Gap: The authors leverage a fascinating theoretical insight: finding the best rank-$k$ matrix under the Frobenius norm (L2) inherently provides a $\sqrt{\log d}$ factor approximation for the L1-style "sum of distances" problem. This allows them to use efficient L2 tools as a foundational stepping stone.
  • Cauchy for Robustness: While Gaussian sketches preserve L2 distances, Cauchy sketches excel at preserving L1-like structures, making them the natural choice for robust dimensionality reduction.
  • Communication Efficiency: In distributed environments, each machine sketches its own local data and sends only the highly compressed sketch to a central coordinator. This drastically reduces network communication overhead.

Empirical and Theoretical Results

The algorithm, termed COARSEAPPROX, was evaluated against standard truncated SVD on both synthetic and real-world datasets.

  • Theoretical Guarantees: The algorithm achieves a $(1+\epsilon)$ approximation with a memory footprint that scales only logarithmically with the number of data points ($n$) and the dimension ($d$). This sublinear space requirement is a massive leap forward for streaming "Big Data" scenarios.
  • Synthetic Data: On generated Rank-2 and Rank-3 matrices with intentionally injected large outlier rows, the algorithm successfully ignored the noise to find the true underlying structure, whereas SVD was easily derailed.
  • Real-World Data: Tested on datasets from the UCI Repository (Glass and E. Coli), a heuristic extension of the algorithm consistently outperformed SVD. On the E. Coli dataset, it improved upon SVD by up to 50% in terms of the robust cost function for certain subspace dimensions ($k$).

Limitations and Future Directions

While groundbreaking for streaming and distributed models, the approach has a few limitations:

  • Computational Complexity: Although the algorithm runs in "input sparsity time" (extremely fast relative to the raw data size), the final refinement step relies on a black-box solver with a runtime exponential in $k/\epsilon$. Consequently, the algorithm is most practical when the target dimension $k$ is small.
  • Heuristic Gap: In practical evaluations, the authors utilized a heuristic extension (Iteratively Reweighted Least Squares) to achieve the best real-world results, indicating a gap between the pure theoretical algorithm and the most efficient practical implementation.
  • Constant Factors: The initial "coarse" approximation carries a large approximation constant ($O(\sqrt{\log d \dots})$). Future research could focus on tightening these theoretical bounds for the first pass.

Summary updated

Abstract

We study robust subspace estimation in the streaming and distributed settings. Given a set of n data points {a<em>i}</em>{i=1}^n in R^d and an integer k, we wish to find a linear subspace S of dimension k for which sum<em>i M(dist(S, a</em>i)) is minimized, where dist(S,x) := min<em>{y in S} |x-y|</em>2, and M() is some loss function. When M is the identity function, S gives a subspace that is more robust to outliers than that provided by the truncated SVD. Though the problem is NP-hard, it is approximable within a (1+epsilon) factor in polynomial time when k and epsilon are constant. We give the first sublinear approximation algorithm for this problem in the turnstile streaming and arbitrary partition distributed models, achieving the same time guarantees as in the offline case. Our algorithm is the first based entirely on oblivious dimensionality reduction, and significantly simplifies prior methods for this problem, which held in neither the streaming nor distributed models.
BibTeX
@inproceedings{levin2018robust,
  author = {Roie Levin and Anish Prasad Sevekari and David P. Woodruff},
  title = {{Robust Subspace Approximation in a Stream}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=S1WYNDZu-r},
}
Figure