A multiscale cavity method for sublinear-rank symmetric matrix factorization

Jean Barbier, Justin Ko, Anas A. Rahman

Abstract

We consider a statistical model for symmetric matrix factorization with additive Gaussian noise in the high-dimensional regime where the rank $M$ of the signal matrix to infer scales with its size $N$ as $M={\rm o}(\sqrt{\ln N})$. Allowing for an $N$-dependent rank offers new challenges and requires new methods. Working in the Bayes-optimal setting, we show that whenever the signal has i.i.d.~entries, the limiting mutual information between signal and data is given by a variational formula involving a rank-one replica symmetric potential. In other words, from the information-theoretic perspective, the case of a (slowly) growing rank is the same as when $M=1$ (namely, the standard spiked Wigner model). The proof is primarily based on a novel multiscale cavity method allowing for growing rank along with some information-theoretic identities on worst noise for the vector Gaussian channel. We believe that the cavity method developed here will play a role in the analysis of a broader class of inference and spin models where the degrees of freedom are large arrays instead of vectors.

Introduction

In the field of high-dimensional statistical inference, the spiked Wigner model is a cornerstone for understanding how signals can be recovered from noisy observations. Traditionally, this model is analyzed under the assumption that the rank $M$ of the signal is a small, fixed constant while the matrix size $N$ tends toward infinity. However, modern data science frequently encounters scenarios where the complexity of the signal (its rank) grows alongside the volume of data.

This research addresses the fundamental information-theoretic limits of symmetric matrix factorization when the rank $M$ is no longer fixed but scales sublinearly with $N$. Specifically, the authors investigate the regime where $M = o(\sqrt{\ln N})$. This shift from a fixed to a growing rank introduces significant technical challenges, as the mathematical order parameters—typically used to describe the system's state—transform from simple scalars into increasingly large and complex matrices.

The Multiscale Cavity Method

The primary methodological breakthrough of this work is the development of a multiscale cavity method. The standard cavity method (or Aizenman–Sims–Starr scheme) is a technique from statistical mechanics used to calculate the "free entropy" of a system by observing the effect of adding a single new data point (a "spin").

To handle a growing rank, the authors generalized this approach to account for two interacting scales:

  1. The Data Scale ($N$): Adding new rows and columns to the observed matrix.
  2. The Rank Scale ($M$): Adding new dimensions to the signal rank.

By tracking how the system's free energy changes across both dimensions simultaneously, the authors established a multiscale identity. They discovered that while adding a new rank dimension is mathematically "heavier" than adding a new data point, these two effects reach a perfect balance in the thermodynamic limit, provided the rank grows slowly enough.

Key Insights: The Rank-One Equivalence

The most significant finding of the paper is the Rank-One Reduction. The authors prove that if the signal entries are independent and identically distributed (i.i.d.), the complex, high-dimensional variational formula that describes the system's limit simplifies into a one-dimensional scalar formula.

Remarkably, this is the exact same formula used to describe the standard $M=1$ (rank-one) spiked Wigner model. This implies that, from an information-theoretic standpoint, a model with a slowly growing rank behaves identically to a simple rank-one model. The phase transition—the specific signal-to-noise ratio (SNR) at which signal recovery becomes possible—remains unchanged despite the increasing rank.

This simplification is driven by the symmetry inherent in i.i.d. signals. This symmetry induces a form of "exchangeability" in the overlap matrix (the measure of reconstruction accuracy), allowing the authors to collapse a matrix-valued problem into a scalar one.

Theoretical Results and Performance Limits

The research establishes several rigorous benchmarks for the sublinear-rank regime:

  • Mutual Information: The limiting mutual information between the hidden signal and the noisy data is governed by a rank-one replica symmetric potential.
  • Minimum Mean-Square Error (MMSE): The authors provide a quantitative limit for the MMSE, defined as $\rho^2 - q^*(\lambda)^2$, where $\rho^2$ represents the signal variance and $q^*$ is the maximizer of a specific scalar potential function.
  • Thermal Concentration: A critical component of the proof is the demonstration that the overlap matrix concentrates around its mean even as the rank grows. The authors successfully tracked the $M$-dependence in convergence rates, proving that error terms vanish in the $o(\sqrt{\ln N})$ regime.

Implications and Future Directions

While this work provides a rigorous foundation for sublinear-rank models, it also highlights new frontiers for research. The current proof is constrained to very slow growth ($M = o(\sqrt{\ln N})$). The authors conjecture that these results may hold for any sublinear rank ($M = o(N)$), but current mathematical tools for proving "concentration of measure" are not yet robust enough to bridge that gap.

Furthermore, the results are expected to diverge in the "extensive rank" regime, where $M = \Theta(N)$. In such cases, the rank-one reduction is likely to fail, giving way to much more complex behaviors. The multiscale cavity method introduced here offers a promising framework for exploring these more complex systems, including asymmetric matrix factorization and tensor factorization in growing-rank environments.

Summary updated

Abstract

We consider a statistical model for symmetric matrix factorization with additive Gaussian noise in the high-dimensional regime where the rank $M$ of the signal matrix to infer scales with its size $N$ as $M={\rm o}(\sqrt{\ln N})$. Allowing for an $N$-dependent rank offers new challenges and requires new methods. Working in the Bayes-optimal setting, we show that whenever the signal has i.i.d.~entries, the limiting mutual information between signal and data is given by a variational formula involving a rank-one replica symmetric potential. In other words, from the information-theoretic perspective, the case of a (slowly) growing rank is the same as when $M=1$ (namely, the standard spiked Wigner model). The proof is primarily based on a novel multiscale cavity method allowing for growing rank along with some information-theoretic identities on worst noise for the vector Gaussian channel. We believe that the cavity method developed here will play a role in the analysis of a broader class of inference and spin models where the degrees of freedom are large arrays instead of vectors.
BibTeX
@misc{barbier2024multiscale,
  author = {Jean Barbier and Justin Ko and Anas A. Rahman},
  title = {{A multiscale cavity method for sublinear-rank symmetric matrix factorization}},
  year = {2024},
  eprint = {2403.07189},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2403.07189},
}

Loading related content...

Figure