Fundamental Limits of Matrix Sensing: Exact Asymptotics, Universality, and Applications

Yizhou Xu, Antoine Maillard, Lenka Zdeborová, Florent Krzakala
Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:5757-5823, 2025.

Abstract

In the matrix sensing problem, one wishes to reconstruct a matrix from (possibly noisy) observations of its linear projections along given directions. We consider this model in the high-dimensional limit: while previous works on this model primarily focused on the recovery of low-rank matrices, we consider in this work more general classes of structured signal matrices with potentially large rank, e.g. a product of two matrices of sizes proportional to the dimension. We provide rigorous asymptotic equations characterizing the Bayes-optimal learning performance from a number of samples which is proportional to the number of entries in the matrix. Our proof is composed of three key ingredients: $(i)$ we prove universality properties to handle structured sensing matrices, related to the “Gaussian equivalence” phenomenon in statistical learning, $(ii)$ we provide a sharp characterization of Bayes-optimal learning in generalized linear models with Gaussian data and structured matrix priors, generalizing previously studied settings, and $(iii)$ we leverage previous works on the problem of matrix denoising. The generality of our results allow for a variety of applications: notably, we mathematically establish predictions obtained via non-rigorous methods from statistical physics in Erba et al. (2024) regarding Bilinear Sequence Regression, a benchmark model for learning from sequences of tokens, and in Maillard et al. (2024) on Bayes-optimal learning in neural networks with quadratic activation function, and width proportional to the dimension.

Cite this Paper

BibTeX
@InProceedings{pmlr-v291-xu25a, title = {Fundamental Limits of Matrix Sensing: Exact Asymptotics, Universality, and Applications}, author = {Xu, Yizhou and Maillard, Antoine and Zdeborov\'a, Lenka and Krzakala, Florent}, booktitle = {Proceedings of Thirty Eighth Conference on Learning Theory}, pages = {5757--5823}, year = {2025}, editor = {Haghtalab, Nika and Moitra, Ankur}, volume = {291}, series = {Proceedings of Machine Learning Research}, month = {30 Jun--04 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v291/main/assets/xu25a/xu25a.pdf}, url = {https://proceedings.mlr.press/v291/xu25a.html}, abstract = {In the matrix sensing problem, one wishes to reconstruct a matrix from (possibly noisy) observations of its linear projections along given directions. We consider this model in the high-dimensional limit: while previous works on this model primarily focused on the recovery of low-rank matrices, we consider in this work more general classes of structured signal matrices with potentially large rank, e.g. a product of two matrices of sizes proportional to the dimension. We provide rigorous asymptotic equations characterizing the Bayes-optimal learning performance from a number of samples which is proportional to the number of entries in the matrix. Our proof is composed of three key ingredients: $(i)$ we prove universality properties to handle structured sensing matrices, related to the “Gaussian equivalence” phenomenon in statistical learning, $(ii)$ we provide a sharp characterization of Bayes-optimal learning in generalized linear models with Gaussian data and structured matrix priors, generalizing previously studied settings, and $(iii)$ we leverage previous works on the problem of matrix denoising. The generality of our results allow for a variety of applications: notably, we mathematically establish predictions obtained via non-rigorous methods from statistical physics in Erba et al. (2024) regarding Bilinear Sequence Regression, a benchmark model for learning from sequences of tokens, and in Maillard et al. (2024) on Bayes-optimal learning in neural networks with quadratic activation function, and width proportional to the dimension.} }
Endnote
%0 Conference Paper %T Fundamental Limits of Matrix Sensing: Exact Asymptotics, Universality, and Applications %A Yizhou Xu %A Antoine Maillard %A Lenka Zdeborová %A Florent Krzakala %B Proceedings of Thirty Eighth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2025 %E Nika Haghtalab %E Ankur Moitra %F pmlr-v291-xu25a %I PMLR %P 5757--5823 %U https://proceedings.mlr.press/v291/xu25a.html %V 291 %X In the matrix sensing problem, one wishes to reconstruct a matrix from (possibly noisy) observations of its linear projections along given directions. We consider this model in the high-dimensional limit: while previous works on this model primarily focused on the recovery of low-rank matrices, we consider in this work more general classes of structured signal matrices with potentially large rank, e.g. a product of two matrices of sizes proportional to the dimension. We provide rigorous asymptotic equations characterizing the Bayes-optimal learning performance from a number of samples which is proportional to the number of entries in the matrix. Our proof is composed of three key ingredients: $(i)$ we prove universality properties to handle structured sensing matrices, related to the “Gaussian equivalence” phenomenon in statistical learning, $(ii)$ we provide a sharp characterization of Bayes-optimal learning in generalized linear models with Gaussian data and structured matrix priors, generalizing previously studied settings, and $(iii)$ we leverage previous works on the problem of matrix denoising. The generality of our results allow for a variety of applications: notably, we mathematically establish predictions obtained via non-rigorous methods from statistical physics in Erba et al. (2024) regarding Bilinear Sequence Regression, a benchmark model for learning from sequences of tokens, and in Maillard et al. (2024) on Bayes-optimal learning in neural networks with quadratic activation function, and width proportional to the dimension.
APA
Xu, Y., Maillard, A., Zdeborová, L. & Krzakala, F.. (2025). Fundamental Limits of Matrix Sensing: Exact Asymptotics, Universality, and Applications. Proceedings of Thirty Eighth Conference on Learning Theory, in Proceedings of Machine Learning Research 291:5757-5823 Available from https://proceedings.mlr.press/v291/xu25a.html.

Related Material