May, 2024

有效的矩阵分解：通过 Householder 变换

PDF
TL;DR基于正交字典学习问题，我们提出了一种新的矩阵分解方法，其中数据矩阵 Y 是 Householder 矩阵 H 和二进制矩阵 X 的乘积。首先，我们证明了从 Y 中确切恢复出因子 H 和 X 是在 Y 中具有 Ω(1) 列的；接下来，我们证明了在 Y 中具有 Ω(log n) 列时，可以在多项式时间 (O (np)) 内以 l∞意义上近似恢复。希望本文中的技术有助于开发正交字典学习的替代算法。
发现论文，激发创造
  • 使用 Householder 反射进行递归神经网络的高效正交参数化

    本文介绍了通过约束转移矩阵为正交矩阵来解决序列学习中的长期依赖性问题的方法，并针对简单 RNN 的情况提出了一种新的参数化方案，将正交约束应用于转移矩阵，以提高训练效率。

    Dec, 2016

  • 通过豪斯荷尔德反射自适应缩小低秩与正交适应之间的差距

    基于 Householder 反射的正交微调方法在适应大规模预训练模型方面表现出优越的性能，具有更少的可学习参数。

    May, 2024

  • 半定凸问题的低秩优化

    提出了一种基于对称半正定矩阵变量 X 进行定义的非线性凸程序的求解算法，该算法基于因数分解 X=YY^T，其中 Y 的列数确定 X 的秩。该因式分解唤起了将原问题重新表述为特定商流形上的优化的几何，并得出了二阶优化方法。此外，文章提供了一些关于分解秩的条件以确保与原始问题的等价性。该算法的效率在图的最大切割和稀疏主成分分析问题上得到了说明。

    Jul, 2008

  • 球上的完整字典恢复

    本文利用一种 Riemannian 信任域算法解决了矩阵恢复和字典学习问题，通过几何结构证明了算法的有效性，同时为非凸回收结构的其他问题提供了启示。

    Apr, 2015

  • 蝴蝶分解

    本文介绍了蝴蝶分解作为满足互补低秩性质的矩阵的一种数据稀疏逼近方法，并阐述了构建该分解的有效算法。结果表明，蝴蝶分解可以被快速地应用于 N x N 矩阵，并取得了很好的数值结果。

    Feb, 2015

  • 具有应用价值的分层矩阵快速对称因式分解

    本文介绍了一种快速计算对称正定分层矩阵的对称因子分解的算法，基于低秩更新和递归分治策略，可将计算成本降至 O (nlog^2n) 和 O (nlogn)，适用于处理概率和统计问题、径向基函数插值和流体力学中的算法等。

    May, 2014

  • 贝叶斯最优矩阵分解中的相变和样本复杂度

    使用统计力学工具分析了矩阵分解问题的可实现性和计算可处理性，在贝叶斯最优推断设置下计算任意计算时间内可能实现的最小均方误差和有效近似迭代推理算法可以达到的误差。

    Feb, 2014

  • 基于 Kronecker 积分解的矩阵 - 值数据回归

    我们提出了一种名为 KRO-PRO-FAC 的估计算法，用于高维情况下的矩阵变量回归问题。通过利用 Kronecker 乘积分解和重新排列操作，该算法在计算效率上具备优势，并且可以在存在独立的次高斯随机向量的情况下建立估计参数的扰动界限。数值研究表明，我们的方法在估计误差和预测准确性方面具有竞争力。

    Apr, 2024

  • MahNMF：曼哈顿非负矩阵分解

    本文提出了 MahNMF 方法以及 5 种扩展，用于处理非负矩阵。利用两种算法，即秩一残留迭代（RRI）方法和 Nesterov 的平滑方法，有效地优化了 MahNMF 和其扩展。MahNMF 方法在处理重尾部的拉普拉斯噪声时，能够很好地拟合数据，是一种鲁棒性较强的方法。

    Jul, 2012

  • 二进制分解矩阵

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

    Jan, 2014