Low-Rank PSD Approximation in Input-Sparsity Time
Low-Rank PSD Approximation in Input-Sparsity Time
复制标题
DOI：
10.1137/1.9781611974782.134
复制
发表时间：
2017-01
期刊：
影响因子：
--
通讯作者：
K. Clarkson;David P. Woodruff
中科院分区：
文献类型：
--
作者：
K. Clarkson;David P. Woodruff
我们给出了低秩正半定（PSD）矩阵的近似算法。对于对称输入矩阵 A ∈ ℝn × n、目标秩 k 和误差参数 e > 0，一种算法以恒定概率找到秩 k 的 PSD 矩阵 Ỹ，使得 ||A − Ỹ ||F2 ≤ (1 + e) || A − Ak, +||F2，其中 Ak,+ 表示 A 的最佳 k 级 PSD 近似，范数为 Frobenius。该算法需要时间 O(nnz(A) log n) + npoly((logn)k/e) + poly(k/e)，其中 nnz(A) 表示 A 的非零项数，poly(k/e) 表示 k/e 中的多项式。 （时间限制中有两个不同的多项式。）这里输出矩阵 Ỹ 的形式为 CUC⊤，其中 C 的 O(k/e) 列是 A 的列。与之前的工作相比，我们不需要输入矩阵 A 是 PSD，我们的输出是秩 k（不更大），并且我们的运行时间是 O(nnz(A) log n)，前提是它大于 npoly((log n)k/e)。我们给出了一种更快、更简单的类似算法，但其rank-k PSD输出不涉及A的列，并且不要求A是对称的。我们给出了类似的算法，用于受对称性约束的最佳 k 级近似。我们还表明，存在不对称输入矩阵，它们不能具有良好的对称列选择近似值。
We give algorithms for approximation by low-rank positive semidefinite (PSD) matrices. For symmetric input matrix A ∈ ℝn × n, target rank k, and error parameter e > 0, one algorithm finds with constant probability a PSD matrix Ỹ of rank k such that ||A − Ỹ ||F2 ≤ (1 + e) || A − Ak, +||F2, where Ak,+ denotes the best rank-k PSD approximation to A, and the norm is Frobenius. The algorithm takes time O(nnz(A) log n) + npoly((logn)k/e) + poly(k/e), where nnz(A) denotes the number of nonzero entries of A, and poly(k/e) denotes a polynomial in k/e. (There are two different polynomials in the time bound.) Here the output matrix Ỹ has the form CUC⊤, where the O(k/e) columns of C are columns of A. In contrast to prior work, we do not require the input matrix A to be PSD, our output is rank k (not larger), and our running time is O(nnz(A) log n) provided this is larger than npoly((log n)k/e). We give a similar algorithm that is faster and simpler, but whose rank-k PSD output does not involve columns of A, and does not require A to be symmetric. We give similar algorithms for best rank-k approximation subject to the constraint of symmetry. We also show that there are asymmetric input matrices that cannot have good symmetric column-selected approximations.