Sep, 2015

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

PDF
TL;DR本篇论文证明了基于分量的 l1 - 范数的低秩矩阵逼近问题是 NP-hard 的， 并与其它著名问题进行了有趣的联系。
发现论文，激发创造
  • 带权重或缺失数据的低秩矩阵逼近是 NP 难的

    本文研究了带权低秩逼近算法的计算复杂度，并证明了即使在寻求秩为一的逼近解时，找到近似解也是 NP 难的，该证明基于最大边双团问题的约化并适用于严格正权重和二进制权重。

    Dec, 2010

  • 主成分分析的随机算法

    本文提出一种有效的算法，用于对任意规模的矩阵进行低秩逼近，可以在保证精度的同时大大提高计算效率，实验结果证明了算法的可行性。

    Sep, 2008

  • 非凸秩近似实现的鲁棒 PCA

    研究了鲁棒主成分分析方法在矩阵恢复中的应用，提出了一种比核范数更紧的非凸秩逼近方法，并且设计了一种高效的基于增广拉格朗日乘子法的优化算法。实验结果表明，该方法在精度和效率方面优于现有的最先进算法。

    Nov, 2015

  • 鲁棒主成分分析？

    本文介绍了一种名为主成分追踪的凸型优化方法，能在有噪声或缺损情况下准确分离一个 $ m * n $ 数据矩阵的低秩和稀疏成分，该方法有望应用于视频监控和人脸识别等领域。

    Dec, 2009

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

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

    Dec, 2018

  • 一些低秩子空间恢复模型之间的关系

    本文发现一些代表性的子空间恢复模型（如 Robust Principal Component Analysis（R-PCA），Robust Low Rank Representation（R-LRR）和 Robust Latent Low Rank Representation（R-LatLRR））之间存在深层次联系，一旦获得一个模型的解决方案，可以通过封闭形式公式获得其他模型的解决方案，从而使得 R-PCA 成为低秩子空间恢复模型的核心。同时，通过先解决 R-PCA 可以获得显著更快的算法，并且可以通过应用低复杂度的随机算法进一步降低计算成本。

    Dec, 2014

  • 广义低秩模型

    本文将 PCA 技术扩展到处理包含数字、布尔、分类、有序等多种数据类型的任意数据集，提出了一种处理异构数据集的通用低秩模型，并为其提供了一些基于并行算法的实现。

    Oct, 2014

  • 图上快速鲁棒主成分分析

    本文提出了一种基于主成分分析（PCA）的解决方案，通过设计凸优化问题来实现对高维数据集的低秩恢复，重点解决了高计算复杂性、非凸性和数据中的大量异常问题，同时经过了 7 组基准数据集的聚类实验和 3 组视频数据集的背景分离实验的测试，结果表明我们提出的模型优于 10 种最先进的降维模型。

    Jul, 2015

  • 加权低秩逼近的重新加权解

    通过使用权重矩阵本身进行矩阵重新加权，我们提出了一种放松的 WLRA 解法，该方法可以输出一个并非低秩矩阵，但可以使用非常少的参数进行存储，并在权重矩阵具有低秩时给出可证明的近似保证。此外，我们的算法在模型压缩和合成数据集方面展现出非常出色的实证性能，并为与此问题相关的自然分布问题提供了几乎最佳的通信复杂性界限。

    Jun, 2024

  • 矩阵刚性与鲁棒 PCA 和矩阵完成的不适定性

    研究了 Robust Principal Component Analysis 和 low-rank matrix completion 两个问题的稳健性，发现由于其低秩矩阵和基础矩阵之间的相干性，以及矩阵刚度函数的不连续性等问题，可能会出现无解的情况。

    Nov, 2018