A Max-Norm Constrained Minimization Approach to 1-Bit Matrix Completion
arXiv:1309.6013
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.
arXiv comment33 pages, 3 figures
References in corpus (7)
- Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
- Regime Change: Bit-Depth versus Measurement-Rate in Compressive Sensing
- Matrix Completion via Max-Norm Constrained Optimization
- Collaborative Filtering in a Non-Uniform World: Learning with the Weighted Trace Norm
- Note on sampling without replacing from a finite collection of matrices
- Optimistic Rates for Learning with a Smooth Loss
- Learning with the Weighted Trace-norm under Arbitrary Sampling Distributions
Cited by in corpus (37)
- 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
- Matrix Completion via Max-Norm Constrained 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
- Network cross-validation by edge sampling
- Item Response Theory -- A Statistical Framework for Educational and Psychological Measurement
- 1-Bit Matrix Completion under Exact Low-Rank Constraint
- Learning from Binary Multiway Data: Probabilistic Tensor Decomposition and its Statistical Optimality
- A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimation
- 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
- Quantized Matrix Completion for Personalized Learning
- Tensor denoising and completion based on ordinal observations
- Imputation and low-rank estimation with Missing Not At Random data
- Flexible Low-Rank Statistical Modeling with Side Information
- Spectral State Compression of Markov Processes
- Social Trust Prediction via Max-norm Constrained 1-bit Matrix Completion
- Binary Matrix Completion Using Unobserved Entries
- Joint Maximum Likelihood Estimation for High-dimensional Exploratory Item Response Analysis
- Unfolding-Model-Based Visualization: Theory, Method and Applications
- Regret Bounds for Non-decomposable Metrics with Missing Labels
- Categorical Matrix Completion
- Relative Error Bound Analysis for Nuclear Norm Regularized Matrix Completion
- TenIPS: Inverse Propensity Sampling for Tensor Completion
- Robust Matrix Completion with Mixed Data Types
- Online network change point detection with missing values and temporal dependence
- Online Optimization for Large-Scale Max-Norm Regularization
- Cluster Developing 1-Bit Matrix Completion
- Binary matrix completion with nonconvex regularizers
- SAR: Semantic Analysis for Recommendation
- One-Bit Matrix Completion with Differential Privacy