# Nuclear Norm-Regularized Bayesian Matrix Completion

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 25 references that are in the map.
- First posted on arXiv 24 Sep 2026.

## Builds on (most cited first, 10 of 10)

- [Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1507.05021/) (2015)
- [Log-concave sampling: Metropolis-Hastings algorithms are fast](https://mlsanity.com/paper/1801.02309/) (2018)
- [Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients](https://mlsanity.com/paper/1905.12247/) (2019)
- [Causal Matrix Completion](https://mlsanity.com/paper/2109.15154/) (2021)
- [Primal Dual Interpretation of the Proximal Stochastic Gradient Langevin Algorithm](https://mlsanity.com/paper/2006.09270/) (2020)
- [Bridging Convex and Nonconvex Optimization in Robust PCA: Noise, Outliers, and Missing Data](https://mlsanity.com/paper/2001.05484/) (2020)
- [Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlo](https://mlsanity.com/paper/2002.04121/) (2020)
- [An Efficient Sampling Algorithm for Non-smooth Composite Potentials](https://mlsanity.com/paper/1910.00551/) (2019)
- [Stochastic Proximal Langevin Algorithm: Potential Splitting and Nonasymptotic Rates](https://mlsanity.com/paper/1905.11768/) (2019)
- [Low-rank Bayesian matrix completion via geodesic Hamiltonian Monte Carlo on Stiefel manifolds](https://mlsanity.com/paper/2410.20318/) (2024)

## Abstract (arXiv)

Matrix completion, the problem of estimating missing entries in a matrix from noisily observed ones, underlies a diverse array of problems such as recommender systems and counterfactual outcome estimation in panel data. Many algorithms address the problem using regularized least squares, often with the nuclear norm as a regularizer, but this method yields a point estimate with no built-in uncertainty quantification. A Bayesian formulation is a natural alternative, and if the noise variance is known, the nuclear norm-based prior yields a log-concave posterior. Unfortunately, in practice, the noise variance will not be known a priori, so for a fully Bayesian approach, a prior must be imposed on it. We give the first sampler for this model with an explicit non-asymptotic guarantee: polynomial in the matrix dimensions and in the reciprocal of the target accuracy. Our technique is to discretize the distribution of the noise precision onto a grid and build a categorical posterior via thermodynamic integration. This extension is not specific to matrix completion and may be useful in other non-log-concave sampling problems where the non-log-concavity is restricted to a single variable and the joint distribution of the remaining variables is nonsmooth. Our contribution is a feasibility result: we show that a polynomial-time Bayesian sampler for this model exists at all, and the resulting complexity, while polynomial, is not intended as a deployable algorithm at current problem scales.