For any matrix A in R^(m x n) of rank \rho, we present a probability
distribution over the entries of A (the element-wise leverage scores of
equation (2)) that reveals the most influential entries in the matrix. From a
theoretical perspective, we prove that sampling at most s = O ((m +
本文提出了一种新的随机算法,该算法采用特别偏向采样的方法,使误差最小化,可以在光谱范数下利用输入稀疏性生成 M 的秩 - r 逼近,并具有 better dependence on error ε,是一种高度可并行化的优化方法。此外,本论文探讨了计算两个给定矩阵的积的小秩逼近的新方法和小通信开销的改进算法。