CUR Algorithm for Partially Observed Matrices

Miao Xu, Rong Jin, Zhi-Hua Zhou
Proceedings of the 32nd International Conference on Machine Learning, PMLR 37:1412-1421, 2015.

Abstract

CUR matrix decomposition computes the low rank approximation of a given matrix by using the actual rows and columns of the matrix. It has been a very useful tool for handling large matrices. One limitation with the existing algorithms for CUR matrix decomposition is that they cannot deal with entries in a \it partially observed matrix, while incomplete matrices are found in many real world applications. In this work, we alleviate this limitation by developing a CUR decomposition algorithm for partially observed matrices. In particular, the proposed algorithm computes the low rank approximation of the target matrix based on (i) the randomly sampled rows and columns, and (ii) a subset of observed entries that are randomly sampled from the matrix. Our analysis shows the relative error bound, measured by spectral norm, for the proposed algorithm when the target matrix is of full rank. We also show that only O(n r\ln r) observed entries are needed by the proposed algorithm to perfectly recover a rank r matrix of size n\times n, which improves the sample complexity of the existing algorithms for matrix completion. Empirical studies on both synthetic and real-world datasets verify our theoretical claims and demonstrate the effectiveness of the proposed algorithm.

Cite this Paper

BibTeX
@InProceedings{pmlr-v37-xua15, title = {CUR Algorithm for Partially Observed Matrices}, author = {Xu, Miao and Jin, Rong and Zhou, Zhi-Hua}, booktitle = {Proceedings of the 32nd International Conference on Machine Learning}, pages = {1412--1421}, year = {2015}, editor = {Bach, Francis and Blei, David}, volume = {37}, series = {Proceedings of Machine Learning Research}, address = {Lille, France}, month = {07--09 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v37/xua15.pdf}, url = {https://proceedings.mlr.press/v37/xua15.html}, abstract = {CUR matrix decomposition computes the low rank approximation of a given matrix by using the actual rows and columns of the matrix. It has been a very useful tool for handling large matrices. One limitation with the existing algorithms for CUR matrix decomposition is that they cannot deal with entries in a \it partially observed matrix, while incomplete matrices are found in many real world applications. In this work, we alleviate this limitation by developing a CUR decomposition algorithm for partially observed matrices. In particular, the proposed algorithm computes the low rank approximation of the target matrix based on (i) the randomly sampled rows and columns, and (ii) a subset of observed entries that are randomly sampled from the matrix. Our analysis shows the relative error bound, measured by spectral norm, for the proposed algorithm when the target matrix is of full rank. We also show that only O(n r\ln r) observed entries are needed by the proposed algorithm to perfectly recover a rank r matrix of size n\times n, which improves the sample complexity of the existing algorithms for matrix completion. Empirical studies on both synthetic and real-world datasets verify our theoretical claims and demonstrate the effectiveness of the proposed algorithm.} }
Endnote
%0 Conference Paper %T CUR Algorithm for Partially Observed Matrices %A Miao Xu %A Rong Jin %A Zhi-Hua Zhou %B Proceedings of the 32nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2015 %E Francis Bach %E David Blei %F pmlr-v37-xua15 %I PMLR %P 1412--1421 %U https://proceedings.mlr.press/v37/xua15.html %V 37 %X CUR matrix decomposition computes the low rank approximation of a given matrix by using the actual rows and columns of the matrix. It has been a very useful tool for handling large matrices. One limitation with the existing algorithms for CUR matrix decomposition is that they cannot deal with entries in a \it partially observed matrix, while incomplete matrices are found in many real world applications. In this work, we alleviate this limitation by developing a CUR decomposition algorithm for partially observed matrices. In particular, the proposed algorithm computes the low rank approximation of the target matrix based on (i) the randomly sampled rows and columns, and (ii) a subset of observed entries that are randomly sampled from the matrix. Our analysis shows the relative error bound, measured by spectral norm, for the proposed algorithm when the target matrix is of full rank. We also show that only O(n r\ln r) observed entries are needed by the proposed algorithm to perfectly recover a rank r matrix of size n\times n, which improves the sample complexity of the existing algorithms for matrix completion. Empirical studies on both synthetic and real-world datasets verify our theoretical claims and demonstrate the effectiveness of the proposed algorithm.
RIS
TY - CPAPER TI - CUR Algorithm for Partially Observed Matrices AU - Miao Xu AU - Rong Jin AU - Zhi-Hua Zhou BT - Proceedings of the 32nd International Conference on Machine Learning DA - 2015/06/01 ED - Francis Bach ED - David Blei ID - pmlr-v37-xua15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 37 SP - 1412 EP - 1421 L1 - http://proceedings.mlr.press/v37/xua15.pdf UR - https://proceedings.mlr.press/v37/xua15.html AB - CUR matrix decomposition computes the low rank approximation of a given matrix by using the actual rows and columns of the matrix. It has been a very useful tool for handling large matrices. One limitation with the existing algorithms for CUR matrix decomposition is that they cannot deal with entries in a \it partially observed matrix, while incomplete matrices are found in many real world applications. In this work, we alleviate this limitation by developing a CUR decomposition algorithm for partially observed matrices. In particular, the proposed algorithm computes the low rank approximation of the target matrix based on (i) the randomly sampled rows and columns, and (ii) a subset of observed entries that are randomly sampled from the matrix. Our analysis shows the relative error bound, measured by spectral norm, for the proposed algorithm when the target matrix is of full rank. We also show that only O(n r\ln r) observed entries are needed by the proposed algorithm to perfectly recover a rank r matrix of size n\times n, which improves the sample complexity of the existing algorithms for matrix completion. Empirical studies on both synthetic and real-world datasets verify our theoretical claims and demonstrate the effectiveness of the proposed algorithm. ER -
APA
Xu, M., Jin, R. & Zhou, Z.. (2015). CUR Algorithm for Partially Observed Matrices. Proceedings of the 32nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 37:1412-1421 Available from https://proceedings.mlr.press/v37/xua15.html.

Related Material