BibTeX Entry

  author	= {Ruchansky, Natali and Terzi, Evimaria and Crovella, Mark},
  title		= {Targeted Matrix Completion},
  booktitle	= {Proceedings of the SIAM International Conference on Data Mining (SDM)},
  year		= {2017},
  month		= apr,
  address	= {Houston, TX},
  doi		= {TBD},
  URL		= {},
  abstract	= {Matrix completion is a problem that arises in many data-analysis settings where the input consists of a partially-observed matrix (e.g., recommender systems, traffic matrix analysis etc.). Classical approaches to matrix completion assume that the input partially-observed matrix is low rank. The success of these methods depend on the number of observed entries and the actual rank of the matrix; the larger the rank, the more entries need to be observed in order to accurately complete the input matrix. In this paper, we deal with matrices that are not necessarily low rank themselves, but rather they contain many low-rank submatrices. For these matrices, we propose Targeted, which is a general framework for completing such matrices. In this framework, we first extract the low-rank submatrices and then we apply a matrix-completion algorithm to these low-rank submatrices as well as the remainder matrix (once the submatrices are removed) separately. Although for the completion itself we use state-of-the-art completion methods, our results demonstrate that Targeted achieves significantly smaller reconstruction errors than other classical matrix-completion methods. One of the key technical contributions of the paper lies in the identification of the low-rank submatrices from the input partially-observed matrices.},