Oct, 2015

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

PDF
TL;DR研究了多维欧氏空间中寻找一个 k 维子空间 F，使得一组 n 个点到该子空间的 p 次方欧氏距离和最小的问题。进一步探讨了在某些损失函数 M ()（如 Huber 和 Tukey 损失函数）下此问题的最优解。这些鲁棒子空间可替代奇异值分解（SVD）提供更有效的解决方案，对于典型的 M-Estimators，对离群值的鲁棒性更强。本文给出了一些这些鲁棒子空间逼近问题的算法和难度结果。
subspace approximationeuclidean distancesm-estimatorsoutliersalgorithmic results
发现论文，激发创造
  • 输入稀疏时间内低失真子空间嵌入及其在鲁棒线性回归中的应用

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

    Oct, 2012

  • 几乎线性化稀疏化的高维 l_p 子空间逼近

    ell_p 子空间逼近问题是一个 NP-hard 的低秩逼近问题，我们通过构建一个强核心集算法，第一次获得了对于 rank 参数 k 几乎最优性的依赖，得到了 p<2 时的近似线性边界 O (k) poly (ε^(-1)) 和 p>2 时的 O (k^(p/2)) poly (ε^(-1)) 边界，此外，我们还解决了在线 setting 中 poly (k) 因子损失的问题。

    Jul, 2024

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

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

    Jul, 2012

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

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

    May, 2013

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

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

    Apr, 2019

  • 通过几何 l_p 最小化实现多子空间鲁棒恢复

    本文研究了从混合分布中采样的数据，通过最小化样本数据与 K 个线性子空间的 l_p 平均距离，同时恢复 K 个子空间并解释了 l_p 能量最小化方法在多子空间数据建模中的失败和成功

    Apr, 2011

  • 高维极小化稀疏主子空间估计

    研究高维稀疏主成分分析，提出了行稀疏和列稀疏的 lq 子空间稀疏概念，并为 0≤q≤1 证明了极小化子空间估计误差的非渐近下限和上限。这一限制完美适用于行精疏的子空间，并且近乎适用于列精疏的子空间。我们使用一种新颖的变分 sinΘ 定理进行证明，该定理可能对其他正则化谱估计问题有用。

    Nov, 2012

  • 基于更严格的秩近似的鲁棒子空间聚类

    本文介绍了一种基于反正切函数的更紧密逼近秩函数的方法，并使用它来解决具有挑战性的子空间聚类问题，并开发了一种基于增广拉格朗日乘数方法的有效优化过程。实验结果表明，所提出的方法对于秩逼近问题十分有效。

    Oct, 2015

  • 一种新的 M - 估计器用于鲁棒主成分分析

    研究了鲁棒子空间恢复的基本问题，通过解决凸最小化过程来估计 “鲁棒逆样本协方差”，然后通过此矩阵的底部特征向量（其数量对应于接近 0 的特征值的数量）恢复子空间。我们保证在某些条件下精确恢复子空间，同时提出了一种快速迭代算法，可线性收敛到最小化凸问题的矩阵。我们对噪声和正则化的影响进行了量化，并在各种设置中讨论了许多实际和理论问题，以改善子空间恢复。与许多其他鲁棒 PCA 算法相比，在合成和实际数据集上进行了比较，并证明具有最先进的速度和准确度。

    Dec, 2011

  • 鲁棒子空间恢复的算法和难度

    从高维空间中的数据中识别子空间问题是一个困难的计算问题，本文提出了一种在存在异常值情况下有效识别子空间的算法，并证明该算法在异常值率小于等于 $d/n$ 时是最优的。

    Nov, 2012