Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, PMLR 22:373-381, 2012.
Abstract
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 nxN matrix whose (complete) columns lie in a union of at most k subspaces, each of rank = r n, and assume Nkn. 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 C r N \log^2(n) entries of X are observed uniformly at random, with C1 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.
@InProceedings{pmlr-v22-eriksson12,
title = {High-Rank Matrix Completion},
author = {Brian Eriksson and Laura Balzano and Robert Nowak},
booktitle = {Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics},
pages = {373--381},
year = {2012},
editor = {Neil D. Lawrence and Mark Girolami},
volume = {22},
series = {Proceedings of Machine Learning Research},
address = {La Palma, Canary Islands},
month = {21--23 Apr},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v22/eriksson12/eriksson12.pdf},
url = {http://proceedings.mlr.press/v22/eriksson12.html},
abstract = {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 nxN matrix whose (complete) columns lie in a union of at most k subspaces, each of rank = r n, and assume Nkn. 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 C r N \log^2(n) entries of X are observed uniformly at random, with C1 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.}
}
%0 Conference Paper
%T High-Rank Matrix Completion
%A Brian Eriksson
%A Laura Balzano
%A Robert Nowak
%B Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics
%C Proceedings of Machine Learning Research
%D 2012
%E Neil D. Lawrence
%E Mark Girolami
%F pmlr-v22-eriksson12
%I PMLR
%J Proceedings of Machine Learning Research
%P 373--381
%U http://proceedings.mlr.press
%V 22
%W PMLR
%X 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 nxN matrix whose (complete) columns lie in a union of at most k subspaces, each of rank = r n, and assume Nkn. 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 C r N \log^2(n) entries of X are observed uniformly at random, with C1 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.
TY - CPAPER
TI - High-Rank Matrix Completion
AU - Brian Eriksson
AU - Laura Balzano
AU - Robert Nowak
BT - Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics
PY - 2012/03/21
DA - 2012/03/21
ED - Neil D. Lawrence
ED - Mark Girolami
ID - pmlr-v22-eriksson12
PB - PMLR
SP - 373
DP - PMLR
EP - 381
L1 - http://proceedings.mlr.press/v22/eriksson12/eriksson12.pdf
UR - http://proceedings.mlr.press/v22/eriksson12.html
AB - 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 nxN matrix whose (complete) columns lie in a union of at most k subspaces, each of rank = r n, and assume Nkn. 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 C r N \log^2(n) entries of X are observed uniformly at random, with C1 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.
ER -
Eriksson, B., Balzano, L. & Nowak, R.. (2012). High-Rank Matrix Completion. Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, in PMLR 22:373-381
This site last compiled Wed, 03 Jan 2018 13:53:01 +0000