论文标题
近距离进入数值稀疏矩阵的采样
Near-Optimal Entrywise Sampling of Numerically Sparse Matrices
论文作者
论文摘要
许多真实的数据集稀疏或几乎稀疏。用于矩阵$ a \ in \ mathbb {r}^{n \ times n} $的一种方法是\ emph {数值稀疏}，表示为$ \ m athsf {ns}（ns}（a）$，定义为最低$ $ k \ geq 1 $ \ | \ sqrt {k} $对于每个行，每个列$ a $ a $ a $。 $ a $的量度平滑，显然仅小于行/列$ a $中的非零件数量。 Achlioptas和McSherry [2007]的开创性工作提出了一个问题，即通过进入采样近似输入矩阵$ a $。更准确地说，目标是快速计算满足$ \ | a} $满足$ \ | a - \ tilde {a} \ | _2 \ | _2 \ | _2 \ leqleqε\ | a \ | a \ | _2 $（即，给定添加频谱近似）给定错误参数$ 0 $ 0 $ε> 0 $ 0。已知的方案样本并重新订阅了一小部分条目，价格为$ a $。我们提出了一个计划，该方案将几乎是一个矩阵$ a $ a $ - 它产生矩阵$ \ tilde {a} $，并使用$ O（ε^{ - 2} \ Mathsf {ns}（a）\ cdot n \ ln n \ ln n n n \ ln n）$ non-Zero erenties具有很高的可能性。我们还证明，这种上限在$ \ mathsf {nnz}（\ tilde {a}）$上是\ emph {tight}到对数因素。此外，当$ a $衰减的频谱迅速衰减时，我们的上限会有所改善（大约用$ n $代替$ n $ $ a $）。当给出$ \ | a \ | _2 $时，我们的方案可以在时间$ o（\ Mathsf {nnz}（a））$中实现。以前，通过Achlioptas等获得了类似的上限。 AL [2013]，但仅用于限制类别的投入类别，甚至不包括对称或协方差矩阵。最后，我们演示了这些采样技术的两种应用，以更快地近似矩阵乘法，并使用稀疏的预处理器进行脊回归。
Many real-world data sets are sparse or almost sparse. One method to measure this for a matrix $A\in \mathbb{R}^{n\times n}$ is the \emph{numerical sparsity}, denoted $\mathsf{ns}(A)$, defined as the minimum $k\geq 1$ such that $\|a\|_1/\|a\|_2 \leq \sqrt{k}$ for every row and every column $a$ of $A$. This measure of $a$ is smooth and is clearly only smaller than the number of non-zeros in the row/column $a$. The seminal work of Achlioptas and McSherry [2007] has put forward the question of approximating an input matrix $A$ by entrywise sampling. More precisely, the goal is to quickly compute a sparse matrix $\tilde{A}$ satisfying $\|A - \tilde{A}\|_2 \leq ε\|A\|_2$ (i.e., additive spectral approximation) given an error parameter $ε>0$. The known schemes sample and rescale a small fraction of entries from $A$. We propose a scheme that sparsifies an almost-sparse matrix $A$ -- it produces a matrix $\tilde{A}$ with $O(ε^{-2}\mathsf{ns}(A) \cdot n\ln n)$ non-zero entries with high probability. We also prove that this upper bound on $\mathsf{nnz}(\tilde{A})$ is \emph{tight} up to logarithmic factors. Moreover, our upper bound improves when the spectrum of $A$ decays quickly (roughly replacing $n$ with the stable rank of $A$). Our scheme can be implemented in time $O(\mathsf{nnz}(A))$ when $\|A\|_2$ is given. Previously, a similar upper bound was obtained by Achlioptas et. al [2013] but only for a restricted class of inputs that does not even include symmetric or covariance matrices. Finally, we demonstrate two applications of these sampling techniques, to faster approximate matrix multiplication, and to ridge regression by using sparse preconditioners.
