提出快速采样算法，可在亚线性时间内对半正定矩阵列进行平方范数采样。
Fast Length-Squared Sampling for Positive-Semidefinite Matrices
- 基于拒绝采样，用O(n)期望时间实现列的平方范数采样。
- 在半正定矩阵上，采样速度比输入规模还快，且为理论最优。
- 适用于低秩逼近、范数估计等场景，简化复杂算法设计。
我们提出一种基于拒绝采样的简单算法，用于对n×n半正定（psd）矩阵进行长度平方采样：即按列的ℓ₂-范数平方概率采样。该算法期望运行时间为O(n)，远低于输入矩阵大小的线性时间，且在输入为对角矩阵时仍为最优。该结果有多个应用：长度平方采样常用于子线性时间矩阵算法（如低秩近似和特征值估计），通常假设可直接获取列范数以高效采样。我们的结果表明，至少对半正定矩阵，这一假设可被移除。我们还讨论了其在相对误差下估计psd矩阵Frobenius范数的渐近最优算法中的应用。最后，该采样算法可导出一个极简的子线性时间算法，解决Bakshi等人（FOCS, 2020）提出的鲁棒半正定低秩逼近问题，性能几乎与原复杂方法相当。
原文摘要 · Abstract (English)
We describe a simple rejection-sampling-based algorithm to perform length-squared sampling on an $n \times n$ positive-semidefinite (psd) matrix: that is, to sample a column with probability proportional to its squared $\ell_2$-norm. The algorithm runs in just $O(n)$ expected time, which is significantly sublinear in the input matrix size. The runtime is optimal, even when the input is assumed to be diagonal. Our result has several applications. Length-squared sampling is used by a number of sublinear time algorithms for matrix problems, like low-rank approximation and eigenvalue approximation. Often, it is assumed that the algorithm is given access to the matrix column norms, and thus can perform length-squared sampling efficiently. Our result shows that, at least for psd matrices, we can remove this assumption. We also discuss an application to an asymptotically optimal algorithm for estimating the Frobenius norm of a psd matrix to relative error. Finally, we show that our sampling algorithm yields a very simple sublinear time algorithm for the robust psd low-rank approximation problem introduced by Bakshi et al. (FOCS, 2020), which nearly matches the more complex method developed there.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。