Input-Sparsity Low Rank Approximation in Schatten Norm
Input-Sparsity Low Rank Approximation in Schatten Norm
复制标题
DOI：
--
复制
发表时间：
2020-04
期刊：
影响因子：
--
通讯作者：
Yi Li;David P. Woodruff
中科院分区：
文献类型：
--
作者：
Yi Li;David P. Woodruff
在每个Schatten范数下，我们给出了RANK-$K$低阶逼近问题的第一个输入稀疏时间算法。具体地说，对于给定的$n次n$矩阵$A$，我们的算法计算$Y，Z\in{R}^{n\次k}$，它以很高的概率满足$A-YZ^T_p\leq(1+epsilon)A-A_k_p$，其中$M_p=\Left(sum_i=1^n\sigma_i(M)^p\right)^{1/p}$是矩阵$M$的Schatten$p$-范数\Sigma_n(M)$，其中$A_k$是$A$的最佳秩-$k$逼近。该算法的运行时间为[1，2]中$p的$αp=0$，$p>；2$的$αp=(omega-1)(1-2/p)$，其中$omega约2.374$是矩阵乘法的指数。对于重要的情况$p=1$，它对应于更“稳健”的核范数，我们得到了${O}(算子名{nnz}(A)+m\cot\算子名{polon}(k/\epsilon))$time，它以前只知道Frobenius范数($p=2$).此外，由于对于每$p$，我们的算法对$n$的依赖性比奇异值分解对$n$的依赖程度更好。我们的分析的关键是对Ky-Fan$p$-范数使用降维。
We give the first input-sparsity time algorithms for the rank-$k$ low rank approximation problem in every Schatten norm. Specifically, for a given $n\times n$ matrix $A$, our algorithm computes $Y,Z\in \mathbb{R}^{n\times k}$, which, with high probability, satisfy $\|A-YZ^T\|_p \leq (1+\epsilon)\|A-A_k\|_p$, where $\|M\|_p = \left (\sum_{i=1}^n \sigma_i(M)^p \right )^{1/p}$ is the Schatten $p$-norm of a matrix $M$ with singular values $\sigma_1(M), \ldots, \sigma_n(M)$, and where $A_k$ is the best rank-$k$ approximation to $A$. Our algorithm runs in time $\tilde{O}(\operatorname{nnz}(A) + mn^{\alpha_p}\operatorname{poly}(k/\epsilon))$, where $\alpha_p = 0$ for $p\in [1,2)$ and $\alpha_p = (\omega-1)(1-2/p)$ for $p>2$ and $\omega \approx 2.374$ is the exponent of matrix multiplication. For the important case of $p = 1$, which corresponds to the more "robust" nuclear norm, we obtain $\tilde{O}(\operatorname{nnz}(A) + m \cdot \operatorname{poly}(k/\epsilon))$ time, which was previously only known for the Frobenius norm ($p = 2$). Moreover, since $\alpha_p < \omega - 1$ for every $p$, our algorithm has a better dependence on $n$ than that in the singular value decomposition for every $p$. Crucial to our analysis is the use of dimensionality reduction for Ky-Fan $p$-norms.