基于谱方法的正交和置换群同步的近优性能界
该研究提出了一种基于特殊正交群上的同步问题,该问题包括从它们成对比率的噪声测量中估计一组未知的旋转。它的最小二乘解可以通过谱松弛或半定规划来近似,其具有类似于 Max-Cut 的近似算法。该研究通过提出偏差平方和的罚函数来弱化其次方项,并引出了一种求解该问题的凸优化方法,同时在特定噪声模型下,证明了其稳定性并得到了相位转变行为的模拟结果。
Nov, 2012
本研究旨在探究相位恢复系统中采用随机正交向量矩阵的谱方法启动的局部搜索算法。我们在渐进的情况下,获得了谱估计器和真实信号向量之间的最大重叠程度的简单表达式。
Mar, 2019
该研究探讨了在多重网络中识别社区的问题,当节点之间的相互作用由相似度的符号(可能加权)度量时,可以考虑使用谱算法或消息传递算法,特别是当节点之间存在特定子集表示相同未知的群元时,以及对应的噪声测量的情况下。在应用中,研究者成功地将所提议的方法应用于美国国会中两个政党的识别,即民主党和共和党。
Apr, 2015
给定多个项目之间的成对比较,如何对它们进行排名,以使得排名与观察结果相匹配?本研究关注基于 Erdos-Renyi 异常值(ERO)模型的排名问题,在该问题中,每个成对比较都是真实分数差异的损坏副本。通过研究基于非归一化和归一化数据矩阵的谱排名算法,我们提供了每个项目从观察数据中恢复出其潜在分数的性能,并得出了非归一化 / 归一化数据矩阵的最大特征向量与其总体对应物之间的逐项扰动误差界限。通过留一法技术,我们提供了更精确的最大特征向量的 l∞范数扰动界限,并在只有 Ω(nlogn) 个样本的情况下导出了每个项目的最大偏移误差界限。理论分析在样本复杂度方面改进了现有技术的结果,并通过数值实验验证了这些理论发现。
Sep, 2023
本研究针对在 Stiefel 流形上最大化(或最小化)二次目标函数的的优化问题,提出了一种基于正交迭代算法的稀疏矩阵优化方法,并将其应用于排列同步问题,取得了比之前更好的结果。
Sep, 2021
在这篇论文中,我们研究了在一般的二元博弈和高斯矩阵模型中的精确社区恢复问题,这两种模型分别捕捉了随机块模型、子矩阵定位和 Z2 同步作为特例。我们还研究了有关社区分配标签的智能信息可用的情况,将其建模为通过噪声通道传递真实标签:二进制擦除通道(其中某些社区标签已知而其他被抹去)或二进制对称通道(其中某些标签被翻转)。我们对智能信息对精确恢复的信息论极限的影响提供了统一的分析,扩展了之前的研究并拓展到新的设定。此外,我们设计了一个简单但最优的谱算法,将智能信息(如有)与矩阵观测的特征向量结合起来。利用入元素特征向量分析的强大工具 [Abbe, Fan, Wang, Zhong 2020],我们表明我们的谱算法可以模仿所谓的 “精灵辅助估计器”,其中第 i 个精灵辅助估计器在精灵揭示其他标签的情况下,最优计算第 i 个标签的估计。这一观点为最近的一系列工作中各种精确恢复问题的谱算法的最优性提供了统一的理解。
Jun, 2024
本文介绍一种解决几何估计中同步问题的算法,通过基于半定松弛的最大似然估计得出全局最优解,该算法可以在非对抗噪声情况下高效恢复可认证的全局最优解,并在大规模实例上使用低维黎曼曲面与特殊优化方案实现了优化问题的求解。
Nov, 2016
提出了一种新的二次规划公式,用于估计组同步中的数据损坏程度,并使用这些估计值来解决此问题。该方法利用了组的循环一致性,并将其称为结构一致性的检测和估计(DESC)。该公式具有多种优点,例如可以容忍高达信息论界限的数据损坏,不需要好的初始化,具有简单的解读,并且在一些温和的条件下,我们的目标函数全局最小值恰好恢复数据损坏程度。我们在旋转均值的合成和真实数据实验中展示了该方法的竞争准确性。
Jun, 2022