Identifying Influential Entries in a Matrix
This addresses matrix completion for researchers in machine learning and data science by providing strong theoretical guarantees without incoherence assumptions, though it is incremental in improving existing methods.
The paper tackles the problem of identifying influential entries in a matrix by proposing a probability distribution based on element-wise leverage scores, proving that sampling O((m+n)ρ^2 ln(m+n)) entries and using nuclear norm minimization can exactly reconstruct the matrix without incoherence assumptions. Experimentally, high leverage scores reveal structural properties of interest to domain scientists.
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.