A Max-Norm Constrained Minimization Approach to 1-Bit Matrix Completion

Abstract

We consider in this paper the problem of noisy 1-bit matrix completion under a general non-uniform sampling distribution using the max-norm as a convex relaxation for the rank. A max-norm constrained maximum likelihood estimate is introduced and studied. The rate of convergence for the estimate is obtained. Information-theoretical methods are used to establish a minimax lower bound under the general sampling model. The minimax upper and lower bounds together yield the optimal rate of convergence for the Frobenius norm loss. Computational algorithms and numerical performance are also discussed.

33 pages, 3 figures

References in corpus (3)

• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Collaborative Filtering in a Non-Uniform World: Learning with the Weighted Trace Norm
• Learning with the Weighted Trace-norm under Arbitrary Sampling Distributions

Cited by in corpus (36)

• An overview of low-rank matrix recovery from incomplete observations
• Inference and Uncertainty Quantification for Noisy Matrix Completion
• Global Optimality in Low-rank Matrix Optimization
• Learning tensors from partial binary measurements
• 1-bit Matrix Completion: PAC-Bayesian Analysis of a Variational Approximation
• The Global Optimization Geometry of Low-Rank Matrix Optimization
• Low Rank Matrix Completion with Exponential Family Noise
• Probabilistic low-rank matrix completion on finite alphabets
• Item Response Theory -- A Statistical Framework for Educational and Psychological Measurement
• Network cross-validation by edge sampling
• 1-Bit Matrix Completion under Exact Low-Rank Constraint
• A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimation
• Learning from Binary Multiway Data: Probabilistic Tensor Decomposition and its Statistical Optimality
• A Universal Variance Reduction-Based Catalyst for Nonconvex Low-Rank Matrix Recovery
• Recursive Importance Sketching for Rank Constrained Least Squares: Algorithms and High-order Convergence
• Generalized High-Dimensional Trace Regression via Nuclear Norm Regularization
• Tensor denoising and completion based on ordinal observations
• Quantized Matrix Completion for Personalized Learning
• Flexible Low-Rank Statistical Modeling with Side Information
• Imputation and low-rank estimation with Missing Not At Random data
• Spectral State Compression of Markov Processes
• Regret Bounds for Non-decomposable Metrics with Missing Labels
• Joint Maximum Likelihood Estimation for High-dimensional Exploratory Item Response Analysis
• Social Trust Prediction via Max-norm Constrained 1-bit Matrix Completion
• Unfolding-Model-Based Visualization: Theory, Method and Applications
• Categorical Matrix Completion
• Binary Matrix Completion Using Unobserved Entries
• TenIPS: Inverse Propensity Sampling for Tensor Completion
• Relative Error Bound Analysis for Nuclear Norm Regularized Matrix Completion
• One-Bit Matrix Completion with Differential Privacy
• Robust Matrix Completion with Mixed Data Types
• SAR: Semantic Analysis for Recommendation
• Cluster Developing 1-Bit Matrix Completion
• Binary matrix completion with nonconvex regularizers
• Online Optimization for Large-Scale Max-Norm Regularization
• Online network change point detection with missing values and temporal dependence