提出新方法加速低秩矩阵近似，提升迭代求解速度。
What is a Sketch-and-Precondition Derivation for Low-Rank Approximation? Inverse Power Error or Inverse Power Estimation?
- 用随机投影构建预条件器，改进迭代算法收敛性。
- 收敛速度随采样规模线性提升，理论保证明确。
- 适合大规模矩阵计算，尤其对低秩近似有效。
随机投影可降低大规模数值线性代数的计算复杂度。传统‘投影-求解’方法直接通过投影缩小问题规模，而‘投影-预条件’方法利用投影构造计算友好的预条件器，从而加快原始问题上迭代求解器的收敛速度，并保持全空间精度。此外，求解器的收敛速率至少随投影规模线性提升。尽管潜力巨大，将投影-预条件框架应用于随机低秩矩阵近似仍是一个开放挑战。本文提出基于拉格朗日形式的误差驱动投影牛顿迭代（EPSI）方法，作为随机低秩近似的投影-预条件变体。该方法具备理论保证，其收敛速度至少随投影大小线性改善。
原文摘要 · Abstract (English)
Randomized sketching accelerates large-scale numerical linear algebra by reducing computational complexity. While the traditional sketch-and-solve approach reduces the problem size directly through sketching, the sketch-and-precondition method leverages sketching to construct a computational friendly preconditioner. This preconditioner improves the convergence speed of iterative solvers applied to the original problem, maintaining accuracy in the full space. Furthermore, the convergence rate of the solver improves at least linearly with the sketch size. Despite its potential, developing a sketch-and-precondition framework for randomized algorithms in low-rank matrix approximation remains an open challenge. We introduce the Error-Powered Sketched Inverse Iteration (EPSI) Method via run sketched Newton iteration for the Lagrange form as a sketch-and-precondition variant for randomized low-rank approximation. Our method achieves theoretical guarantees, including a convergence rate that improves at least linearly with the sketch size.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。