提出高效更新方法，实时处理数据流中的低秩变化。
Fast and Accurate SVD-Type Updating in Streaming Data
- 用分步分解法分离稀疏与低秩更新，内存减半。
- 基于Givens旋转算法每步仅10次浮点运算，计算量二次增长。
- 适合推荐系统等高吞吐场景，比LAPACK更高效。
对于数据流，短时间内的变化通常具有低秩特性。对于以矩阵形式排列的高吞吐信息，每次更新后重新计算最优SVD近似通常不可行。因此，我们提出一组高效的新型算法，用于更新双对角分解，其精度与SVD方法相当。特别地，我们开发了一种紧凑的Householder型算法，将稀疏部分与低秩更新解耦，内存需求约为标准双对角化方法的一半。第二个基于Givens旋转的算法每旋转仅需约10次浮点运算，计算复杂度随问题规模呈二次增长，而传统方法通常为三次。该算法在处理高吞吐更新时表现优异，我们在推荐系统和网络的大子空间追踪中验证了其有效性，并与LAPACK及增量SVD等知名软件进行了对比。
原文摘要 · Abstract (English)
For a datastream, the change over a short interval is often of low rank. For high throughput information arranged in matrix format, recomputing an optimal SVD approximation after each step is typically prohibitive. Instead, incremental and truncated updating strategies are used, which may not scale for large truncation ranks. Therefore, we propose a set of efficient new algorithms that update a bidiagonal factorization, and which are similarly accurate as the SVD methods. In particular, we develop a compact Householder-type algorithm that decouples a sparse part from a low-rank update and has about half the memory requirements of standard bidiagonalization methods. A second algorithm based on Givens rotations has only about 10 flops per rotation and scales quadratically with the problem size, compared to a typical cubic scaling. The algorithm is therefore effective for processing high-throughput updates, as we demonstrate in tracking large subspaces of recommendation systems and networks, and when compared to well known software such as LAPACK or the incremental SVD.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。