Timezone: »

 
Poster
Robust Subspace Approximation in a Stream
Roie Levin · Anish Prasad Sevekari · David Woodruff

Thu Dec 06 02:00 PM -- 04:00 PM (PST) @ Room 210 #48
in Thu Poster Session B » 
We study robust subspace estimation in the streaming and distributed settings. Given a set of n data points {a_i}_{i=1}^n in R^d and an integer k, we wish to find a linear subspace S of dimension k for which sum_i M(dist(S, a_i)) is minimized, where dist(S,x) := min_{y in S} |x-y|_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.
Keywords: Regression · Algorithms
[ Paper] 

Author Information

Roie Levin (Carnegie Mellon University)
Anish Prasad Sevekari (Carnegie Mellon University)
David Woodruff (Carnegie Mellon University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors