Restricted strong convexity and weighted matrix completion: Optimal bounds with noise

Abstract

We consider the matrix completion problem under a form of row/column weighted entrywise sampling, including the case of uniform entrywise sampling as a special case. We analyze the associated random observation operator, and prove that with high probability, it satisfies a form of restricted strong convexity with respect to weighted Frobenius norm. Using this property, we obtain as corollaries a number of error bounds on matrix completion in the weighted Frobenius norm under noisy sampling and for both exact and near low-rank matrices. Our results are based on measures of the "spikiness" and "low-rankness" of matrices that are less restrictive than the incoherence conditions imposed in previous work. Our technique involves an $M$-estimator that includes controls on both the rank and spikiness of the solution, and we establish non-asymptotic error bounds in weighted Frobenius norm for recovering matrices lying with ${\ell }_q$-"balls" of bounded spikiness. Using information-theoretic methods, we show that no algorithm can achieve better estimates (up to a logarithmic factor) over these same sets, showing that our conditions on matrices and associated rates are essentially optimal.

References in corpus (2)

• Consistency of trace norm minimization
• Collaborative Filtering in a Non-Uniform World: Learning with the Weighted Trace Norm

Cited by in corpus (27)

• Matrix Completion on Graphs
• Provable Tensor Factorization with Missing Data
• Learning with the Weighted Trace-norm under Arbitrary Sampling Distributions
• Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares
• Low Rank Matrix Completion with Exponential Family Noise
• On the Power of Adaptivity in Matrix Completion and Approximation
• Probabilistic low-rank matrix completion on finite alphabets
• Collaboratively Learning Preferences from Ordinal Data
• Regularization and the small-ball method II: complexity dependent error rates
• Learning Mixed Multinomial Logit Model from Ordinal Data
• Dynamic matrix recovery from incomplete observations under an exact low-rank constraint
• A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimation
• Towards Faster Rates and Oracle Property for Low-Rank Matrix Estimation
• Individualized Rank Aggregation using Nuclear Norm Regularization
• Speeding Up Latent Variable Gaussian Graphical Model Estimation via Nonconvex Optimizations
• Matrix reconstruction with the local max norm
• A Universal Variance Reduction-Based Catalyst for Nonconvex Low-Rank Matrix Recovery
• Advancing Matrix Completion by Modeling Extra Structures beyond Low-Rankness
• Noisy Inductive Matrix Completion Under Sparse Factor Models
• Stochastic Variance-reduced Gradient Descent for Low-rank Matrix Recovery from Linear Measurements
• Estimation of low rank density matrices by Pauli measurements
• Consistent Collective Matrix Completion under Joint Low Rank Structure
• Poisson Matrix Completion
• A multi-stage convex relaxation approach to noisy structured low-rank matrix recovery
• Convergence rate of Bayesian tensor estimator: Optimal rate without restricted strong convexity
• Convex Optimization Learning of Faithful Euclidean Distance Representations in Nonlinear Dimensionality Reduction
• Learning Parameters for Weighted Matrix Completion via Empirical Estimation