International Journal of Web Applications Cong Wang 7 4 2015 http://www.dline.info/ijwa/fulltext/v7n4/v7n4_1.pdf 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.