Fast Subspace Approximation Via Greedy Least-Squares

In this note, we develop fast and deterministic dimensionality reduction techniques for a family of subspace approximation problems. We then utilize these dimensionality reduction techniques to help rapidly and accurately approximate the n-widths of point sets. Let (Formula presented.) be a given set of M points. The techniques developed herein find an O(nlogM)-dimensional subspace that is guaranteed to always contain a near-best fit n-dimensional hyperplane H for P with respect to the cumulative projection error (Formula presented.), for any chosen p>2. The deterministic algorithm runs in (Formula presented.)-time, and can be randomized to run in only (Formula presented.)-time while maintaining its error guarantees with high probability. In the important p=∞ case, the dimensionality reduction techniques are then combined with efficient algorithms for computing the John ellipsoid of a data set in order to produce an n-dimensional subspace whose maximum ℓ2-distance to any point in the convex hull of P is minimized. The resulting algorithm remains in (Formula presented.)-time.