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

arXiv: https://arxiv.org/abs/1309.6013 · HTML: https://mlsanity.com/paper/1309.6013/

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Sep 2013.

## Built on by (most cited first, 25 of 25)

- [High Dimensional Statistical Estimation under Uniformly Dithered One-bit Quantization](https://mlsanity.com/paper/2202.13157/) (2022)
- [Quantizing Heavy-tailed Data in Statistical Estimation: (Near) Minimax Rates, Covariate Quantization, and Uniform Recovery](https://mlsanity.com/paper/2212.14562/) (2022)
- [TenIPS: Inverse Propensity Sampling for Tensor Completion](https://mlsanity.com/paper/2101.00323/) (2021)
- [Concentration properties of fractional posterior in 1-bit matrix completion](https://mlsanity.com/paper/2404.08969/) (2024)
- [Matrix Completion with Model-free Weighting](https://mlsanity.com/paper/2106.05850/) (2021)
- [Quantized Radio Map Estimation Using Tensor and Deep Generative Models](https://mlsanity.com/paper/2303.01770/) (2023)
- [Quantized Low-Rank Multivariate Regression with Random Dithering](https://mlsanity.com/paper/2302.11197/) (2023)
- [Tensor Completion with Provable Consistency and Fairness Guarantees for Recommender Systems](https://mlsanity.com/paper/2204.01815/) (2022)
- [A Majorization-Minimization Gauss-Newton Method for 1-Bit Matrix Completion](https://mlsanity.com/paper/2304.13940/) (2023)
- [Causal Customer Churn Analysis with Low-rank Tensor Block Hazard Model](https://mlsanity.com/paper/2405.11377/) (2024)
- [A Generalized Latent Factor Model Approach to Mixed-data Matrix Completion with Entrywise Consistency](https://mlsanity.com/paper/2211.09272/) (2022)
- [Transductive Matrix Completion with Calibration for Multi-Task Learning](https://mlsanity.com/paper/2302.09834/) (2023)
- [Collaborative Automotive Radar Sensing via Mixed-Precision Distributed Array Completion](https://mlsanity.com/paper/2403.08168/) (2024)
- [Data Imputation by Pursuing Better Classification: A Supervised Kernel-Based Method](https://mlsanity.com/paper/2405.07800/) (2024)
- [Impossibility of latent inner product recovery via rate distortion](https://mlsanity.com/paper/2407.11932/) (2024)
- [Maximum a Posteriori Inference of Random Dot Product Graphs via Conic Programming](https://mlsanity.com/paper/2101.02180/) (2021)
- [One-Bit Matrix Completion with Differential Privacy](https://mlsanity.com/paper/2110.00719/) (2021)
- [An Admissible Shift-Consistent Method for Recommender Systems](https://mlsanity.com/paper/2307.08857/) (2023)
- [Matrix Completion from One-Bit Dither Samples](https://mlsanity.com/paper/2310.03224/) (2023)
- [Misclassification excess risk bounds for 1-bit matrix completion](https://mlsanity.com/paper/2312.12945/) (2023)
- [Convergence of the majorized PAM method with subspace correction for low-rank composite factorization model](https://mlsanity.com/paper/2406.04588/) (2024)
- [Pairwise Comparisons without Stochastic Transitivity: Model, Theory and Applications](https://mlsanity.com/paper/2501.07437/) (2025)
- [An Interpretable and Scalable Framework for Evaluating Large Language Models](https://mlsanity.com/paper/2605.07046/) (2026)
- [Empirical Bayes 1-bit matrix completion](https://mlsanity.com/paper/2605.09509/) (2026)
- [Exponential-Family Tensor Completion via Nonconvex Dual Total-Variation Regularization](https://mlsanity.com/paper/2606.30958/) (2026)

## Abstract (arXiv)

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.