论文标题
改进的概括和学习数据驱动的低级近似值的稀疏模式的学习
Improved Generalization Bound and Learning of Sparsity Patterns for Data-Driven Low-Rank Approximation
论文作者
论文摘要
学习素描矩阵以快速准确的低级别近似（LRA）引起了人们的关注。最近，Bartlett，Indyk和Wagner（Colt 2022）提出了针对基于学习的LRA的概括。具体来说，对于使用$ m \ times n $的排名 - $ k $近似，每列中使用$ s $ non-ZRIX学习的草图矩阵，他们证明了一个$ \ tilde {\ mathrm {o}}}（nsm）$绑定在\ emph上的\ emph {fat shattering dimension}（$ \ tilde}（$ \ tilde} $} $}我们以他们的工作为基础，做出了两项贡献。 1。我们提出了一个更好的$ \ tilde {\ mathrm {o}}（nsk）$ bund（$ k \ le m $）。在获得此结果的途径中，我们给出了用于计算伪内部矩阵的低复杂性\ emph {goldberg - jerrum算法}，这将引起独立的关注。 2。我们缓解了先前研究的假设，即草绘矩阵具有固定的稀疏模式。我们证明，非二方的学习位置仅将脂肪破碎的维度增加到$ {\ mathrm {o}}（ns \ log n）$。此外，实验证实了学习稀疏模式的实际好处。
Learning sketching matrices for fast and accurate low-rank approximation (LRA) has gained increasing attention. Recently, Bartlett, Indyk, and Wagner (COLT 2022) presented a generalization bound for the learning-based LRA. Specifically, for rank-$k$ approximation using an $m \times n$ learned sketching matrix with $s$ non-zeros in each column, they proved an $\tilde{\mathrm{O}}(nsm)$ bound on the \emph{fat shattering dimension} ($\tilde{\mathrm{O}}$ hides logarithmic factors). We build on their work and make two contributions. 1. We present a better $\tilde{\mathrm{O}}(nsk)$ bound ($k \le m$). En route to obtaining this result, we give a low-complexity \emph{Goldberg--Jerrum algorithm} for computing pseudo-inverse matrices, which would be of independent interest. 2. We alleviate an assumption of the previous study that sketching matrices have a fixed sparsity pattern. We prove that learning positions of non-zeros increases the fat shattering dimension only by ${\mathrm{O}}(ns\log n)$. In addition, experiments confirm the practical benefit of learning sparsity patterns.
