Algorithms and Hardness for Subspace Approximation

Details Algorithms and Hardness for Subspace Approximation Algorithms and Hardness for Subspace Approximation

2009-12-08

arxiv.org/abs/0912.1403v2

Computer Science

Data Structures and Algorithms

Scientific paper

The subspace approximation problem Subspace($k$,$p$) asks for a $k$-dimensional linear subspace that fits a given set of points optimally, where the error for fitting is a generalization of the least squares fit and uses the $\ell_{p}$ norm instead. Most of the previous work on subspace approximation has focused on small or constant $k$ and $p$, using coresets and sampling techniques from computational geometry. In this paper, extending another line of work based on convex relaxation and rounding, we give a polynomial time algorithm, \emph{for any $k$ and any $p \geq 2$}, with the approximation guarantee roughly $\gamma_{p} \sqrt{2 - \frac{1}{n-k}}$, where $\gamma_{p}$ is the $p$-th moment of a standard normal random variable N(0,1). We show that the convex relaxation we use has an integrality gap (or "rank gap") of $\gamma_{p} (1 - \epsilon)$, for any constant $\epsilon > 0$. Finally, we show that assuming the Unique Games Conjecture, the subspace approximation problem is hard to approximate within a factor better than $\gamma_{p} (1 - \epsilon)$, for any constant $\epsilon > 0$.

Affiliated with

Also associated with

No associations

Rating

Algorithms and Hardness for Subspace Approximation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Algorithms and Hardness for Subspace Approximation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algorithms and Hardness for Subspace Approximation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-385404