Nuclear Norm-Regularized Bayesian Matrix Completion
Abstract
Nuclear-norm-regularized least squares is a standard approach to matrix completion, but it yields only a point estimate. Its Bayesian counterpart, a prior combining the nuclear norm with a Frobenius-norm term, gives a strongly log-concave though nonsmooth posterior when the noise precision is known. In practice the precision is unknown, and placing a truncated Jeffreys prior on it makes the joint posterior neither log-concave nor smooth. To our knowledge, we give the first sampler for this model with an explicit non-asymptotic guarantee: its output is within a prescribed total-variation or Wasserstein distance of the posterior on the matrix after a number of steps polynomial in the matrix dimensions and the reciprocal of the target accuracy. The sampler never targets a continuous distribution that is not strongly log-concave. It discretizes the precision onto a grid, estimates its posterior by thermodynamic integration along the tilted conditional posteriors of the matrix, and bounds the error this propagates to the posterior on the matrix. The approach applies whenever non-log-concavity is confined to a bounded scalar hyperparameter and the conditional distributions are strongly log-concave with smooth-plus-Lipschitz potentials. Our result establishes feasibility; the polynomial complexity is not intended as a practical algorithm at current problem scales.
Related
- A Nuclear-Norm Lower Bound for Dithered Scalar Quantization of Matrix Products
- Notes on the discretization of TV-NORM regularized inverse potential problems
- Rank Stabilization for Sparse Coordinate Completion of Unit-Norm Tight Frames
- Robust low-rank tensor completion via factorized weighted tensor schatten-p norm minimization
- Matrix Completion Discriminants
BibTeX
@misc{tolbert2026nuclear,
title = {{Nuclear Norm-Regularized Bayesian Matrix Completion}},
author = {Calvin Tolbert},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.30078},
eprint = {2609.30078},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.30078},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Nuclear Norm-Regularized Bayesian Matrix Completion
AU - Calvin Tolbert
PY - 2026
DA - 2026/10/27
PB - arXiv
DO - 10.48550/arxiv.2609.30078
UR - https://arxiv.org/abs/2609.30078
AB - Nuclear-norm-regularized least squares is a standard approach to matrix completion, but it yields only a point estimate. Its Bayesian counterpart, a prior combining the nuclear norm with a Frobenius-norm term, gives a strongly log-concave though nonsmooth posterior when the noise precision is known. In practice the precision is unknown, and placing a truncated Jeffreys prior on it makes the joint posterior neither log-concave nor smooth. To our knowledge, we give the first sampler for this model with an explicit non-asymptotic guarantee: its output is within a prescribed total-variation or Wasserstein distance of the posterior on the matrix after a number of steps polynomial in the matrix dimensions and the reciprocal of the target accuracy. The sampler never targets a continuous distribution that is not strongly log-concave. It discretizes the precision onto a grid, estimates its posterior by thermodynamic integration along the tilted conditional posteriors of the matrix, and bounds the error this propagates to the posterior on the matrix. The approach applies whenever non-log-concavity is confined to a bounded scalar hyperparameter and the conditional distributions are strongly log-concave with smooth-plus-Lipschitz potentials. Our result establishes feasibility; the polynomial complexity is not intended as a practical algorithm at current problem scales.
ER -