Matrix Completion via Max-Norm Constrained Optimization
arXiv:1303.0341 · doi:10.1214/16-EJS1147
Abstract
Matrix completion has been well studied under the uniform sampling model and the trace-norm regularized methods perform well both theoretically and numerically in such a setting. However, the uniform sampling model is unrealistic for a range of applications and the standard trace-norm relaxation can behave very poorly when the underlying sampling scheme is non-uniform. In this paper we propose and analyze a max-norm constrained empirical risk minimization method for noisy matrix completion under a general sampling model. The optimal rate of convergence is established under the Frobenius norm loss in the context of approximately low-rank matrix reconstruction. It is shown that the max-norm constrained method is minimax rate-optimal and yields a unified and robust approximate recovery guarantee, with respect to the sampling distributions. The computational effectiveness of this method is also discussed, based on first-order algorithms for solving convex optimizations involving max-norm regularization.
arXiv comment33 pages
References in corpus (12)
- A Simpler Approach to Matrix Completion
- User-friendly tail bounds for sums of random matrices
- Recovering low-rank matrices from few coefficients in any basis
- Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
- Estimation of high-dimensional low-rank matrices
- Tight oracle bounds for low-rank matrix recovery from a minimal number of random measurements
- Noisy low-rank matrix completion with general sampling distribution
- A Max-Norm Constrained Minimization Approach to 1-Bit Matrix Completion
- Collaborative Filtering in a Non-Uniform World: Learning with the Weighted Trace Norm
- Concentration-Based Guarantees for Low-Rank Matrix Reconstruction
- Optimistic Rates for Learning with a Smooth Loss
- Learning with the Weighted Trace-norm under Arbitrary Sampling Distributions
Cited by in corpus (26)
- Inference and Uncertainty Quantification for Noisy Matrix Completion
- A Max-Norm Constrained Minimization Approach to 1-Bit Matrix Completion
- Learning subgaussian classes : Upper and minimax bounds
- Learning tensors from partial binary measurements
- Low Rank Matrix Completion with Exponential Family Noise
- Geometric Inference for General High-Dimensional Linear Inverse Problems
- Probabilistic low-rank matrix completion on finite alphabets
- Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization
- Statistical Inferences of Linear Forms for Noisy Matrix Completion
- Towards Faster Rates and Oracle Property for Low-Rank Matrix Estimation
- Deterministic tensor completion with hypergraph expanders
- Tensor Completion with Provable Consistency and Fairness Guarantees for Recommender Systems
- Cross: Efficient Low-rank Tensor Completion
- Multi-source Learning via Completion of Block-wise Overlapping Noisy Matrices
- Entrywise tensor-train approximation of large tensors via random embeddings
- Identifying Influential Entries in a Matrix
- Statistical Inference For Noisy Matrix Completion Incorporating Auxiliary Information
- HOSVD-Based Algorithm for Weighted Tensor Completion
- Outlier-robust sparse/low-rank least-squares regression and robust matrix completion
- Intelligent Initialization and Adaptive Thresholding for Iterative Matrix Completion; Some Statistical and Algorithmic Theory for Adaptive-Impute
- Structured Matrix Completion with Applications to Genomic Data Integration
- Binary matrix completion with nonconvex regularizers
- Online network change point detection with missing values and temporal dependence
- Entry-Specific Bounds for Low-Rank Matrix Completion under Highly Non-Uniform Sampling
- Robust Matrix Completion with Mixed Data Types
- Matrix Completion for Survey Data Prediction with Multivariate Missingness