Identifying Influential Entries in a Matrix
arXiv:1310.3556
Abstract
For any matrix A in R^(m x n) of rank ρ, we present a probability distribution over the entries of A (the element-wise leverage scores of equation (2)) that reveals the most influential entries in the matrix. From a theoretical perspective, we prove that sampling at most s = O ((m + n) ρ^2 ln (m + n)) entries of the matrix (see eqn. (3) for the precise value of s) with respect to these scores and solving the nuclear norm minimization problem on the sampled entries, reconstructs A exactly. To the best of our knowledge, these are the strongest theoretical guarantees on matrix completion without any incoherence assumptions on the matrix A. From an experimental perspective, we show that entries corresponding to high element-wise leverage scores reveal structural properties of the data matrix that are of interest to domain scientists.
arXiv commentThere is a bug in the proof of Lemma 5, which we are currently working to fix
References in corpus (8)
- A Simpler Approach to Matrix Completion
- Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
- Fast approximation of matrix coherence and statistical leverage
- Randomized algorithms for matrices and data
- Matrix Completion via Max-Norm Constrained Optimization
- Low-rank Matrix Completion using Alternating Minimization
- Completing Any Low-rank Matrix, Provably
- Low-rank Matrix Recovery from Errors and Erasures