CUR Algorithm for Partially Observed Matrices

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 need an access to the {\it full} matrix, a requirement that can be difficult to fulfill 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(nr\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.

References in corpus (12)

• A Simpler Approach to Matrix Completion
• Estimation of high-dimensional low-rank matrices
• Consistency of trace norm minimization
• Fast approximation of matrix coherence and statistical leverage
• Improving CUR Matrix Decomposition and the Nyström Approximation via Adaptive Sampling
• Universal Matrix Completion
• Near-Optimal Column-Based Matrix Reconstruction
• High-Rank Matrix Completion and Subspace Clustering with Missing Data
• Estimation of (near) low-rank matrices with noise and high-dimensional scaling
• Optimal CUR Matrix Decompositions
• CUR from a Sparse Optimization Viewpoint
• A Scalable CUR Matrix Decomposition Algorithm: Lower Time Complexity and Tighter Bound

Cited by in corpus (7)

• Provably Correct Algorithms for Matrix Column Subset Selection with Selectively Sampled Data
• Matrix Completion with Cross-Concentrated Sampling: Bridging Uniform Sampling and CUR Sampling
• A divide-and-conquer algorithm for binary matrix completion
• Matrix Completion from Non-Uniformly Sampled Entries
• CUR Decompositions, Approximations, and Perturbations
• Perspectives on CUR Decompositions
• NoisyCUR: An algorithm for two-cost budgeted matrix completion