Abstract

The problem of discovering the hidden low dimensional structure in high dimensional data arises in various scenarios. We consider here a classical and simple algorithmic formulation of the problem: given a set P of n points in d-dimensional Euclidean space, and an integer k between 1 and d, find the k-dimensional subspace that best fits the point set P. In many settings, the fit of a subspace is defined to be the sum of of the squares of the distances of points in P to the subspace; here we define the fit to be the sum of the distances of points in P to the subspace. We imagine k to be small compared to d.

We obtain approximation algorithms for the problem with running time linear in n*d and exponential in k. We present a dimension reduction result that has one such algorithm as a consequence -- we can, in time that is linear in n*d and polynomial in k, compute a subspace V of dimension polynomial in k such that it suffices to search for the best k-subspace in V.