一种网络时延矩阵分布式自适应重建算法

An Adaptive Distributed Completion Algorithm for Network Latency Matrix

该文基于互联网时延矩阵的近似稀疏性,通过给定重建矩阵的零范数先验估计,讨论了不完整时延矩阵在完全去中心化环境下的填充问题。首先,将该问题转化为一对耦合凸优化问题,并进行轮转求解;然后,针对次梯度下降求解算法中存在的计算代价过高与泛化能力不足的问题,提出了搜索上界倍增的自适应分布式矩阵重建(ADMC)算法,并引入不同的损失函数作为重建误差评价准则,以提升算法的适应能力。实验证明,在不增加测量与通信负载的前提下,ADMC能够在不损失精度的情况下显著降低计算代价,同时,多种损失函数的引入也提升了算法的鲁棒性。

On the basis of the low-rank characteristic of the Internet latency matrix, the in-complete latency matrix completion problem in full-decentralized environment is studied through setting a priori estimation of the l 0 norm of this matrix. First, the problem is componentized into a couple of convex optimization problems, thus it can be solved by alternative direction method. Then, to achieve low computation cost along with well generalization, an Adaptive Distributed Matrix Completion （ADMC） algorithm is proposed. ADMC doubles the upper-bound of the iterative step size searching area, and introduces several kinds of loss functions as the latency estimation error measures. Experiments show that, without losing any accuracy, ADMC reduces the computation cost significantly without any additional measurement or communication cost, and the introduced various loss functions also improve the robustness of the algorithm.