Sep, 2019

Kronecker 乘积回归和低秩逼近的最优素描

PDF
TL;DR本研究旨在提出一种高效的 Kronecker 乘积回归算法，该算法可以用于矩阵逼近和低秩逼近，并且小于 2 的 p 值具有更好的运行时间，此外，还提出了一种用于所有成对差异的回归问题的算法。
kronecker product regressionmatrix approximationlow rank approximationalgorithm efficiencyall-pairs regression
发现论文，激发创造
  • 低秩张量回归的近似最优素描

    本文介绍了针对最小二乘回归问题的 CP 和 Tucker 分解模型，以及基于稀疏随机投影的数据降维技术，旨在减小模型参数数量和计算量。作者通过数值模拟得到了实验结果，证实了其理论的有效性。

    Sep, 2017

  • Kronecker 乘积回归和 P 样条的草图

    本文提出一种名为 TensorSketch 的算法，它可以用于 Kronecker 乘积回归、正规化样条回归等问题，并且还可以用于基本相关性分析和低秩逼近。此外，该算法还被扩展到用于其他范数的计算。

    Dec, 2017

  • 量子快速速度与克罗内克积的谱逼近

    本研究提出了一种创新的方法，通过将矩阵视为量子态来高效地处理 Kronecker 积的光谱近似问题，将时间复杂度显著降低为 O_{d,ε}(√n)。

    Feb, 2024

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

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

    Apr, 2024

  • Krylov 方法在低秩近似中（几乎）是最优的

    本文通过矩阵向量乘积模型和多种 Schatten norm 下的 rank-1 低秩逼近问题，证明了 Krylov methods 几乎达到了谱（p=∞）、Frobenius（p=2）和核（p=1）LRA 的信息论最优矩阵向量乘积数量的上界，并给出了一些改进的上界。

    Apr, 2023

  • 基于学习的低秩逼近

    本文介绍了一种基于学习的算法来解决低秩分解问题，并且通过学习用稀疏矩阵来代替随机矩阵可以减小近似误差。同时，给出了针对稀疏矩阵学习问题的泛化界及近似算法。

    Oct, 2019

  • 稳定秩下的最优近似矩阵乘积

    用子空间嵌入保证黑盒方式证明，通过降维映射可实现近似矩阵乘法的谱范数保障，其中降维映射具有 O（~r/ε^2）行，且优于以前的工作 [MZ11，KVZ14]，对于任何混淆的降维映射也是最佳的。

    Jul, 2015

  • 输入稀疏时间内的低秩逼近和回归

    本文提出了一种新的稀疏嵌入矩阵，通过使用这种矩阵，可以实现超约束最小二乘回归、低秩逼近、所有梁角得分的近似和 $l_p$- 回归问题的 $(1+\varepsilon)$- 近似，其时间复杂度的主导项是 $O (\nnz (A))$ 或 $O (\nnz (A)\log n)$。

    Jul, 2012

  • 低秩核矩阵近似的尖锐分析

    本文研究了在正定核框架下的监督学习问题，提出了基于随机矩阵列采样的核矩阵低秩近似方法，此方法可以在 sub-quadratic 的时间复杂度内有效解决核矩阵计算问题，同时保持预测性能不变。

    Aug, 2012

  • 低秩矩阵值 Chernoff 界和近似矩阵乘法

    本文提出了一种利用两种不同抽样方法进行矩阵乘法，以逼近具有谱范数的矩阵，从而得出理论上的界限。

    May, 2010