Approximating the Top Eigenvector in Random Order Streams

The paper studies the problem of finding the top eigenvector of a matrix in the streaming model. The problem is: given a sequence of d-dimensional rows a_1, a_2, ..., a_n of a matrix A, approximately compute the top eigenvector v_1 of A^TA. The algorithms gets a single pass over the stream of input rows, must use subquadratic (in d) space, and should output an approximation \hat v_1 to v_1.

Existing works on this problem have the following natural idea at their core: initialize a vector z\in R^d to be zero, and then, upon receiving a row a_i, set z\gets z+ \eta a_i^T z a_i for some learning rate \eta. One can either keep a fixed learning rate, or use a combination: the latter is done in Price's algorithm from a few years ago, which computes an approximation \hat v_1 that is at least 1-O(log d/R) correlated with v_1, where R is the eigenvalue gap \sigma_2(A^TA)/\sigma_1(A^TA). Price also showed that a 1-O(1/R^2) correlation requires almost quadratic in d space.

The author(s) result is that in random streams, the correlation bound can be improved to 1-O(1/\sqrt{R}). They complement their algorithmic result with a lower bound for Price's algorithm -- this is basically an adaptation of Price's lower bound to random order streams. They also provide certain impossibility results for fixed rate Oja's algorithm.

The main algorithmic technique is clean. The main point is that the fact that the stream is randomly ordered implies that its substreams contain good spectral approximations to the original matrix -- this is by standard spectral concentration bounds (after removing heavy entries). Due to the spectral gap assumption the top eigenvectors of these rescaled submatrices are close to v_1. Thus, one can run the power method on the substreams, of which there are quite a few. Thus, a good convergence can be obtained.

The paper studies the problem of approximating the top eigenvector of $A^T A$ when rows of an $n \times d$ matrix $A$ are given in a stream. The authors consider worst-case inputs $A$ but assume the rows are presented in a uniformly random order. They show that when the gap parameter $R = \sigma_1(A)^2 / \sigma_2(A)^2 = \Omega(1)$, there is a randomized algorithm using $O(h \cdot d \cdot \text{polylog}(d))$ bits of space that outputs a unit vector $v$ with correlation $1 - O(1/\sqrt{R})$ with the top eigenvector $v_1$. Here, $h$ denotes the number of "heavy rows" in the matrix, defined as rows with Euclidean norm at least $|A|_F / \sqrt{d \cdot \text{polylog}(d)}$. The authors provide a lower bound showing that any algorithm using $O(hd/R)$ bits of space can obtain at most $1 - \Omega(1/R^2)$ correlation with the top eigenvector. Their results improve upon the $R = \Omega(\log n \cdot \log d)$ requirement in a recent work by Price. The authors' algorithm is based on a variant of the block power method. They also show improvements to the gap requirements in Price's analysis for both arbitrary order and random order streams. The techniques involve row sampling, concentration inequalities, and careful analysis of the power method with approximate quadratic forms.

This paper is concerned with estimating a direction that is well-correlated with the top eigenvector $v_1$ of a matrix where the rows $a_1, \dots, a_n$ are streamed to us in uniformly random order. To make this well-defined, a gap assumption is required, i.e., that $R \coloneqq \lambda_1(A^{\top}A)/\lambda_2(A^{\top}A) \gg 1$. A successful algorithm is one that returns an estimate vector that is $1 - o_{R}(1)$ correlated with $v_1$ while using at most $\widetilde{O}(d)$ space. Note that if we are allowed to use $d^2$ space, then the problem is trivial, as we can simply maintain $A^{\top}A$. Thus, one of the main challenges is to figure out how to estimate $v_1$ when we are not allowed to remember too many of the rows we have seen so far.

The main result is an algorithm that uses $\widetilde{O}(hd)$ space and outputs a unit vector $u$ such that $\langle u, v_1 \rangle \ge 1-C/\sqrt{R}$ for some universal constant $C$, and where $h$ denotes the number of "heavy" rows (those that contribute at least a $\sim 1/d$ fraction to the Frobenius norm of $A$). This dependence on $h$ is essentially optimal, as the authors give a lower bound saying that any algorithm that outputs a vector with at least $1-1/R^2$ correlation must use $hd/R$ space.

The main technical contribution is to observe that if the rows of $A$ are randomly permuted and streamed to us, then in some sense, we can see $\sim \log d$ spectral approximations to $A$ in disjoint contiguous windows of the stream. Thus, the power method can be simulated by adding $a_i\langle a_i, u \rangle$ to the estimate in each round. To actually form the spectral approximations and implement this with low space, the authors use a row sampling result which says that one only needs to choose and reweight $\sim \rho/\varepsilon^2$ rows of $A$ to form a decent spectral approximation to $A$, where $\rho$ denotes the stable rank of $A$. So, the authors use the row sampling result to form $\log d$ many spectral approximations to $A$ and then simulate the power method on these approximations. The final result follows from showing that the top eigenvector of the spectral approximations is reasonably well correlated with the top eigenvector of $A$, which itself follows from standard eigenvector perturbation tools and the gap assumption.

Although this does not immediately work for heavy rows (e.g. consider a more difficult scenario where there is one row orthogonal to all the other rows in the matrix, it has large norm, and it witnesses $v_1$, then we must remember it), the simple fix is to just identify heavy rows on the fly and store those exactly. As mentioned earlier, this linear dependence on the number of heavy rows is necessary.

Given a stream of $n$ data-points $a_1, a_2, \dots, a_n \in \mathbb{R}^d$, this paper studies the problem of approximating the top eigen-vector of the matrix $A^T A$ at the end of the stream, where $A \in \mathbb{R}^{n \times d}$ is the data-matrix with rows of the matrix corresponding to the data-points. This is the same problem as approximating the first principal component in PCA. Prior work on this problem by Price (2023) gave an algorithm that works with some worst-case guarantees i.e. both the data-points and the order of the data-points can be chosen by the adversary. This paper is the first to study the setting where although the data-points can be chosen arbitrarily by the adversary, the order of arrival of the data-points is uniformly at random. For this setting, the paper provides an algorithm with improved guarantees over the algorithm by Price. Additionally, they also provide a lower bound for streaming algorithms for the random-order arrival model.

This paper studies the problem of approximating the top eigenvector of the matrix in the random order data stream model. Both upper and lower bounds are provided.

All reviewers agreed that the problem studied is natural, and that the random order stream is a reasonable model for obtaining more optimistic results. It is also very nice that the space complexity of the proposed algorithm is nearly optimal.