Matrix Norms in Data Streams: Faster, Multi-Pass and Row-Order
Matrix Norms in Data Streams: Faster, Multi-Pass and Row-Order
复制标题
DOI：
--
复制
发表时间：
2016-09
期刊：
影响因子：
--
通讯作者：
V. Braverman;Stephen R. Chestnut;Robert Krauthgamer;Yi Li;David P. Woodruff;Lin F. Yang
中科院分区：
文献类型：
--
作者：
V. Braverman;Stephen R. Chestnut;Robert Krauthgamer;Yi Li;David P. Woodruff;Lin F. Yang
数据流中的一个中心问题是表征潜在频率向量的哪些函数可以有效地近似。最近已经有相当大的努力，在扩展这个问题的估计函数的矩阵，作为一个数据流。这种设置将经典问题推广到矩阵的类似问题。例如，我们现在希望估计“频繁方向”计数，而不是估计频繁项计数。一个相关的例子是估计范数，现在对应于估计矩阵奇异值的向量范数。尽管最近的努力，目前的理解，这样的矩阵问题是相当弱的向量问题。我们研究了在流中估计矩阵范数的许多方面，这些方面以前没有被考虑过：（1）多遍算法，（2）一次一行地看到底层矩阵的算法，以及（3）时间有效的算法。我们的多通道和行顺序算法使用的内存比单通道和入口更新模型中可证明需要的内存少，因此可以在这些模型之间进行分离（就内存而言）。此外，我们所有的算法都比以前的算法快得多。我们还证明了一些下界，并获得例如，一个近乎完整的表征所需的内存行顺序算法估计Schatten $p$-规范的稀疏矩阵。
A central problem in data streams is to characterize which functions of an underlying frequency vector can be approximated efficiently. Recently there has been considerable effort in extending this problem to that of estimating functions of a matrix that is presented as a data-stream. This setting generalizes classical problems to the analogous ones for matrices. For example, instead of estimating frequent-item counts, we now wish to estimate "frequent-direction" counts. A related example is to estimate norms, which now correspond to estimating a vector norm on the singular values of the matrix. Despite recent efforts, the current understanding for such matrix problems is considerably weaker than that for vector problems. We study a number of aspects of estimating matrix norms in a stream that have not previously been considered: (1) multi-pass algorithms, (2) algorithms that see the underlying matrix one row at a time, and (3) time-efficient algorithms. Our multi-pass and row-order algorithms use less memory than what is provably required in the single-pass and entrywise-update models, and thus give separations between these models (in terms of memory). Moreover, all of our algorithms are considerably faster than previous ones. We also prove a number of lower bounds, and obtain for instance, a near-complete characterization of the memory required of row-order algorithms for estimating Schatten $p$-norms of sparse matrices.