PaperlayerView exact revision on arXiv

Source-linked AI summary

Bayesian CP Factorization of Incomplete Tensors with Automatic Rank Determination

Qibin Zhao, Liqing Zhang, Andrzej Cichocki

arXiv:1401.6497v2cs.LGcs.CVstat.ML

TL;DR

Incomplete-tensor CP factorization requires difficult rank selection and typically lacks uncertainty modeling for latent factors and missing entries. The paper introduces a fully Bayesian hierarchical CP model with sparsity-inducing priors and deterministic variational inference. It reports automatic rank recovery, resistance to overfitting, predictive distributions for missing entries, and superior predictive performance in synthetic and real-world applications.

  • Problem

    Existing incomplete-tensor CP methods require a manually specified rank, while CP-rank determination is difficult and uncertainty in latent factors and missing entries is not modeled.

  • Method

    The paper uses a fully Bayesian CP model with sparsity-inducing hierarchical priors, hyperpriors over model parameters, and deterministic variational Bayesian inference.

  • Results

    The method recovers ground-truth CP rank, prevents overfitting with highly incomplete data, predicts missing values, and outperforms state-of-the-art tensor factorization and completion methods.

  • Takeaways & Limitations

    Automatic rank determination and parameter inference from observed data make the approach applicable to incomplete and noisy tensor factorization without manual tuning-parameter selection.

  • Takeaways & Limitations

    The low-rank assumption can oversimplify tensors without intrinsic low-rank structure when many entries are missing, motivating mixture priors that also model local similarity.

Abstract

from arXiv · show

CANDECOMP/PARAFAC (CP) tensor factorization of incomplete data is a powerful technique for tensor completion through explicitly capturing the multilinear latent factors. The existing CP algorithms require the tensor rank to be manually specified, however, the determination of tensor rank remains a challenging problem especially for CP rank. In addition, existing approaches do not take into account uncertainty information of latent factors, as well as missing entries. To address these issues, we formulate CP factorization using a hierarchical probabilistic model and employ a fully Bayesian treatment by incorporating a sparsity-inducing prior over multiple latent factors and the appropriate hyperpriors over all hyperparameters, resulting in automatic rank determination. To learn the model, we develop an efficient deterministic Bayesian inference algorithm, which scales linearly with data size. Our method is characterized as a tuning parameter-free approach, which can effectively infer underlying multilinear factors with a low-rank constraint, while also providing predictive distributions over missing entries. Extensive simulations on synthetic data illustrate the intrinsic capability of our method to recover the ground-truth of CP rank and prevent the overfitting problem, even when a large amount of entries are missing. Moreover, the results from real-world applications, including image inpainting and facial image synthesis, demonstrate that our method outperforms state-of-the-art approaches for both tensor factorization and tensor completion in terms of predictive performance.

1 INTRODUCTION

Incomplete-tensor CP factorization must recover latent multilinear structure while handling difficult rank selection. The paper proposes a fully Bayesian approach that determines rank automatically and improves predictive performance on missing entries.

  • Motivation: Missing entries arise in real-world tensor data, requiring factorization methods to learn multilinear factors from partially observed entries.The inferred factors can then be used to predict missing entries.
  • Prior limitations: Existing completion methods based on nuclear norms target multilinear rank and cannot explicitly capture the underlying CP factors.This motivates a method that combines factor modeling with completion.
  • Motivation: CP rank is difficult to determine because computing or even bounding it for arbitrary tensors is challenging, especially with missing data.The paper notes that computing tensor rank is NP-complete.
  • Contribution: The paper proposes a fully Bayesian CP model that infers multilinear factors and missing-entry predictive distributions while determining the latent tensor rank automatically.A sparsity-inducing hierarchical prior is placed over multiple factor matrices.
  • Contribution: Variational Bayesian inference yields a deterministic, tuning-parameter-free procedure that avoids parameter selection and is reported to outperform state-of-the-art methods predictively.Experiments cover synthetic data and real-world image completion, restoration, and synthesis.

2 PRELIMINARIES AND NOTATIONS

This section establishes notation for tensors and the multilinear products used in tensor factorization. It defines inner products, norms, Hadamard products, Kronecker products, and Khatri–Rao products.

  • Tensor notation: Tensor order denotes the number of dimensions, while vectors, matrices, and higher-order tensors use distinct notation.An Nth-order tensor has dimensions I1 × I2 × ··· × IN and entries indexed by i1, i2, . . . , iN.
  • Tensor operations: The inner product sums element-wise products, and the squared Frobenius norm is defined as the inner product of a tensor with itself.These definitions provide basic measures for tensor calculations.
  • Tensor operations: The Hadamard product is an entrywise product between objects of equal size.For matrices, the result retains the same dimensions as both inputs.
  • Matrix products: The Kronecker product of matrices A ∈ R^I×J and B ∈ R^K×L has size IK × JL.The notation is A ⊗ B.
  • Matrix products: The Khatri–Rao product is a columnwise Kronecker product, producing a matrix of size IJ × K from matrices with K columns.The section also introduces reverse-order and mode-excluded Khatri–Rao products.

3.1 Probabilistic Model and Priors

The model represents an incomplete noisy tensor through CP factorization with Gaussian observation noise and hierarchical priors over latent factors and hyperparameters. Shared sparsity controls suppress unnecessary components, enabling automatic CP-rank determination while supporting posterior prediction of missing entries.

  • Probabilistic model: An incomplete tensor is modeled through observed-index set Ω and indicator tensor O, with observations given by a noisy latent tensor.The noise is assumed to be independently Gaussian.
  • CP representation: CP factorization expresses the latent tensor as a sum of R rank-one tensors formed from mode-specific factor matrices.The smallest number of rank-one terms defines the CP rank.
  • Probabilistic model: The likelihood models each observed tensor element through multilinear interactions among R-dimensional latent vectors from the different modes.These interactions distinguish tensor factorization from matrix factorization but complicate learning.
  • Hierarchical priors: The effective latent dimensionality is selected automatically by placing sparsity-inducing hyperpriors on component-specific variance controls.Each hyperparameter controls one component across the factor matrices through shared precision parameters.
  • Automatic rank determination: Shared priors across all mode matrices learn a common sparsity pattern, yielding the minimum number of rank-one terms needed by the model.The initial latent dimension R can therefore be set to a maximum value while effective rank is inferred.
  • Bayesian inference: A fully Bayesian treatment places priors over model parameters and noise precision, then targets the full posterior rather than only a point estimate.The posterior also supports predictive distributions for missing entries.

3.2 Model Learning via Bayesian Inference

The model learns a probabilistic CP factorization by approximating the intractable posterior with a factorized variational distribution. Conjugacy yields closed-form posterior updates for factor matrices and hyperparameters using observed entries and multilinear computations.

  • Variational Bayesian inference approximates the true posterior by minimizing KL divergence under a factorized distribution over model variables.The optimized factors are derived by maximizing the variational lower bound.
  • Conjugate exponential-family distributions enable closed-form posterior update rules for each parameter and hyperparameter.Each update uses expectations with respect to all variational factors except the variable being updated.
  • Factor-matrix posteriors combine observed-data messages, other-mode factors, noise precision, and shared prior information.Multilinear operations and observed-index subtensors make these updates computationally tractable for incomplete tensors.
  • The shared hyperparameter λ is learned from all factor matrices, with smaller component norms producing stronger shrinkage toward zero.This update mechanism enforces a common sparsity pattern across modes and supports automatic rank determination.
  • The noise-precision posterior is updated from observed-data error and factor uncertainty, with missing-entry expectations evaluated through multilinear identities.Theorem-based computations reduce expectations of squared inner products and Khatri-Rao products to matrix operations.

3.3 Predictive Distribution

The method estimates predictive distributions for missing tensor entries from the variational posterior conditioned on observed entries. The resulting predictive distribution is a Student’s t-distribution with an associated predictive variance.

  • Predictive distributions for missing entries are inferred from the variational posterior conditioned on observed entries.
  • The conditional distribution of a missing entry is approximated by a Student’s t-distribution with estimated location, scale, and degrees-of-freedom parameters.
  • Predictive variance is obtained directly from the Student’s t-distribution parameters.

3.4 Computational Complexity

The inference algorithm has linear complexity in the number of observations and polynomial complexity in the model rank. Automatic pruning further reduces the effective rank during early iterations.

  • R ≪M in typical settings, so the latent-component dimension is much smaller than the input data size.
  • O(NR2M + R3) is the overall complexity, scaling linearly with data size and polynomially with model complexity.N is tensor order, R is the number of latent components, and M is the number of observations.
  • Excess latent components are pruned during the first few iterations, causing the effective R to decrease rapidly in practice.

3.5 Discussion of Advantages

The method combines automatic rank determination, parameter-free Bayesian learning, uncertainty estimation, and deterministic inference. These properties support low-rank approximation and probabilistic prediction for noisy, incomplete tensors.

  • Automatic CP-rank determination enables low-rank tensor approximation from highly noisy and incomplete tensors.
  • The tuning-parameter-free formulation infers model parameters from observed data instead of requiring a predefined rank or several nuclear-norm tuning parameters.
  • Posterior uncertainty is inferred for both latent factors and predictions of missing entries, unlike methods providing only point estimates.
  • Deterministic Bayesian inference provides efficient model learning and empirically fast convergence.

4 MIXTURE FACTOR PRIORS

The model augments the low-rank assumption with local similarity through a Gaussian mixture prior over factor-matrix rows, using adjacent-row correlations to define mixture weights.

  • The variant Bayesian CP model incorporates local similarity in addition to the low-rank assumption.This addresses cases where data lacks intrinsic low-rank structure and many entries are missing.
  • A Gaussian mixture prior is specified over the factor matrices.The prior rewrites each factor-matrix row distribution as a mixture distribution.
  • Adjacent factor-matrix rows are assumed to be highly correlated, so mixture coefficients decrease with squared row distance.The coefficients are defined using wi,j = zi exp(−|i − j|^2), with normalization zi.
  • Posterior factor means are updated by applying the mixture-weight matrix W, while posterior covariances remain unchanged.The remaining variable-inference procedures require no changes under this variant.

5 EXPERIMENTAL RESULTS

Experiments evaluate FBCP on synthetic tensors, incomplete noisy data, image inpainting, and facial image synthesis. Across these settings, the method determines rank automatically and achieves strong predictive or recovery performance, including under substantial missingness.

  • Experimental setup: FBCP was compared with seven state-of-the-art tensor factorization and completion methods across synthetic and real-world experiments.The comparisons included CPWOPT, CPNLS, HaLRTC, FaLRTC, FCSA, HardC., geomCG, and STDC.
  • Synthetic experiments: 100% rank-detection accuracy was achieved for complete tensors at SNR≥10 dB and for incomplete tensors with missing ratio 0.7 under nearly noiseless conditions.At SNR=0 dB with missing ratio 0.5, accuracy was 90%; with 50×50×50 tensors, 90% accuracy persisted at SNR=0 dB and missing ratio 0.9.
  • Synthetic experiments: Rank detection depends mainly on observed entries and true rank: larger ranks require more observations, while excessive observations may not help under high noise.For true rank R = 15, recovery succeeded on complete tensors but failed when the missing ratio exceeded 0.5.
  • Predictive performance: FBCP significantly outperformed other algorithms in predictive performance across missing ratios, while factorization methods were stronger than completion methods only at relatively low missingness.At high missingness, factorization methods such as CPWOPT and CPNLS performed worse than completion methods, whereas FBCP remained strongest in the reported comparison.
  • Real-world applications: In image and facial-image applications, FBCP or FBCP-MP produced strong recovery and visual results under high missingness, with FBCP-MP achieving the best recovery on eight images.FBCP also showed significantly superior facial-image synthesis and could outperform completion methods on missing images.

6 CONCLUSION

The paper presents a fully Bayesian CP factorization for incomplete and noisy tensors that automatically determines CP rank and avoids tuning-parameter selection. Experiments show effective rank discovery and missing-value imputation, with real-world applications outperforming state-of-the-art techniques.

  • The proposed fully Bayesian CP factorization handles incomplete and noisy tensor data while automatically determining CP rank.Hierarchical priors over unknown parameters enable deterministic Bayesian inference and automatic rank determination.
  • The tuning parameter-free formulation avoids parameter selection and can prevent overfitting.
  • A mixture-prior variant shows advantages on natural images with a large amount of missing pixels.
  • Empirical results validate ground-truth tensor-rank discovery and missing-value imputation for extremely sparse tensors.
  • Image completion and image synthesis applications demonstrate superiority over state-of-the-art techniques.
Loading 1401.6497v2…