ADeMaC: An adaptive decentralized network latency matrix completion algorithm

Latency matrix completion is an important foundation of latency-sensitive applications optimization. But in decentralized environments, this matrix always is incomplete. On the basis of the in-depth discussion of the low-rank characteristic of the latency matrix, this paper propose a new algorithm named Adaptive Decentralized Matrix Completion, ADeMaC, to complete the matrix approximately. First, we give out a priori estimation of the matrix rank, and transform the matrix completion problem into solving two convex function minimization problems alternatively. For each function, we introduce the sub-gradient descending algorithm with adaptive step size choosing. Finally, experiments show that this algorithm can reduce the computation cost about 68.66% without losing any accuracy.