Jul, 2012

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

PDF
TL;DR本文提出了一种新的稀疏嵌入矩阵，通过使用这种矩阵，可以实现超约束最小二乘回归、低秩逼近、所有梁角得分的近似和 $l_p$- 回归问题的 $(1+\varepsilon)$- 近似，其时间复杂度的主导项是 $O (\nnz (A))$ 或 $O (\nnz (A)\log n)$。
subspace embeddingsparse embedding matrices$(1+\varepsilon)$-approximationleast-squares regression$\ell_p$-regression
发现论文，激发创造
  • 输入稀疏时间内低失真子空间嵌入及其在鲁棒线性回归中的应用

    提出了一种低失真度嵌入方法，在线性代数问题中得到广泛应用，支持 l_2 误差损失最小回归以及 (1±ε) 失真度的 l_p 子空间嵌入，包括一种基于输入稀疏性的 l_p 子空间采样过程。

    Oct, 2012

  • 指数随机变量的子空间嵌入和 Lp 回归

    本文从子空间嵌入的角度出发，提出了一种构造常数扭曲率子空间嵌入的新方法，并将其应用于线性回归问题以及分布式计算中。

    May, 2013

  • 强健子空间逼近的输入稀疏度和难度

    研究了多维欧氏空间中寻找一个 k 维子空间 F，使得一组 n 个点到该子空间的 p 次方欧氏距离和最小的问题。进一步探讨了在某些损失函数 M ()（如 Huber 和 Tukey 损失函数）下此问题的最优解。这些鲁棒子空间可替代奇异值分解（SVD）提供更有效的解决方案，对于典型的 M-Estimators，对离群值的鲁棒性更强。本文给出了一些这些鲁棒子空间逼近问题的算法和难度结果。

    Oct, 2015

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

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

    Jul, 2015

  • 利用数值稀疏性进行高效学习：更快的特征向量计算和回归

    本文提出了更快的算法来解决数据矩阵中回归和特征向量计算问题，使用这些算法，即使在稀疏矩阵的情况下，也可以获得近似的线性运行时间。

    Nov, 2018

  • 用 Orlicz 范数进行子空间嵌入和线性回归

    本文针对经典线性回归问题进行推广，研究了 Orlicz 范数的损失函数，并提出了一种新的盲嵌入，用于将具有 Orlicz 范数的矩阵空间嵌入到具有二范数的较低维空间，从而得到回归问题和低秩矩阵逼近问题的近似算法。

    Jun, 2018

  • 子空间草图问题的紧密界限及应用

    研究子空间草图问题，通过构建一个小空间数据结构压缩给定矩阵，讨论其压缩方案和所需存储空间以及相应的下界，探讨其在矩阵乘积中的应用，展示了对内积基于任意数构建数据结构的不可行性以及 l1 奇异值分解的不同情况下的空间复杂度变化。

    Apr, 2019

  • 核矩阵低秩逼近中是否存在稀疏化输入时间？

    本文研究了计算有效的低秩核近似的限制，证明计算相对误差 k 秩逼近 K 对于广泛类别的核，包括高斯和多项式核，至少与将输入数据矩阵 A 乘以任意矩阵 C 一样困难，并给出了一些希望：首次证明对于一般的径向基函数核， 如高斯核，存在 $O (nnz (A))$ 的时间近似方法。

    Nov, 2017

  • 入项变换矩阵乘积的低秩逼近难度

    在输入转换设置中，我们研究低秩逼近，给出了该问题的条件时间难度结果和运行时下界，同时证明了这些下界是紧致的，并提供了使用基于张量的草图的相对误差逼近算法。

    Nov, 2023

  • 稳健稀疏均值估计的次二次时间算法

    稀疏均值估计算法在存在对抗性异常值的情况下的研究，提出了一种在次二次时间内运行的鲁棒稀疏均值估计算法，并在检测弱相关性方面取得了算法进展。

    Mar, 2024