# Matrix Completion via Max-Norm Constrained Optimization

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Mar 2013.

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

- [Causal Matrix Completion](https://mlsanity.com/paper/2109.15154/) (2021)
- [Multi-source Learning via Completion of Block-wise Overlapping Noisy Matrices](https://mlsanity.com/paper/2105.10360/) (2021)
- [Doubly robust nearest neighbors in factor models](https://mlsanity.com/paper/2211.14297/) (2022)
- [Matrix Completion with Model-free Weighting](https://mlsanity.com/paper/2106.05850/) (2021)
- [Deep Clustering with Incomplete Noisy Pairwise Annotations: A Geometric Regularization Approach](https://mlsanity.com/paper/2305.19391/) (2023)
- [Tensor Completion with Provable Consistency and Fairness Guarantees for Recommender Systems](https://mlsanity.com/paper/2204.01815/) (2022)
- [When big data actually are low-rank, or entrywise approximation of certain function-generated matrices](https://mlsanity.com/paper/2407.03250/) (2024)
- [Distributional Matrix Completion via Nearest Neighbors in the Wasserstein Space](https://mlsanity.com/paper/2410.13112/) (2024)
- [Generalization Bounds for Inductive Matrix Completion in Low-noise Settings](https://mlsanity.com/paper/2212.08339/) (2022)
- [Statistical Inference For Noisy Matrix Completion Incorporating Auxiliary Information](https://mlsanity.com/paper/2403.14899/) (2024)
- [A Generalized Latent Factor Model Approach to Mixed-data Matrix Completion with Entrywise Consistency](https://mlsanity.com/paper/2211.09272/) (2022)
- [Entry-Specific Bounds for Low-Rank Matrix Completion under Highly Non-Uniform Sampling](https://mlsanity.com/paper/2403.00184/) (2024)
- [On the Optimality of Nuclear-norm-based Matrix Completion for Problems with Smooth Non-linear Structure](https://mlsanity.com/paper/2105.01874/) (2021)
- [An Admissible Shift-Consistent Method for Recommender Systems](https://mlsanity.com/paper/2307.08857/) (2023)
- [Matrix Completion via Residual Spectral Matching](https://mlsanity.com/paper/2412.10005/) (2024)
- [Pairwise Comparisons without Stochastic Transitivity: Model, Theory and Applications](https://mlsanity.com/paper/2501.07437/) (2025)
- [Computational Efficient and Minimax Optimal Nonignorable Matrix Completion](https://mlsanity.com/paper/2504.04016/) (2025)
- [Transformed ℓ1 Regularizations for Robust Principal Component Analysis: Toward a Fine-Grained Understanding](https://mlsanity.com/paper/2510.03624/) (2025)

## Abstract (arXiv)

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.