2020/02/15 by Vladimir Braverman, Dan Feldman, Braverman, Vladimir +8
Computer Science · Engineering · #Machine Learning and Algorithms #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #cs.DS
paper · pdf · doi:10.48550/arxiv.2002.06296
arxiv created 2020/11/26 · arxiv updated 2020/11/30
In streaming Singular Value Decomposition (SVD), d-dimensional rows of a possibly infinite matrix arrive sequentially as points in ℝd. An ε-coreset is a (much smaller) matrix whose sum of square distances of the rows to any hyperplane approximates that of the original matrix to a 1 ± ε factor. Our main result is that we can maintain a ε-coreset while storing only O(d log2 d / ε2) rows. Known lower bounds of Ω(d / ε2) rows show that this is nearly optimal. Moreover, each row of our coreset is a weighted subset of the input rows. This is highly desirable since it: (1) preserves sparsity; (2) is easily interpretable; (3) avoids precision errors; (4) applies to problems with constraints on the input. Previous streaming results for SVD that return a subset of the input required storing Ω(d log3 n / ε2) rows where n is the number of rows seen so far. Our algorithm, with storage independent of n, is the first result that uses finite memory on infinite streams. We support our findings with experiments on the Wikipedia dataset benchmarked against state-of-the-art algorithms.