通过延迟计算提升约翰椭球的计算速度
John Ellipsoids via Lazy Updates
- 用采样延迟高精度杠杆率计算，减少重复开销
- 结合快速矩形矩阵乘法批量处理杠杆率，提速显著
- 适合大规模数据流场景，内存占用低
我们提出一种更快的算法，用于在 d 维空间中对 n 个点计算近似约翰椭球。已有最优算法依赖于反复计算点的杠杆率并据此重加权 [CCLY19]。本文通过使用采样延迟高精度杠杆率的计算，并随后利用快速矩形矩阵乘法批量计算多组高精度杠杆率，显著加速了该过程。此外，我们还基于类似思想设计了低空间消耗的流式约翰椭球算法。
原文摘要 · Abstract (English)
We give a faster algorithm for computing an approximate John ellipsoid around $n$ points in $d$ dimensions. The best known prior algorithms are based on repeatedly computing the leverage scores of the points and reweighting them by these scores [CCLY19]. We show that this algorithm can be substantially sped up by delaying the computation of high accuracy leverage scores by using sampling, and then later computing multiple batches of high accuracy leverage scores via fast rectangular matrix multiplication. We also give low-space streaming algorithms for John ellipsoids using similar ideas.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。