Abstract | ||
---|---|---|
The subspace approximation problem Subspace(k, p) asks for a k dimensional linear subspace that fits a given set of m points in Rn optimally. The error for fitting is a generalization of the least squares fit and uses the lp norm of the distances (l2 distances) of the points from the subspace, e.g., p = ∞ means minimizing the l2 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]. |
Year | DOI | Venue |
---|---|---|
2009 | 10.5555/2133036.2133075 | Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms |
Keywords | Field | DocType |
convex programming,subspace approximation problem,farthest point,rn optimally,previous work,l2 distance,subspace approximation,m point,k dimensional linear subspace,unique games,constant k,lp norm,approximation algorithms,least square,leader election,randomized algorithms,distributed computing | Least squares,Krylov subspace,Leader election,Randomized algorithm,Discrete mathematics,Combinatorics,Subspace topology,Lp space,Linear subspace,Mathematics | Journal |
Volume | ISBN | Citations |
abs/0912.1 | 978-1-61197-251-1 | 18 |
PageRank | References | Authors |
0.91 | 22 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Amit Deshpande | 1 | 676 | 40.91 |
Madhur Tulsiani | 2 | 358 | 24.60 |
Nisheeth K. Vishnoi | 3 | 592 | 61.14 |