This paper considers the problem of completing a matrix with many missing entries under the assumption that the columns of the matrix belong to a union of multiple low-rank subspaces. This generalizes the standard low-rank matrix completion problem to situations in which the matrix rank can be quite high or even full rank. Since the columns belong to a union of subspaces, this problem may also be viewed as a missing-data version of the subspace clustering problem. Let X be an n x N matrix whose (complete) columns lie in a union of at most k subspaces, each of rank > kn. The main result of the paper shows that under mild assumptions each column of X can be perfectly recovered with high probability from an incomplete version so long as at least CrNlog^2(n) entries of X are observed uniformly at random, with C>1 a constant depending on the usual incoherence conditions, the geometrical arrangement of subspaces, and the distribution of columns over the subspaces. The result is illustrated with numerical experiments and an application to Internet distance matrix completion and topology identification.
The proof of the main result draws on ideas from matrix completion theory, subspace learning and detection with missing data, and subspace clustering. One key ingredient in our approach is the celebrated results on low-rank Matrix Completion @cite_12 @cite_0 @cite_5 . Unfortunately, in many real-world problems where missing data is present, particularly when the data is generated from a union of subspaces, these matrices can have very large rank values ( e.g., networking data in @cite_17 ). Thus, these prior results will require effectively all the elements be observed to accurately reconstruct the matrix.
@cite_0 @cite_5 @cite_12 @cite_17
2182949771 2120872934 2159326294
This paper is concerned with the problem of recov- ering an unknown matrix from a small fraction of its entries. This is known as the matrix completion problem, and comes up in a great number of applications, including the famous Netflix Prize and other similar questions in collaborative filtering. In general, accurate recovery of a matrix from a small number of entries is impossible, but the knowledge that the unknown matrix has low rank radically changes this premise, making the search for solu- tions meaningful. This paper presents optimality results quanti- fying the minimum number of entries needed to recover a matrix of rank exactly by any method whatsoever (the information theo- retic limit). More importantly, the paper shows that, under certain incoherence assumptions on the singular vectors of the matrix, re- covery is possible by solving a convenient convex program as soon as the number of entries is on the order of the information theo- retic limit (up to logarithmic factors). This convex program simply finds, among all matrices consistent with the observed entries, that with minimum nuclear norm. As an example, we show that on the order of samples are needed to recover a random matrix of rank by any method, and to be sure, nuclear norm min- imization succeeds as soon as the number of entries is of the form . This paper provides the best bounds to date on the number of randomly sampled entries required to reconstruct an unknown low-rank matrix. These results improve on prior work by Candes and Recht (2009), Candes and Tao (2009), and (2009). The reconstruction is accomplished by minimizing the nuclear norm, or sum of the singular values, of the hidden matrix subject to agreement with the provided entries. If the underlying matrix satisfies a certain incoherence condition, then the number of entries required is equal to a quadratic logarithmic factor times the number of parameters in the singular value decomposition. The proof of this assertion is short, self contained, and uses very elementary analysis. The novel techniques herein are based on recent work in quantum information theory. Despite many efforts over the past decade, the ability to generate topological maps of the Internet at the router-level accurately and in a timely fashion remains elusive. Mapping campaigns commonly involve traceroute-like probing that are usually non-adaptive and incomplete, thus revealing only a portion of the underlying topology. In this paper we demonstrate that standard probing methods yield datasets that implicitly contain information about much more than just the directly observed links and routers. Each probe, in addition to the underlying domain knowledge, returns information that places constraints on the underlying topology, and by integrating a large number of such constraints it is possible to accurately infer the existence of unseen components of the Internet. We describe DomainImpute, a novel data analysis methodology designed to accurately infer the unseen hop-count distances between observed routers. We use both synthetic and a large empirical dataset to validate the proposed methods. On our empirical real world dataset, we show that our methods can estimate over 55 of the unseen distances between observed routers to within a one-hop error.