The subspace approximation problem Subspace(k, p) asks for a k dimensional linear subspace that fits a given set of m points in R n optimally. The error for fitting is a generalization of the least squares fit and uses the p norm of the distances ( 2 distances) of the points from the subspace, e.g., p = ∞ means minimizing the 2 distance of the farthest point from the subspace. Previous work on subspace approximation considers either the case of small or constant k and p [27, 11, 14] or the case of p = ∞ [16, 8, 17, 7, 24, 23, 29] . In this paper, we study the algorithms and hardness for Subspace(k, p) in the natural range 1 ≤ k ≤ n and 2 ≤ p ≤ ∞. Our results are as follows. • Extending the convex relaxation and rounding techniques of Varadarajan, Venkatesh, Ye and Zhang [29], we give a polynomial time approximation algorithm for Subspace(k, p), for any k and any p ≥ 2, with an approximation guarantee of roughly √ 2γ p , where γ p ≈ p/e(1 + o(1)) is the p th moment of a standard normal variable. This improves to γ p for k = n − 1. • We exhibit a simple integrality gap (or "rank gap") instance for our convex relaxation giving a gap of γ p (1 − ε), for any constant ε > 0. • We show that, assuming the Unique Games Conjecture, the subspace approximation problem is hard to approximate within a factor better than γ p (1 − ε), for any constant ε > 0. Our hardness reduction involves a dictatorship test which is somewhat different from "long code" based tests used in reductions from Unique Games, and seems better suited for problems of a continuous nature.
Recently, REF study the problem of finding the best k-dimensional subspace approximation to a set of points, where one wishes to minimize the p distances to the subspace.
Algorithms and hardness for subspace approximation
SODA '11
Mathematics Computer Science