mlsanityData to 14 Oct 2026

Matrix Completion via Max-Norm Constrained Optimization

arXiv 1303.0341 ↗First posted 2 Mar 2013cs.LG cs.IT math.ITcited by 18

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 4; 2022: 4; 2023: 2; 2024: 5; 2025: 3.

18 papers.

Sort:

  1. 2021Causal Matrix Completioncited by 45
  2. 2021Multi-source Learning via Completion of Block-wise Overlapping Noisy Matricescited by 10
  3. 2022Doubly robust nearest neighbors in factor modelscited by 9
  4. 2021Matrix Completion with Model-free Weightingcited by 6
  5. 2023Deep Clustering with Incomplete Noisy Pairwise Annotations: A Geometric Regularization Approachcited by 5
  6. 2022Tensor Completion with Provable Consistency and Fairness Guarantees for Recommender Systemscited by 4
  7. 2024When big data actually are low-rank, or entrywise approximation of certain function-generated matricescited by 3
  8. 2024Distributional Matrix Completion via Nearest Neighbors in the Wasserstein Spacecited by 3
  9. 2022Generalization Bounds for Inductive Matrix Completion in Low-noise Settingscited by 2
  10. 2024Statistical Inference For Noisy Matrix Completion Incorporating Auxiliary Informationcited by 2
  11. 2022A Generalized Latent Factor Model Approach to Mixed-data Matrix Completion with Entrywise Consistencycited by 1
  12. 2024Entry-Specific Bounds for Low-Rank Matrix Completion under Highly Non-Uniform Samplingcited by 1
6 more
  1. 2021On the Optimality of Nuclear-norm-based Matrix Completion for Problems with Smooth Non-linear Structurecited by 0
  2. 2023An Admissible Shift-Consistent Method for Recommender Systemscited by 0
  3. 2024Matrix Completion via Residual Spectral Matchingcited by 0
  4. 2025Pairwise Comparisons without Stochastic Transitivity: Model, Theory and Applicationscited by 0
  5. 2025Computational Efficient and Minimax Optimal Nonignorable Matrix Completioncited by 0
  6. 2025Transformed ℓ1 Regularizations for Robust Principal Component Analysis: Toward a Fine-Grained Understandingcited by 0