Mar, 2024

分块结构的特征相位转换与最优主成分分析

PDF
TL;DR我们通过随机矩阵理论，重点研究了非齐次分组伪威格纳模型中的结构噪声，目标是找到一个最优的频谱方法，并将均匀情况下著名的 BBP 相变准则扩展到非齐次块状威格纳模型，我们对一个变换矩阵进行了彻底而严格的分析，并展示了在最佳阈值处 1）超出极限谱分布的异常值的出现，和 2）相应特征向量与信号之间的正重叠，在最佳阈值处同时出现，使得所提议的频谱方法在非齐次威格纳问题的迭代方法类中是最优的。
发现论文，激发创造
  • 主成分分析的最优性与次优性 I：尖峰随机矩阵模型

    通过研究 Le Cam 的连续性，我们探讨了用于检测稀疏向量存在的测试的统计极限，包括非光谱测试，并证明了对于高斯 Wishart 集合，PCA 阈值对于正向 spikes（自然先验）是最佳的，但这并不总是负向 spikes 的情况。

    Jul, 2018

  • 聚类、稀疏 PCA 和子矩阵定位中的信息论限制和相变

    研究了检测结构化低秩信号矩阵被加性高斯噪声污染的问题，包括在高斯混合模型中的聚类， 稀疏主成分分析和子矩阵定位。通过将第一和第二时刻方法应用于这些 “种植模型” 和零模型之间的似然比来导出阈值的上下界，我们证明了在信号矩阵过于微弱时没有任何算法可以检测其信号。

    Jul, 2016

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

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

    Jul, 2023

  • 非负主成分分析：消息传递算法和尖锐渐近

    本文研究了主成分分析中，如果利用附加到主向量的信息，能否使得任务更容易并提高准确性。在正协方差约束条件下，该文在一峰模型下开发了相似的特征，证明了估计误差也存在相似的相变现象，并且展示在几乎线性时间内如何近似计算非负主成分。

    Jun, 2014

  • 大型随机矩阵有限低秩扰动的特征值和特征向量

    研究了随机矩阵的有限低秩扰动的特征值和特征向量，发现扰动的矩阵极端特征值收敛于非随机值且存在相变现象，临界点与积分变换有关。

    Oct, 2009

  • 信息论上最优稀疏主成分分析

    本文讨论了两种概率稀疏主成分分析模型：钉住 Wigner 模型和钉住 Wishart 模型，并分析了一个用于估计基本信号的近似信息传递 (AMP) 算法。在高维极限下，AMP 估计是信息理论上的最优。此外，本文提供了稀疏 PCA 问题的单字母特征。

    Feb, 2014

  • 高维稀疏 PCA 的在线学习：精确动态和相变

    研究基于在线 PCA 和逐元素非线性的算法对于稀疏主特征向量的学习，证明其在高维极限下收敛于确定性的，尺度测度过程，同时证明在稀疏支持恢复中有良好的表现，并通过非线性 PDE 的稳态分析揭示了有趣的相变现象。

    Sep, 2016

  • 稀疏带宽矩阵估计中的全有或全无统计计算相变

    本文研究在一个稀疏极限下，当底层隐藏向量（构建排名为一的矩阵）非零组成部分数与向量总维数的比例为亚线性，信噪比以适当的速度趋于无穷大时，估计被加性高斯噪声矩阵污染的排名为一的矩阵的统计和计算限制，并证明了渐近互信息的显式低维变分公式，分析了稀疏状态下的近似消息传递算法。对于伯努利和伯努利 - 拉德马赫分布向量，当稀疏度和信号强度满足适当的比例关系时，我们发现渐近最小和算法均方误差的全有或全无相变。在渐近情况下，统计与算法之间的差距发散，表明近似消息传递对于稀疏恢复是非常困难的。

    Jun, 2020

  • 一种张量 PCA 的统计模型

    本文针对任意阶数的大型张量，从信息论和概率论角度出发，讨论了单峰（或秩一加噪声）模型下的主成分分析问题。并使用张量展开、幂迭代和信息传递等多项式时间估算算法分析了这一问题的可行性，阐述了张量幂迭代的初期化和运用附加侧信息推导良好估算的条件。

    Nov, 2014

  • 在未知模型参数时，针对随机块模型的一致的邻接谱划分

    研究随机图中将顶点划分为块的谱技术，通过修改邻接谱分区算法，只需估计通信概率矩阵的秩上限，从而在模型错配的情况下实现一致性，也适用于具有多种模态的邻接表以及有向或无向的图。

    May, 2012