半定规划多参考序列比对
本文研究相位同步问题的解决方案及其联系,引入半正定松弛及广义幂法求解此非凸问题,并提出一种新的迭代算法跟踪较紧密的序列,推导出广义幂法全局收敛于峰值解、线性收敛性及贝塔扰动项。
Mar, 2017
本文提出将最小二乘问题转化为凸性的半定规划问题,通过刚体变换及刚体理论来稳定恢复解,同时实验证明该方法在噪声较大时表现显著优于谱松弛法和流形优化方法。
Jun, 2013
本文通过对众多相对相位的测量,给出了一种角度同步方法,提出了在噪声干扰下用 MLE 方法解决该问题的难点,探究在不知道最优条件的情况下,最大似然估计解决角度同步过程的正确性。
Nov, 2014
提出了一种新的半定规划解决方案(SDP-1)以适应随机块模型(SBM)中的社区检测问题,可以放宽之前提出的 SDP 方法中的一些条件,并且是适合拟合网络直方图的理想工具。
Jun, 2014
这篇论文主要探讨了应用于信号处理、数据挖掘和机器学习中的统计推理问题,当数据的维度很高时,常常导致较难处理的组合优化问题。文中提出了通过构建这些组合优化问题的凸松弛来解决问题的热门思想。其中,半定规划松弛是该家族中最有力的方法之一,并且出人意料地适用于形如矩阵或图形的数据问题。作者对几个经典的半定规划松弛模型进行了研究,尤其是适用于图同步和网络中的社区检测等统计问题的模型。通过将这些优化问题映射到带有向量自旋的统计力学模型中,使用统计力学中的非严谨技术来描述相应的相变,以期阐明半定规划松弛在高维统计问题中解决问题的有效性。
Nov, 2015
通过引入非凸约束形式并应用 Riemannian trust-region 方法,该论文研究了 MaxCut 和同步问题中的秩约束半定规划,并建立了一个 Grothendieck 型不等式证明局部最大值和危险鞍点都在离全局最大值一个小倍数距离的情况下,SDPs 可以在已知精度内得到解决。
Mar, 2017
本文提出使用具有两个创新的二进制 SDP 松弛,同时聚焦于计算效率的 SOS 层次结构进行 MAP 推理,该算法在实际问题如图像去噪和 Ising 自旋玻璃方面表现优于 BP 和 GBP。
Sep, 2017
本文介绍了一种基于新的半定松弛形式 (SDR) 的最大后验推理方法,用于在大规模马尔科夫随机场上求解 MAP 问题,并采用 SDPAD-LR 交替方向乘法加速算法,取得了显著的可扩展性和计算效率。
May, 2014
本文研究从损坏的成对线测量中估计 n 个位置的逆问题,提出了半定规划 (SDP) 的配套公式,并提供一种交替方向方法来解决这个问题。与此同时,我们还提出了一个基于鲁棒相机方向和子空间估计的成对线估计方法,并通过实验来展示我们算法的效用。
Dec, 2013
该研究提出了第一个通用且可扩展的框架,用于设计可靠的几何感知算法,以在存在异常值的情况下证明其准确性,并在六个几何感知问题上进行了评估。
Sep, 2021