On the Identifiability of Tensor Ranks via Prior Predictive Matching

AI summary

Overview

Research area: Machine learning — probabilistic tensor factorization, specifically the theory of rank selection in tensor decomposition models.

Technical level: Advanced. The paper assumes familiarity with tensor decompositions (Tucker, PARAFAC/CP, Tensor Train, Tensor Ring), probabilistic generative models, and linear-algebraic identifiability arguments.

Scope: The paper develops a prior-predictive moment-matching framework that converts moment equations of probabilistic tensor models into a log-linear system, uses it to decide whether tensor ranks are identifiable, and derives closed-form rank estimators for the identifiable models.

What This Paper Is About

Choosing the number of latent dimensions (ranks) in a tensor factorization is normally done by heuristic or expensive search, and for arbitrary tensors the problem is NP-Complete over ℚ (Håstad, 1990), NP-Hard over ℝ (Hillar and Lim, 2013), and hard to approximate in general (Swernofsky, 2018). The authors ask a prior question: when can a moment-matching approach identify the ranks at all, given a particular tensor decomposition structure? They answer it by showing that the topology of interactions between latent factors determines whether the resulting system of moment equations can be solved for the ranks.

Key Contributions

1. A general, prior-predictive framework for analyzing rank identifiability in probabilistic tensor models, based on the rank of a log-linear system of moment equations derived from pure interaction terms (Proposition 2.5).
2. Application of the framework to four foundational decompositions: Tucker (Tucker, 1966), PARAFAC/CP (Hitchcock, 1927; Harshman and others, 1970; Carroll and Chang, 1970), Tensor Train (Oseledets, 2011), and Tensor Ring (Zhao et al., 2016).
3. A proof that standard Tucker ranks are not identifiable by this method, because its symmetric "hub-and-spoke" interaction topology (Carlsson and Jia, 2013) makes the reduced design matrix a 0 × M zero matrix (Theorem 3.4).
4. Proofs that PARAFAC/CP, TT, and TR ranks are identifiable from first and second moments, with explicit closed-form estimators, plus a complete bootstrap-based estimation pipeline.

Main Findings

• Polynomial moment structure: For any model matching Definition 2.1, every pure interaction term v_S is a monomial in the unknown hyperparameters (r_p, μ_p, σ_p²), so the mean, variance, and covariance of the rate tensor are polynomials of these quantities (Proposition 2.3). Taking logarithms turns the moment equations into a linear system Ax = b (Definition 2.4).

• Identifiability criterion: Ranks are identifiable from second moments if and only if the prior-moment parameters can be algebraically eliminated, leaving a full-rank reduced system A_red x_r = b_red in the log-ranks alone (Proposition 2.5).

• Tucker is a cautionary case: The identity log v_p − 2 log E[Y] = log v_{G,p} − log v_G holds for every mode p = 1, ..., M (Lemma 3.3), making the M log-rank columns redundant, so the reduced design matrix is the 0 × M zero matrix and the Tucker ranks are not identifiable (Theorem 3.4).

• PARAFAC/CP rank is identifiable: For any two distinct modes p ≠ q, r = v_{ {p,q} } · (E[Y])² / (v_{ {p} } · v_{ {q} }) (Theorem 4.3); all nuisance parameters cancel.

• Tensor Train interior ranks are identifiable: The chain structure creates asymmetric constraints. Using the identities v_{ {p,p+1} }/v_{ {p+1} } = σ_p²/μ_p² and v_{ {p-1,p,p+2} }/v_{ {p-1,p+2} } = (1/r_p)(σ_p²/μ_p²), for 1 < p < M − 1 the estimate is r_p = (v_{ {p,p+1} } · v_{ {p-1,p+2} }) / (v_{ {p+1} } · v_{ {p-1,p,p+2} }) (Theorem 4.6).

• Tensor Ring: TR, formed by connecting the ends of the TT into a closed loop with no limitation on the outer rank dimension, is also proven identifiable; its rank estimation formulas are given in Appendix A.4 (Remark 4.7).

• Simulation accuracy (PARAFAC/CP): Data were generated with Gamma-distributed factor entries and Poisson observations, over tensor orders M ∈ {3,4}, dimensions (100,100,100) or (50,50,50,50), and true ranks r_p ∈ {5, ..., 65}. The mean of median bootstrap estimates closely tracks the y = x line; best performance (closer mean, reduced uncertainty) occurs at ranks below 25, with a slight positive bias and increased variance as the true rank grows. The paper's figure discussion states the estimator follows the linear trend for true ranks ranging from low values up to 90.

• Comparison with AIC/BIC: A variational CP model with AIC/BIC scoring consistently collapsed to the lowest available rank (often R = 2) across simulated CP datasets under Gamma, Uniform, and Gaussian priors, whereas the prior-predictive estimator recovered the scale of the ground-truth rank in non-zero mean scenarios. The paper notes that if all factors have zero-mean priors, all pure interaction terms vanish and ranks are not identifiable from second-order moments.

• Real-data result (PINCAT MRI): Comparing against explicit Bayesian inference from Zhang et al. (2022) with a 10% hold-out, the prior-predictive estimator selected rank 70, BFCP selected 17, and HMC selected 65. Test RMSE and test SD were essentially identical: 0.6086 / 0.4876 (prior predictive), 0.6087 / 0.4877 (BFCP), 0.6086 / 0.4876 (HMC).

• Robustness to missing data: The paper states this is a crucial aspect of real-world tensor analysis, but the provided content is truncated mid-sentence, so the missing-data results are not reported here.

Methodology in Plain English

The authors treat a tensor model as a probabilistic generator: latent factors are drawn independently from location-scale priors, a rate tensor is built by summing products of those factors, and observed tensor entries are drawn conditionally on the rate (for example Poisson with variance equal to the mean, or Gaussian with variance σ_Y²).

They then focus on "pure interaction terms" — the portion of variance attributable to a specific set of shared indices between two tensor entries — and show that each one is a monomial, a product of ranks and prior moments. Because the equations are multiplicative, taking logarithms makes them additive, producing a linear system whose design matrix records the exponents. Whether parameters can be isolated is then a question of linear algebra: if the rank-related columns can be eliminated by the other unknowns, ranks are not identifiable; if a full-rank reduced system in log-ranks remains, they are.

For the identifiable models, dividing pairs of monomials cancels the unknown prior moments and leaves a formula consisting only of quantities estimable from data. Practical estimation then proceeds in three stages: compute the global mean, sample many pairs of entries matching on each shared-index pattern to get covariances, and apply inclusion-exclusion to obtain pure interaction terms; repeat this over block-bootstrap resamples of tensor slices; and summarize the resulting ratios using a regularized denominator (adding 1.96 times the bootstrap standard error of the denominator) with the median as the point estimate and a percentile interval for uncertainty.

Why This Matters

Impact on research: The work shifts rank selection from heuristic search to a structural question about a model's factorization topology. It gives a theoretical explanation for why some decompositions admit closed-form rank recovery and others provably do not, and it links tensor rank identifiability to the same prior-predictive matching logic already used for matrix factorization (da Silva et al., 2023; Wang and Stephens, 2021).

Real-world applications (domains the paper cites as users of tensor factorizations):

• Neuroscience, for multi-way neural data analysis (Cong et al., 2015; Mosayebi and Hossein-Zadeh, 2020).
• Bioinformatics and genomics (Alter et al., 2003) and chemometrics (Bro and Kiers, 2003).
• Network science (Contisciani et al., 2022) and computational social science (Schein et al., 2015).
• Recommender systems (Bhargava et al., 2015; Gopalan et al., 2015), supervised learning (Stoudenmire and Schwab, 2016), and compression of large neural networks (Novikov et al., 2015).

Industry relevance: The estimators are closed-form and depend only on observed moments, so they avoid the cost of repeated model refits or full Bayesian inference. On the PINCAT MRI dataset, the inexpensive estimator matched the predictive accuracy and uncertainty calibration of far more expensive Bayesian procedures (BFCP and HMC), which is a practical argument for adopting it in production settings where domain knowledge for setting ranks is scarce.

Future Directions

• Handling the non-identifiable case: Since Tucker ranks cannot be recovered from second moments, an open question is whether higher-order moments, alternative moment constructions, or additional constraints could identify them.
• Relaxing the prior assumptions: The framework assumes i.i.d. location-scale priors, and the paper notes that zero-mean priors erase all pure interaction terms and destroy second-order identifiability, so behavior under other prior structures is unresolved.
• Robustness under missing data and noise: The paper frames missing data as crucial for real-world use, but the reported pipeline assumes complete tensor entries for moment estimation; extending and validating it under missingness remains open.
• Wider model coverage: The framework was applied to four decompositions; whether other structured tensor models (or constrained variants) yield solvable or degenerate reduced systems is untested.

Target Audience

Researchers and practitioners in probabilistic machine learning and tensor methods who need principled rank selection: statisticians working on identifiability, method developers implementing tensor factorization models such as PARAFAC/CP, TT, or TR, and applied scientists in the application domains cited above who must choose latent dimensions without strong prior knowledge. Readers should be comfortable with tensor algebra, generating-process notation, and linear-system arguments.

Authors’ abstract

Selecting the latent dimensions (ranks) in tensor factorization is a central challenge that often relies on heuristic methods. This paper introduces a rigorous approach to determine rank identifiability in probabilistic tensor models, based on prior predictive moment matching. We transform a set of moment matching conditions into a log-linear system of equations in terms of marginal moments, prior hyperparameters, and ranks; establishing an equivalence between rank identifiability and the solvability of such system. We apply this framework to four foundational tensor-models, demonstrating that the linear structure of the PARAFAC/CP model, the chain structure of the Tensor Train model, and the closed-loop structure of the Tensor Ring model yield solvable systems, making their ranks identifiable. In contrast, we prove that the symmetric topology of the Tucker model leads to an underdetermined system, rendering the ranks unidentifiable by this method. For the identifiable models, we derive explicit closed-form rank estimators based on the moments of observed data only. We empirically validate these estimators and evaluate the robustness of the proposal.