# Max-Norm Optimization for Robust Matrix Recovery

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

## Key facts

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

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

- [Multi-source Learning via Completion of Block-wise Overlapping Noisy Matrices](https://mlsanity.com/paper/2105.10360/) (2021)
- [Matrix Completion with Model-free Weighting](https://mlsanity.com/paper/2106.05850/) (2021)
- [Mixed Matrix Completion in Complex Survey Sampling under Heterogeneous Missingness](https://mlsanity.com/paper/2402.03954/) (2024)
- [An inexact LPA for DC composite optimization and application to matrix completions with outliers](https://mlsanity.com/paper/2303.16822/) (2023)
- [Transformed ℓ1 Regularizations for Robust Principal Component Analysis: Toward a Fine-Grained Understanding](https://mlsanity.com/paper/2510.03624/) (2025)

## Abstract (arXiv)

This paper studies the matrix completion problem under arbitrary sampling schemes. We propose a new estimator incorporating both max-norm and nuclear-norm regularization, based on which we can conduct efficient low-rank matrix recovery using a random subset of entries observed with additive noise under general non-uniform and unknown sampling distributions. This method significantly relaxes the uniform sampling assumption imposed for the widely used nuclear-norm penalized approach, and makes low-rank matrix recovery feasible in more practical settings. Theoretically, we prove that the proposed estimator achieves fast rates of convergence under different settings. Computationally, we propose an alternating direction method of multipliers algorithm to efficiently compute the estimator, which bridges a gap between theory and practice of machine learning methods with max-norm regularization. Further, we provide thorough numerical studies to evaluate the proposed method using both simulated and real datasets.