2024/12/16 by Praneeth Kacham, David P. Woodruff, Kacham, Praneeth +1 · 1 citation
Computer Science · #Data Stream Mining Techniques #Advanced Data Compression Techniques #Neural Networks and Applications
paper · pdf · doi:10.48550/arxiv.2412.11963
When rows of an n × d matrix A are given in a stream, we study algorithms for approximating the top eigenvector of the matrix ATA (equivalently, the top right singular vector of A). We consider worst case inputs A but assume that the rows are presented to the streaming algorithm in a uniformly random order. We show that when the gap parameter R = σ1(A)2/σ2(A)2 = Ω(1), then there is a randomized algorithm that uses O(h ⋅ d ⋅ polylog(d)) bits of space and outputs a unit vector v that has a correlation 1 - O(1/√(R)) with the top eigenvector v1. Here h denotes the number of heavy rows in the matrix, defined as the rows with Euclidean norm at least ‖A‖F/√(d ⋅ polylog(d)). We also provide a lower bound showing that any algorithm using O(hd/R) bits of space can obtain at most 1 - Ω(1/R2) correlation with the top eigenvector. Thus, parameterizing the space complexity in terms of the number of heavy rows is necessary for high accuracy solutions. Our results improve upon the R = Ω(log n ⋅ log d) requirement in a recent work of Price and Xun (FOCS 2024). We note that the algorithm of Price and Xun works for arbitrary order streams whereas our algorithm requires a stronger assumption that the rows are presented in a uniformly random order. We additionally show that the gap requirements in their analysis can be brought down to R = Ω(log2 d) for arbitrary order streams and R = Ω(log d) for random order streams. The requirement of R = Ω(log d) for random order streams is nearly tight for their analysis as we obtain a simple instance with R = Ω(log d/loglog d) for which their algorithm, with any fixed learning rate, cannot output a vector approximating the top eigenvector v1.