NOISY EUCLIDEAN DISTANCE REALIZATION: ROBUST FACIAL REDUCTION AND THE PARETO FRONTIER
NOISY EUCLIDEAN DISTANCE REALIZATION: ROBUST FACIAL REDUCTION AND THE PARETO FRONTIER
复制标题
DOI：
10.1137/15m103710x
复制
发表时间：
2017-01-01
影响因子：
3.1
通讯作者：
Wolkowicz, H.
中科院分区：
文献类型：
--
作者：
Drusvyatskiy, D.;Krislock, N.;Wolkowicz, H.
我们基于半决赛优化，提出了两种用于大规模嘈杂的低级欧几里得距离矩阵完成问题的算法。我们的第一个方法是通过将已知距离图中的集团与阳性半圆锥锥面的面相关联，从而产生了一个合并过程，该组合过程可证明是可靠的且部分可行的。我们的第二个算法是一种一阶方法，用于最大程度地提高痕量的流行低级别诱导常规化器，以限制性失误制定问题。这两种方法都输出了一个点配置，该配置可以用作局部优化技术的高质量初始化。大规模传感器定位问题的数值实验说明了两种方法。
We present two algorithms for large-scale noisy low-rank Euclidean distance matrix completion problems, based on semidefinite optimization. Our first method works by relating cliques in the graph of the known distances to faces of the positive semidefinite cone, yielding a combinatorial procedure that is provably robust and partly parallelizable. Our second algorithm is a first-order method for maximizing the trace a popular low-rank inducing regularizer in the formulation of the problem with a constrained misfit. Both of the methods output a point configuration that can serve as a high-quality initialization for local optimization techniques. Numerical experiments on large-scale sensor localization problems illustrate the two approaches.