Nuclear Norm-Regularized Bayesian Matrix Completion

Calvin Tolbert

stat.MLSep 24, 2026

Nuclear Norm-Regularized Bayesian Matrix Completion

Authors: Calvin Tolbert

Organizations: School of Operations Research and Information Engineering Cornell University

Abstract

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.

Figures & tables

Symbol	Role
$\sigma$	RWM proposal step size
$A(t)$	Intermediate bound on $\mathbb{E}\\|\bm{L}\\|_{\mathrm{F}}^{2}$ feeding $u_{0}$
$u_{0}(t)$	Log of the burn-in chi-squared divergence $\chi^{2}(\mu_{t}^{0}\\|\mu_{t})$
$R_{1}$	Bound on $\mathbb{E}_{\mu}[R(\bm{L})]$
$R_{2}$	Bound on $\mathbb{E}_{\mu}[R(\bm{L})^{2}]$
$\widetilde{R}_{2}$	$R_{1}^{2}+2BR_{1}$

Table 1: Glossary of auxiliary quantities

Symbol	Value
$\sigma$	$\frac{\lambda}{4n_{1}\sqrt{n_{2}}}$
$A(t)$	$\frac{Bn_{1}n_{2}}{2}+\left(1-\frac{2}{Bt+2}\right)^{2}\\|\bm{Y\circ\Omega}\\|_{\mathrm{F}}^{2}$
$u_{0}(t)$	$\exp\!\left(\frac{\sqrt{n_{1}A(t)}}{\lambda}+\frac{Bn_{1}}{4\lambda^{2}}\right)-1$
$R_{1}$	$\\|\bm{Y\circ\Omega}\\|_{\mathrm{F}}^{2}+\frac{NB}{2}$
$R_{2}$	$\left(\\|\bm{Y\circ\Omega}\\|_{\mathrm{F}}+\left(\frac{N(N+2)B^{2}}{4}\right)^{\frac{1}{4}}\right)^{4}$
$\widetilde{R}_{2}$	$R_{1}^{2}+2BR_{1}$

Table 2: Values of auxiliary quantities

Figure 1: Marginalizing $\tau$ on toy $n\times n$ matrices, $n=6,\dots,16$ . (A) The effective-sample-size fraction of naive importance sampling from the untilted prior collapses as $N$ grows. (B) The relative Monte Carlo error of the thermodynamic-integration estimator over the same range of $N$ stays bounded, at a comparable total sampling budget. Different units in each panel; do not compare on one axis.

Figure 2: Posterior on the noise precision $\tau$ and on the leading singular value of $\bm{L}$ : Gibbs sampling (heuristic, no guarantee) versus our thermodynamic-integration-based sampler, at matched practical step budgets. The cross-method gap is within each method’s own split-half Monte Carlo noise.

Explore similar work

Sep 15, 2026math.NA

Near-Optimal Nonconvex Matrix Completion

We study nonconvex methods for matrix completion, the problem of recovering a low-rank matrix from a subset of its entries. Convex methods achieve sample complexity linear in the matrix dimension and the rank, up to logarithmic factors, whereas global guarantees for commonly used nonconvex methods require a higher polynomial dependence on the rank. We close this gap by analyzing Riemannian gradient descent (RGD) and Riemannian Gauss--Newton (RGN) methods. For an

n\times n

matrix of rank

r

with incoherence parameter

μ

and condition number

κ

, the two methods achieve exact recovery with high probability from

O(μnr\log n\log(nκ))

and

O(μnr\log n\log(2μrκ))

observations, respectively. The methods use a multiscale residual initialization, while the analysis simultaneously controls the spectral error and incoherence. The resulting RGD iterates converge linearly, whereas RGN eventually converges Q-quadratically.

Jian-Feng Cai, Xiliang Lu, Juntao You

Department of Mathematics, Hong Kong University of Science and Technology. · School of Mathematics and Statistics, Hubei Center for Applied Mathematics, and Hubei Key Laboratory of Computational Science, Wuhan University, Wuhan 430072, China. · School of Artificial Intelligence, Hubei Center for Applied Mathematics, and Hubei Key Laboratory of Computational Science, Wuhan University, Wuhan 430072, China.

Tensor Completion Convex Optimization Sample Complexity

Ask PDF

Dec 1, 2023stat.ME

Multiple Testing of Linear Forms for Noisy Matrix Completion

Many important tasks of large-scale recommender systems can be naturally cast as testing multiple linear forms for noisy matrix completion. These problems, however, present unique challenges because of the subtle bias-and-variance tradeoff of and an intricate dependence among the estimated entries induced by the low-rank structure. In this paper, we develop a general approach to overcome these difficulties by introducing new statistics for individual tests with sharp asymptotics both marginally and jointly, and utilizing them to control the false discovery rate (FDR) via a data splitting and symmetric aggregation scheme. We show that valid FDR control can be achieved with guaranteed power under nearly optimal sample size requirements using the proposed methodology. Extensive numerical simulations and real data examples are also presented to further illustrate its practical merits.

Wanteng Ma, Lilun Du, Dong Xia +1

Department of Statistics and Data Science, University of Pennsylvania, USA · Department of Decision Analytics and Operations, City University of Hong Kong, Hong Kong · Department of Mathematics, Hong Kong University of Science and Technology, Hong Kong +1

Tensor Completion False Discovery Rate Sample Size Noisy Data Solver Iterations Bias-Variance Decomposition

Ask PDF

May 10, 2026stat.ML

Empirical Bayes 1-bit matrix completion

The problem of predicting unobserved entries in a binary matrix, known as 1-bit matrix completion, has found diverse applications in fields such as recommendation systems. In this study, we develop an empirical Bayes method for 1-bit matrix completion motivated by the Efron--Morris estimator, a matrix generalization of the James--Stein estimator that shrinks singular values toward zero. The proposed method exploits the underlying low-rank structure of binary matrices, drawing parallels with multidimensional item response theory. Simulation studies and real-data applications demonstrate that the proposed method achieves a superior balance of predictive accuracy, calibration reliability (uncertainty quantification), and computational efficiency compared to existing methods.

Takeru Matsuda

Department of Mathematical Informatics, Graduate School of Information Science and Technology, The University of Tokyo · Statistical Mathematics Unit, RIKEN Center for Brain Science

Tensor Completion Empirical Bayes Imputation Bits Item Response Theory

Ask PDF