Robust Subspace Approximation in a Stream
We study robust subspace estimation in the streaming and distributed settings. Given a set of n data points
and an integer k, we wish to find a linear subspace S of dimension k for which
is minimized, where dist(S, x) := min y∈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 + ϵ) factor in polynomial time when k and ϵ 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.
This paper studies the use of oblivious dimensionality reduction for approximating a point set with a subspace. It gives a sketching and solve algorithm that reduces both the number of points, and the dimension that they are in, to numbers close to the dimensional of the goal subspace. It then empirically demonstrates that the proposed methods perform better than SVDs.  While subspace approximation is important, I’m doubtful of the value of this work for several reasons. First, unlike previous results on oblivious subspace embeddings that introduced new tools, this paper appears to be almost entirely applying existing tools to a mathematically natural variant of the problem. It does not discuss the connections and applications related to this problem. The experiments are also restricted on small synthetic data, and does not compare against natural heuristics such as simulated annealing and local methods. The experiment section also does not discuss the parameters that the projections are invoked with, and the role of table (b) is not very well explained.  Overall, while this paper contains good theoretical ideas, it can benefit from a more thorough set of experiments on practically motivated datasets (although good steps in this direction were taken in the Author Feedback), as well as a more thorough treatment of the importance of the problem studied. On the other hand, due to the fundamental importance of subspace approximation problems in numerical linear algebra, I would not object to this paper appearing.