We consider the problem of selecting non-zero entries of a matrix $A$ in
order to produce a sparse sketch of it, $B$, that minimizes $\|A-B\|_2$. For
large $m \times n$ matrices, such that $n \gg m$ (for example, representing $n$
observations over $m$ attributes) we give sampling distributions that exhibit
four important properties. First, they have closed f
通过对两个 m 维变量的光滑函数进行采样生成的矩阵的低秩逼近是本文关注的重点。我们否定了先前文献中对一个特定类别的解析函数所提出的论点，即这些矩阵可以独立于 m 具有准确的逐个元素的秩逼近。我们在理论上解释了支持该论点的数值结果，并描述了三个更窄的函数类别，其中 n×n 由函数生成的矩阵可以在与维度 m 无关的情况下以 O (log (n)ε^(-2) polylog (ε^(-1))) 的逐个元素误差逼近。我们还将我们的论点扩展到了由 m 维变量的多线性积生成的张量的低秩张量列逼近。我们在 Transformer 神经网络的注意力低秩逼近的背景下讨论了我们的结果。