Sublinear Time Eigenvalue Approximation via Random Sampling
Sublinear Time Eigenvalue Approximation via Random Sampling
复制标题
DOI：
10.4230/lipics.icalp.2023.21
复制
发表时间：
2021-09
期刊：
影响因子：
--
通讯作者：
Rajarshi Bhattacharjee;Cameron Musco;Archan Ray
中科院分区：
文献类型：
--
作者：
Rajarshi Bhattacharjee;Cameron Musco;Archan Ray
我们研究了具有有界条目的对称矩阵$ \ mathbf a \ in \ mathbb {r}^{n \ times n} $的对称矩阵的特征的问题（即\ leq 1 $）。我们提出了一个简单的额定时间算法，该算法近似于$ \ mathbf {a} $的所有特征值，然后使用随机采样$ \ tilde {o} \ left（\ frac {\ frac {\ frac {\ frac {\ frac {\ frac {\ frac {\ frac {\ frac {\ frac {\ frac {\ frac {\ frac {\ frac {\ frac {\ frac {\ frac { ^3 n} {\ epsilon^3} \ right）\ times \ tilde o \ left（\ frac {\ log^3 n} {\ epsilon^3} \ right）$ principal subbsatrix。我们的结果可以看作是在随机子序列的完整特征光谱上结合的浓度，仅在单数值（特征值的幅度）上显着扩展了已知界限。我们给出了$ \ pm \ epsilon \ sqrt {\ text {nnz}（\ mathbf {a}）} $和$ \ pm \ epsilon \ | \ mathbf a \ | _f $行，我们给出了改进的错误界限。可以分别以与其稀疏成正比或平方$ \ ell_2 $规范成正比的概率进行采样。这里$ \ text {nnz}（\ mathbf {a}）$是$ \ mathbf {a} $和$ \ | \ | \ mathbf a \ | _f $是其frobenius norm中的$ \ mathbf {a} $中的非零条目的数量。即使对于近似近似值或测试存在大型负特征值的严格问题（Bakshi，Chepurko和Jayaram，focs '20），我们的结果也是第一个利用不均匀抽样来获得改进的误差范围的优势。从技术角度来看，我们的结果需要一些具有有界条目的矩阵的新特征值浓度和扰动界限。我们的非均匀抽样范围需要一种新的算法方法，该方法在计算该子矩阵的特征值之前，明智地将其随机抽样的子序列化的条目降低，以减少差异。我们通过数值模拟来补充理论结果，这证明了我们在实践中算法的有效性。
We study the problem of approximating the eigenspectrum of a symmetric matrix $\mathbf A \in \mathbb{R}^{n \times n}$ with bounded entries (i.e., $\|\mathbf A\|_{\infty} \leq 1$). We present a simple sublinear time algorithm that approximates all eigenvalues of $\mathbf{A}$ up to additive error $\pm \epsilon n$ using those of a randomly sampled $\tilde {O}\left (\frac{\log^3 n}{\epsilon^3}\right ) \times \tilde O\left (\frac{\log^3 n}{\epsilon^3}\right )$ principal submatrix. Our result can be viewed as a concentration bound on the complete eigenspectrum of a random submatrix, significantly extending known bounds on just the singular values (the magnitudes of the eigenvalues). We give improved error bounds of $\pm \epsilon \sqrt{\text{nnz}(\mathbf{A})}$ and $\pm \epsilon \|\mathbf A\|_F$ when the rows of $\mathbf A$ can be sampled with probabilities proportional to their sparsities or their squared $\ell_2$ norms respectively. Here $\text{nnz}(\mathbf{A})$ is the number of non-zero entries in $\mathbf{A}$ and $\|\mathbf A\|_F$ is its Frobenius norm. Even for the strictly easier problems of approximating the singular values or testing the existence of large negative eigenvalues (Bakshi, Chepurko, and Jayaram, FOCS '20), our results are the first that take advantage of non-uniform sampling to give improved error bounds. From a technical perspective, our results require several new eigenvalue concentration and perturbation bounds for matrices with bounded entries. Our non-uniform sampling bounds require a new algorithmic approach, which judiciously zeroes out entries of a randomly sampled submatrix to reduce variance, before computing the eigenvalues of that submatrix as estimates for those of $\mathbf A$. We complement our theoretical results with numerical simulations, which demonstrate the effectiveness of our algorithms in practice.