Graphical model for factorization and completion of relatively high rank tensors by sparse sampling

AI summary

Overview

Research area: Statistical machine learning and statistical mechanics of disordered systems, applied to matrix/tensor factorization and tensor completion (arXiv:2510.17886v3 [stat.ML], CC BY 4.0).

Technical level: Advanced. The paper relies on the replica method, cumulant expansions, belief propagation, generalized approximate message passing (G-AMP), and state evolution — standard machinery in statistical-mechanical informatics but demanding outside it.

Scope (one sentence): The paper analyzes Bayes-optimal factorizations of relatively high rank tensors (rank M with N ≫ M ≫ 1) from only O(NM) of the N^p tensor elements, derives message-passing algorithms and replica-theoretic predictions in a "dense limit," and checks them against each other and against finite-size simulations.

Authors and affiliations: Angelo Giorgio Cavaliere (D3 Center, Osaka University); Riki Nagasawa (Department of Physics, Graduate School of Science, Osaka University); Shuta Yokoi (Department of Physics, Graduate School of Science, Osaka University); Tomoyuki Obuchi (Department of Systems Science, Graduate School of Informatics, Kyoto University; RIKEN center for AIP); Hajime Yoshino (D3 Center, Osaka University; Department of Physics, Graduate School of Science, Osaka University; RIKEN center for AIP).

What This Paper Is About

The authors study how to recover a set of N vectors x_i in R^M from observations of only a vanishing fraction of the entries of a p-th order tensor built from those vectors. Each observed p-plet follows the model π_{i1,...,ip} = (λ/√M) Σ_{μ=1}^{M} F_{i1,...,ip,μ} x_{i1 μ} x_{i2 μ} ⋯ x_{ip μ}, with p = 2, 3, ...

The measurements are sparse in a specific sense: the underlying interaction graph is random, and each vector x_i is observed c = αM times with α = O(1). The total number of measured entries is O(NM), compared with the N^p = O(N^p) total tensor elements of binom(N,p).

The goal is to determine the theoretically optimal estimation performance in the "dense limit" (N, M → ∞ with N ≫ M ≫ 1), where the rank M is not O(1), and to provide an algorithm that achieves this performance.

Key Contributions

1. Exact asymptotics for a high-rank, sparsely measured setting. The paper analyzes tensor/matrix factorization and completion where the rank is not O(1) and measurements are a vanishing fraction of the tensor, obtaining precise asymptotics via the "dense limit" N ≫ M ≫ 1 with O(NM) measurements. The authors state this is, to the best of their knowledge, the first such precise result for this combination of high rank and significantly sparse measurements.

2. A replica theory built on a cumulant expansion. Rather than blindly applying a Gaussian ansatz, the authors develop a replica calculation with a systematic cumulant expansion that studies interactions between microscopic variables. They report that the Gaussian ansatz fails in some fully connected systems, including the p = 2 matrix factorization problem in the full-rank M = N case.

3. Message-passing algorithms and state evolution. The authors build algorithms based on generalized approximate message passing (G-AMP) and derive associated state evolution (SE) equations, checking consistency with the replica result.

4. Characterization of the deterministic versus random coefficient model. For the linear coefficient F_{■,μ}, the paper shows that the deterministic choice F = 1 (corresponding to CP / Canonical Polyadic decomposition) and the i.i.d. random choice with zero mean and unit variance yield identical macroscopic results in the dense limit — while the random choice significantly improves convergence of the message-passing algorithms, particularly for p = 2.

Main Findings

• Sparse sampling from a random graph suffices. Each vector x_i is observed c = αM times with α = O(1), and the edge set size is N_■ = |E| = Nc/p = (α/p)NM, which is much smaller than the total number of p-plets binom(N,p) = O(N^p). Once the vectors x_i (i = 1, 2, ..., N) are estimated, the whole tensor with O(N^p) elements — including unobserved entries — can be inferred.

• The dense limit is what makes the analysis tractable. The limit N, M → ∞ with N ≫ M ≫ 1 allows intricate correlations between variables to be ignored. The authors note N must grow faster than any power of c. The graphs are not sparse in the usual sense (which would mean c = O(1)) and are much sparser than globally coupled graphs with c = O(N^p); the paper calls them "dense graphs."

• Order parameters and error formulas. Two order parameters control the behavior: the overlap m = E_y[(1/NM) Σ_{i∈V} Σ_{μ=1}^{M} x_{*,iμ} ⟨x_{iμ}⟩], which measures teacher–student similarity (called "magnetization"), and q = E_y[(1/NM) Σ_{i∈V} Σ_{μ=1}^{M} ⟨x_{iμ}⟩²], analogous to an Edwards-Anderson order parameter. The input MSE is 1 − 2m + q and the output MSE is λ²(1 − 2m^p + q^p).

• Bayes-optimal identity m = q. In the Bayes-optimal setting the authors note m = q holds, analogous to behavior along the Nishimori line in spin-glass systems. The phase with m = 0 is called paramagnetic (inference impossible); m > 0 is called ferromagnetic or magnetized.

• Deterministic and random F give identical macroscopic results. The two conditions on the linear coefficient yield the same macroscopic behavior in the dense limit, though the random variant improves algorithm convergence at finite N and M, especially for p = 2.

• Consistency between theory and numerics. Numerical experiments on finite-size systems using G-AMP are consistent with the state evolution and replica predictions, which the authors take as evidence that their findings are exact in the limit considered.

• Symmetries. The statistical weight is invariant under reflection x_{iμ} → −x_{iμ} for even p (with the even priors used); under permutations of the component index μ when F_{■,μ} = 1; and under global rotations for p = 2 with Gaussian prior and F_{■,μ} = 1. The permutation and rotation symmetries are suppressed in the random model, while reflection survives for even p.

• Connection to error-correcting codes. The transmission rate is R = NM/N_■ = Mp/c. In the Sourlas code (M = 1, global coupling c ∝ N^{p−1}) this rate vanishes in the thermodynamic limit; in the Kabashima-Saad code (M = 1, sparse coupling c = O(1)) it can remain finite by taking c → ∞ after N → ∞ with p/c fixed. The present model attains Shannon's bound with finite transmission rate R = p/α by taking p → ∞ with p/α fixed.

• Contrast with earlier high-rank work. The authors note their problems do not become equivalent to a bunch of rank-one M = 1 cases, in contrast to the sub-linearly high-rank case M = O(N^α) with 0 < α < 1 under full O(N²) measurements treated in prior work.

• Specific numerical values and phase transition locations. The excerpt provided does not report the specific quantitative results, critical parameter values, or phase transition thresholds obtained in Section 5; these are described as forthcoming in the paper's Section 5.

Methodology in Plain English

The authors set up a teacher–student inference problem: a "teacher" generates the true vectors x_{*,i} from a prior distribution and produces the observed tensor entries through a known likelihood; a "student" tries to recover the vectors while knowing the likelihood, the linear coefficients F, and the prior. The likelihood can be additive noise (y = π + w, with Gaussian noise N(w|0,1) considered) or a sign output (y = sgn(π)). Priors considered are Ising (half weight at x = −1 and x = +1) and Gaussian (standard normal).

Two main tools are used. First, the replica method from statistical mechanics, which computes the expected free energy by introducing n replicas, treating n as a positive integer, then analytically continuing to n → 0. The key technical ingredient is a cumulant expansion that handles interactions between microscopic variables, avoiding a Gaussian ansatz that the authors find fails in some fully connected systems. Second, belief propagation on the factor graph of variables and p-plet interactions, from which the authors build generalized approximate message passing (G-AMP) algorithms and derive state evolution equations that track the macroscopic behavior of the algorithm over iterations.

Because many quantities are random (posterior averages depend on random observations y_■), the paper distinguishes the thermal average over the posterior, written ⟨⋯⟩, from the quenched average over observations, written E_y(⋯). The random graph structure itself is noted to have no direct consequence for macroscopic observables in the N, M → ∞ limit; in finite-size numerics the authors do average over realizations of the edge set E.

Why This Matters

Impact on research. The paper offers a precise asymptotic theory for tensor/matrix factorization when rank is high (not O(1)) and observations are a vanishing fraction of tensor entries — a regime the authors note has been difficult to analyze, with earlier high-rank analyses later recognized as imprecise and addressed only by approximate expansions such as the Plefka–Georges–Yedidia approach. It also shows that the standard Gaussian ansatz can fail in some fully connected systems, motivating the cumulant expansion. The dense-limit technique used here was recently employed in analyzing deep neural networks, suggesting broader applicability.

Real-world applications (as cited in the paper):

• Recommendation systems used heavily in social network services, where a substantial amount of data is missing and estimated tensor rank can range from roughly 50 to 1000 while N is larger by orders of magnitude.
• Facial image analysis, where estimated tensor rank can be as large as order 10^2 while N is larger still.
• Tensor/matrix completion generally — reconstructing the full O(N^p) tensor from O(NM) measured entries.
• Signal processing and machine learning applications of tensor factorization, and adjacent areas such as dictionary learning, low-rank matrix completion, blind calibration, and robust PCA that the related-work section cites.

Industry relevance. The setting directly targets the data-missingness regime of recommender systems and large-scale factorization tasks: recovering structure from a vanishing fraction of entries, with a theoretically optimal benchmark (minimum mean square error under the Bayes-optimal assumption) against which practical algorithms can be compared.

Future Directions

• Extending the analysis beyond the dense limit. The paper explicitly requires N ≫ M ≫ 1 with N growing faster than any power of c; whether comparable exactness can be obtained outside this regime is left open.

• Applying the cumulant-expansion replica technique elsewhere. Since the Gaussian ansatz fails in some fully connected systems — including the p = 2, M = N full-rank matrix factorization case — the systematic treatment introduced here could be tested in other inference problems where the ansatz breaks down.

• Broadening beyond the specific priors and output channels studied. The formalism allows generic priors and output distributions, but the quantitative analysis in the paper focuses on Ising and Gaussian priors and on additive Gaussian noise and sign output.

• Exploring the connection to coding more fully. The paper shows its model attains Shannon's bound with finite transmission rate R = p/α by taking p → ∞ with p/α fixed, paralleling the Sourlas and Kabashima-Saad codes; the implications of this for code construction are not fully explored in the excerpt.

• Practical algorithmic questions. The random spreading factor improves G-AMP convergence, particularly for p = 2, and thus the agreement between finite-size algorithm behavior and the macroscopic SE/replica predictions; how far this convergence advantage extends at larger N and M is a natural follow-up.

Target Audience

This paper is aimed at researchers comfortable with advanced statistical mechanics and inference theory: physicists working on disordered systems and spin glasses, machine learning researchers studying message passing, approximate message passing, and state evolution, and theoretically inclined researchers in matrix/tensor factorization, tensor completion, dictionary learning, and recommendation systems who wish to understand optimal-performance limits for high-rank problems under sparse sampling. Readers seeking an applied tutorial or a plug-and-play algorithm description would find the material substantially more difficult than its practical framing in recommender systems and image analysis might suggest.

Authors’ abstract

We consider tensor factorizations based on sparse measurements of the components of relatively high rank tensors. The measurements are designed in a way that the underlying graph of interactions is a random graph. The setup will be useful in cases where a substantial amount of data is missing, as in completion of relatively high rank matrices for recommendation systems heavily used in social network services. In order to obtain theoretical insights on the setup, we consider statistical inference of the tensor factorization in a high dimensional limit, which we call as dense limit, where the graphs are large and dense but not fully connected. We build message-passing algorithms and test them in a Bayes optimal teacher-student setting in some specific cases. We also develop a replica theory to examine the performance of statistical inference in the dense limit based on a cumulant expansion. The latter approach allows one to avoid blind usage of Gaussian ansatz which fails in some fully connected systems.