Least-mean squares (LMS) solvers such as Linear Ridge Lasso-Regression, SVD and Elastic-Net not only solve fundamental machine learning problems, but are also the building blocks in a variety of other methods, such as decision trees and matrix factorizations. We suggest an algorithm that gets a finite set of @math @math -dimensional real vectors and returns a weighted subset of @math vectors whose sum is the same. The proof in Caratheodory's Theorem (1907) computes such a subset in @math time and thus not used in practice. Our algorithm computes this subset in @math time, using @math calls to Caratheodory's construction on small but "smart" subsets. This is based on a novel paradigm of fusion between different data summarization techniques, known as sketches and coresets. As an example application, we show how it can be used to boost the performance of existing LMS solvers, such as those in scikit-learn library, up to x100. Generalization for streaming and distributed (big) data is trivial. Extensive experimental results and complete open source code are also provided.
We present a general technique for approximating various descriptors of the extent of a set P of n points in Rd when the dimension d is an arbitrary fixed constant. For a given extent measure μ and a parameter e > 0, it computes in time O(n + 1 eO(1)) a subset Q ⊆ P of size 1 eO(1), with the property that (1 − e)μ(P) ≤ μ(Q) ≤ μ(P). The specific applications of our technique include e-approximation algorithms for (i) computing diameter, width, and smallest bounding box, ball, and cylinder of P, (ii) maintaining all the previous measures for a set of moving points, and (iii) fitting spheres and cylinders through a point set P. Our algorithms are considerably simpler, and faster in many cases, than previously known algorithms.