Jul, 2012

快速柯西变换与更快的稳健线性回归

PDF
TL;DR提供了快速算法，用于超约束的 ell_p 回归和相关问题，将问题减少到与输入矩阵的 coreset 相同的问题，我们还提供了一套用于通过椭球舍入找到良好条件的基础的改进结果，包括一种用于 ell_p 问题的快速子空间嵌入。
ell_p regressioncoresetellipsoidal roundingfast cauchy transformjohnson-lindenstrauss transforms
发现论文，激发创造
  • Lp 回归的采样算法和核集

    该论文提出了一个有效的两阶段抽样算法来解决 Lp 回归问题，包括构建核心集合、采样等方法，并且在算法的证明过程中提出了两个值得研究的概念：条件良好的基和子空间保留采样。

    Jul, 2007

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

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

    May, 2013

  • 高效求解密集线性系统的方法

    提出了一种随机优化算法，通过块坐标下降方法和矩阵草图技术，在线性系统中实现了良好的收敛性能和快速迭代时间。

    Dec, 2023

  • 输入稀疏时间内低失真子空间嵌入及其在鲁棒线性回归中的应用

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

    Oct, 2012

  • 几乎最优的无限制快速 Johnson-Lindenstrauss 变换

    利用 Banach 空间中的概率新工具，将随机投影问题的研究推进到一个新的水平。其主要结果是可以线性映射任意 $N$ 个 $n$ 维实向量到一个 $O (log N polylog (n))$ 线性空间中，并在保持向量之间距离一定畸变的同时，对每个向量的映射可以在 $O (n log n)$ 时间内完成。

    May, 2010

  • 关于鲁棒线性回归的高效算法及下界

    研究了高维线性回归在对抗性污染下的稳健模型问题，并针对从高斯分布生成的未被修正的样本的基本情况给出了几乎最紧的上界和计算下界。

    May, 2018

  • 近线性时间内的最优鲁棒线性回归

    研究了高维稳健线性回归问题，在受到对抗性破坏的情况下提出了估计方法，包括样本复杂度，恢复保证，运行时间等关键指标，并利用近期算法发展的加速算法和高斯舍入技术等方法来优化估计器的运行时间和统计样本复杂性。

    Jul, 2020

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

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

    Jul, 2012

  • 对异常数据鲁棒的回归的高效算法

    本文首次给出了一个多项式时间算法，用于在示例和标签中对抗性堕落下执行线性或多项式回归，并基于 SoS 方法提出了一种自然的凸松弛方法来解决非凸优化问题。

    Mar, 2018

  • 高维稳健协方差估计的快速算法

    本文研究了协方差矩阵的估计问题，当仅有小部分样本被恶意更改时，我们提出了一种运行时间接近计算经验协方差且具有最佳误差保证的算法，该算法适用于高维分布，能处理高斯分布等深度分布结构及矩阵乘法指数中的病态情形。

    Jun, 2019