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.
In the recent decades numerous approximation and data summarization algorithms were suggested to the covariance matrix or its singular values. This is by computing a small matrix @math whose covariance @math approximates, in some sense, the covariance matrix @math of the input data @math . The term is usually used when @math is a weighted (scaled) subset of rows from the @math rows of the input matrix. The matrix @math is sometimes called a if each rows in @math is a linear combination of few or all its rows, i.e. @math for some matrix @math . However, those coresets and sketches usually yield @math -multiplicative approximations for @math by @math where the matrix @math is of @math rows and @math may be any vector, or the smallest largest singular vector of @math or @math ; see lower bounds in @cite_9 . Moreover, a @math -approximation to @math by @math does not guarantee an approximation to the actual entries or eigenvectors of @math by @math that may be very different; see @cite_37 .
@cite_9 @cite_37
2089784543 2043804332
We consider the problem of approximating a set P of η points in Rd by a j-dimensional subspace under the lp measure, in which we wish to minimize the sum of lp distances from each point of P to this subspace. More generally, the Fq (lp)-subspace approximation problem asks for a j-subspace that minimizes the sum of qth powers of lp-distances to this subspace, up to a multiplicative factor of (1 + e). We develop techniques for subspace approximation, regression, and matrix approximation that can be used to deal with massive data sets in high dimensional spaces. In particular, we develop coresets and sketches, i.e. small space representations that approximate the input point set P with respect to the subspace approximation problem. Our results are: • A dimensionality reduction method that can be applied to Fq (lp)-clustering and shape fitting problems, such as those in [8, 15]. • The first strong coreset for F1 (l2)-subspace approximation in high-dimensional spaces, i.e. of size polynomial in the dimension of the space. This coreset approximates the distances to any j-subspace (not just the optimal one). • A (1 + e)-approximation algorithm for the j-dimensional F1 (l2)-subspace approximation problem with running time ηd(j e)O(1) + (η + d)2poly(j e). • A streaming algorithm that maintains a coreset for the F1 (l2)-subspace approximation problem and uses a space of d [EQUATION] (weighted) points. • Streaming algorithms for the above problems with bounded precision in the turnstile model, i.e, when coordinates appear in an arbitrary order and undergo multiple updates. We show that bounded precision can lead to further improvements. We extend results of [7] for approximate linear regression, distances to subspace approximation, and optimal rank-j approximation, to error measures other than the Frobenius norm. We present and analyze a sampling algorithm for the basic linear-algebraic problem of l 2 regression. The l 2 regression (or least-squares fit) problem takes as input a matrix A ∈ Rn×d (where we assume n G d) and a target vector b ∈ Rn, and it returns as output Z = min x∈Rd |b - Ax| 2 . Also of interest is x opt = A+b, where A+ is the Moore-Penrose generalized inverse, which is the minimum-length vector achieving the minimum. Our algorithm randomly samples r rows from the matrix A and vector b to construct an induced l 2 regression problem with many fewer rows, but with the same number of columns. A crucial feature of the algorithm is the nonuniform sampling probabilities. These probabilities depend in a sophisticated manner on the lengths, i.e., the Euclidean norms, of the rows of the left singular vectors of A and the manner in which b lies in the complement of the column space of A. Under appropriate assumptions, we show relative error approximations for both Z and x opt . Applications of this sampling methodology are briefly discussed.