NADeMaC: A Simple Non-Nagetive Decentralized Completion Algorithm for Internet Latency Matrix
Cong Wang
International Journal of Web Applications, Vol. 7, No. 4, 2015.
DOI: 
Link: http://www.dline.info/ijwa/fulltext/v7n4/v7n4_1.pdf
Abstract:
In this paper, the non-negative decentralized completion problem of the in-complete Internet latency matrix
is studied. On the basis of the low-rank approximation of the matrix, we componentized this problem into a couple of
convex optimization problems by estimating the l0 norm of this matrix, and then solved it by alternative direction
algorithm. Owing to the asymmetry and the negative definite characteristic of the matrix caused by the difference between
autonomous system routing strategies, some negative entries inevitably exist in the completed matrix. Unlike traditional
non-negative completion algorithms, this paper does not try to prevent the generation of the negative entries. As a
replacement, this paper presents a novel and much simpler non-negative ensuring scheme named NADeMaC, which
calibrates the negative entries by a prior positive estimation value after they appeared. Theoretical analysis shows that
the accuracy of our algorithm is at least no less than traditional methods, and furthermore our experiments show that
our method is far better than traditional non-negative ensuring scheme.