Jul, 2018

低秩二进制矩阵逼近问题的逼近方案

PDF
TL;DR我们为一种关于二进制向量聚类的约束性问题提供了一种随机线性时间逼近方案，并且通过解决这个问题，我们获得了在二进制向量聚类和二进制矩阵低秩逼近方面的第一个线性时间逼近方案。
发现论文，激发创造
  • 广义秩受限矩阵逼近

    本文探讨矩阵的秩约束 Frobenius 范数逼近问题，即对于 $m$ 乘 $n$ 矩阵 $A$，求出秩不超过 $k$ 的矩阵。

    Mar, 2006

  • 线性时间的低秩矩阵近似

    给定一个矩阵，提出了一个线性时间复杂度算法计算其 k 秩矩阵，达到了乘性近似，误差满足 (1+ϵ) 最小误差。

    Oct, 2014

  • 关于贪心低秩优化的近似保证

    本文提供了一种新的矩阵估算近似保证方法，其基于约束强凸性和平滑性的标准假设。同时，本文揭示了低秩估算和组合优化之间的新联系，并针对两个重要的现实问题提供了贪心估计与基准估计间的经验比较。

    Mar, 2017

  • 精确低秩约束下的一比特矩阵补全

    本文提出利用低秩分解完成具有确切秩约束的嘈杂 1 位矩阵完成问题，并研究了在入口无限范数和确切秩约束下的最大似然估计，对于现有结果，本文提供了更快的收敛速率与矩阵维度无关的 1 位观察比例。

    Feb, 2015

  • 二进制分解矩阵

    研究低秩矩阵分解问题，其中一个因子具有 {0,1} 约束条件，第二个因子可以加入凸约束条件；提出一种基于近期非负矩阵分解算法的解决方案，可通过组合数学中的 Littlewood-Offord 引理，在 O (m r 2^r + mnr + r^2 n) 次操作下准确计算低秩分解。

    Jan, 2014

  • k-Means 聚类和低秩逼近的降维

    研究采用缩略图替代数据矩阵来加速 k - 均值聚类和约束 k - 秩近似问题的精确、近似或启发式算法，并提供降维和草图技术及近似算法来解决这些普遍问题。

    Oct, 2014

  • 适用于二元矩阵分解的快速（1+ε）近似算法

    本研究提出了用于解决二元矩阵因式分解问题的高效近似算法，其中输入矩阵 A，矩阵的秩 k，一个精度参数 ε，并且其目标是将 A 近似为低秩因子 UV 的乘积。

    Jun, 2023

  • 距离矩阵的最优低秩逼近

    本文研究了距离矩阵的低秩近似算法及其样本复杂度，在实验中得到了验证。

    Jun, 2019

  • 矩阵隐式函数的分布式低秩逼近

    本研究探讨了分布式低秩逼近，其中需要只隐含地跨不同服务器表示逼近的矩阵。研究表明，在宽泛的函数 f 类别中，可以高效计算一个低秩映射矩阵 P，以满足通信成本为 d∙(sk/ε)^O (1)，且算法成功概率高，并可将其用于计算入门型 softmax、Gaussian 核扩展以及 robust 低秩逼近等问题。

    Jan, 2016

  • 当大数据实际上是低秩的，或者是某个函数生成的矩阵的逐个近似

    通过对两个 m 维变量的光滑函数进行采样生成的矩阵的低秩逼近是本文关注的重点。我们否定了先前文献中对一个特定类别的解析函数所提出的论点，即这些矩阵可以独立于 m 具有准确的逐个元素的秩逼近。我们在理论上解释了支持该论点的数值结果，并描述了三个更窄的函数类别，其中 n×n 由函数生成的矩阵可以在与维度 m 无关的情况下以 O (log (n)ε^(-2) polylog (ε^(-1))) 的逐个元素误差逼近。我们还将我们的论点扩展到了由 m 维变量的多线性积生成的张量的低秩张量列逼近。我们在 Transformer 神经网络的注意力低秩逼近的背景下讨论了我们的结果。

    Jul, 2024