Feb, 2016

噪声幂方法的改进间隔依赖分析

HTML
PDF
TL;DR本文研究了噪声幂法算法在机器学习和统计学中的应用，特别是在资源（通信，存储或隐私）约束下针对主成分分析（PCA）。通过对噪声幂法进行新的分析，改进了其样本复杂度和噪声容忍度，特别是将其依赖性从“连续”的谱差转移到“中间算法参数”与目标秩之差，得到了优于文献中现有结果的界限。最后将该算法应用于分布式隐私PCA和内存高效数据流PCA方面的问题，并获得了优于现有文献结果的界限。
发现论文，激发创造
  • 稀疏主成分分析的最优解

    本论文提出了一种基于协方差矩阵的稀疏主成分分析方法，采用半正定松弛和贪心算法求解，可以适用于诸如子集选择和稀疏恢复等领域，并能在人工和生物数据等实验数据中提供全局最优解。

    Jul, 2007

  • 通过凸松弛进行嘈杂矩阵分解：在高维度中获得最优速率

    通过矩阵分解问题中的凸松弛方法，结合核范数和分解式正则化，我们分析了一个能得到估计值的一般性定理，该定理可以适用于低秩矩阵、稀疏矩阵及一些可压缩的高维矩阵。我们利用了峰态条件，得到了确定性和随机性噪声矩阵的非渐近性弗罗贝尼乌斯误差界，同时也证实了最小化误差的下限和数值模拟结果的契合度。

    Feb, 2011

  • 低秩逼近实现的稀疏主成分分析

    本文介绍了一种计算正半定矩阵的k-稀疏主成分的新算法，其通过查看低维度特征子空间中的一组离散特殊向量来实现。该算法的近似保证取决于其特征值分布，这使得其能够在多项式时间内对任意精度进行近似计算，同时几乎能够匹配或优于之前算法在所有测试数据集上的表现。

    Mar, 2013

  • 噪声幂法：具有应用的元算法

    本文针对机器学习中常用的噪声干扰的幂方法进行研究，提出了新的稳健收敛性分析，解决了在多个应用领域中的一系列问题。

    Nov, 2013

  • 论鲁棒主成分分析和L1范数低秩矩阵逼近的复杂度

    本篇论文证明了基于分量的l1-范数的低秩矩阵逼近问题是NP-hard的， 并与其它著名问题进行了有趣的联系。

    Sep, 2015

  • 通过梯度下降的快速鲁棒PCA算法

    本文介绍了一种非凸优化方法，用于解决全观测和部分观测情况下的鲁棒主成分分析问题，该方法与现有最佳算法相比，显著降低了计算复杂度，并且在部分观测情况下，我们的算法在有可证明的情况下也是已知的运行时间最短的算法。

    May, 2016

  • 非负Rank-1健壮主成分分析不含虚假局部极小值的确切保证

    采用Burer-Monteiro方法，论文提出一种较少变量的非凸非光滑优化问题形式的低维对称和非对称正秩-1 RPCA，其具有良好的景观和不会有虚假的本地解决方案，保证了精确恢复真实主分量的强大确定性和概率保证。

    Dec, 2018

  • 稳健的次高斯主成分分析与宽度独立的谱范数填充

    研究开发了两种基于中心子高斯分布的降噪主成分分析算法，灵活应用于解决具有非代数结构矩的相关问题。同时定量地分析了算法的复杂性和置信度。

    Jun, 2020

  • 稀疏主成分分析的算法和障碍是否适用于其他结构化情境？

    通过研究一种在尖峰维沙特模型下的主成分分析问题，我们揭示了信号中的结构通过一类子空间模型予以捕捉。在统计和计算统一的视角下，我们建立了依赖于问题实例几何结构的基本限制，并展示了一种自然的投影幂法在解的统计可接近最优邻域上表现出的局部收敛性。我们通过分析两个重要特例，即基于路径和树稀疏性的初始方法和匹配证据的计算难度，来补充这些结果。总体而言，我们的结果表明，多个针对普通稀疏主成分分析观察到的现象自然地扩展到其结构化对应物中。

    Jul, 2023

  • 黑盒$k$-to-$1$-PCA降维：理论与应用

    k-主成分分析(k-PCA)问题是一种在数据分析和降维应用中广泛使用的基本算法原语。本文通过分析黑盒排斥方法作为设计k-PCA算法的框架，提出了更加精确的边界以解决k-PCA中的参数损失问题，并应用此框架获得了对数据集污染具有鲁棒性且在样本复杂度和近似质量方面超过之前工作的最先进的k-PCA算法。

    Mar, 2024