Near-Optimal Coresets for Least-Squares Regression
- 9 July 2013
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 59 (10), 6880-6892
- https://doi.org/10.1109/tit.2013.2272457
Abstract
We study the (constrained) least-squares regression as well as multiple response least-squares regression and ask the question of whether a subset of the data, a coreset, suffices to compute a good approximate solution to the regression. We give deterministic, low-order polynomial-time algorithms to construct such coresets with approximation guarantees, together with lower bounds indicating that there is not much room for improvement upon our results.Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Near Optimal Column-Based Matrix ReconstructionPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2011
- Twice-ramanujan sparsifiersPublished by Association for Computing Machinery (ACM) ,2009
- Random projections for the nonnegative least-squares problemLinear Algebra and its Applications, 2009
- Relative-Error $CUR$ Matrix DecompositionsSIAM Journal on Matrix Analysis and Applications, 2008
- Sampling from large matricesJournal of the ACM, 2007
- Solutions and optimality criteria to box constrained nonconvex minimization problemsJournal of Industrial & Management Optimization, 2007
- An interior point Newton‐like method for non‐negative least‐squares problems with degenerate solutionNumerical Linear Algebra with Applications, 2006
- An Introduction to Support Vector Machines and Other Kernel-based Learning MethodsPublished by Cambridge University Press (CUP) ,2000
- 10.1162/153244303322753616Applied Physics Letters, 2000
- Predicting Multivariate Responses in Multiple Linear RegressionJournal of the Royal Statistical Society Series B: Statistical Methodology, 1997