Source-linked AI summary
All-at-once Optimization for Coupled Matrix and Tensor Factorizations
Evrim Acar, Tamara G. Kolda, Daniel M. Dunlavy
TL;DR
The paper studies how to extract shared latent structure from heterogeneous and incomplete matrices and higher-order tensors. It formulates the task as coupled matrix and tensor factorization, introduces the all-at-once CMTF-OPT method, and extends it to incomplete data. Numerical experiments report greater accuracy and robustness to overfactoring than alternating least squares.
Problem
Heterogeneous data from multiple sources comprise matrices and higher-order tensors, and missing entries complicate joint latent-structure analysis.
Method
CMTF-OPT uses first-order all-at-once optimization to solve coupled matrix and tensor factorizations simultaneously, with an extension for incomplete data.
Results
CMTF-OPT is more accurate than alternating least squares and more robust to overfactoring in the reported numerical experiments.
Takeaways & Limitations
Coupled analysis can improve clustering and missing-data recovery by combining complementary data sources that share latent structure.
Takeaways & Limitations
The paper does not address how to weight objective-function terms for different data sets and leaves other loss functions and nonnegativity constraints for future work.
Abstract
from arXiv · showhide
Joint analysis of data from multiple sources has the potential to improve our understanding of the underlying structures in complex data sets. For instance, in restaurant recommendation systems, recommendations can be based on rating histories of customers. In addition to rating histories, customers' social networks (e.g., Facebook friendships) and restaurant categories information (e.g., Thai or Italian) can also be used to make better recommendations. The task of fusing data, however, is challenging since data sets can be incomplete and heterogeneous, i.e., data consist of both matrices, e.g., the person by person social network matrix or the restaurant by category matrix, and higher-order tensors, e.g., the "ratings" tensor of the form restaurant by meal by person. In this paper, we are particularly interested in fusing data sets with the goal of capturing their underlying latent structures. We formulate this problem as a coupled matrix and tensor factorization (CMTF) problem where heterogeneous data sets are modeled by fitting outer-product models to higher-order tensors and matrices in a coupled manner. Unlike traditional approaches solving this problem using alternating algorithms, we propose an all-at-once optimization approach called CMTF-OPT (CMTF-OPTimization), which is a gradient-based optimization approach for joint analysis of matrices and higher-order tensors. We also extend the algorithm to handle coupled incomplete data sets. Using numerical experiments, we demonstrate that the proposed all-at-once approach is more accurate than the alternating least squares approach.
1. INTRODUCTION
CMTF addresses the challenge of jointly analyzing heterogeneous, incomplete matrices and higher-order tensors to extract shared latent structure. The paper introduces all-at-once optimization and extends it to missing data, motivated by improved clustering and recovery across coupled data sources.
- Motivation: CMTF jointly models matrices and higher-order tensors to extract common latent structure from heterogeneous data sources.Examples include customer ratings, restaurant categories, and social networks.
- Motivation: Joint factorization can reveal fine-grained customer clusters that separate groups individual matrix or tensor analyses cannot fully distinguish.The motivating example combines complementary information from customer purchases and residential neighborhoods.
- Missing Data Recovery: CMTF can support missing-data recovery when coupled data sets share a low-rank structure, even when analyzing one data set alone is insufficient.The approach extracts a common factor matrix and uses the coupled factors to recover missing tensor entries.
- Contributions: CMTF-OPT solves for all factor matrices simultaneously using first-order optimization for a specified number of components.It is presented as an alternative to alternating schemes that determine each entity type's basis one at a time.
- Contributions: CMTF-OPT is extended to incomplete data sets and is reported as more accurate than an alternating least squares approach in numerical experiments.The introduction also notes that ALS-based imputation may suffer from poor convergence and limited scalability with missing data.
2. NOTATION AND BACKGROUND
The paper establishes notation for tensors, matrices, vectors, norms, tensor constructions, and common matrix operations used in coupled factorization.
- Tensors, matrices, vectors, scalars, columns, and tensor entries follow distinct notation conventions.
- The number of CMTF components R remains challenging to determine because computing tensor rank is NP-hard.
- Vectorization stacks matrix columns into a vector, while the Khatri–Rao product forms columnwise Kronecker products.The Khatri–Rao product of A and B has size (IJ) × K.
- Matricization rearranges an N-way tensor into a matrix whose columns are mode-n fibers.
- The norm denotes the Frobenius norm for matrices and the two-norm for vectors, extending the tensor norm definition.
- The bracket notation J A(1), A(2), . . . , A(N) K constructs a tensor from factor matrices through outer products.For two matrices, the construction reduces to J A, B K = AB^T.
3. RELATED WORK IN DATA FUSION
Prior data-fusion methods analyze multiple matrices or tensors, but heterogeneous matrix–tensor coupling requires an extended formulation and motivates the proposed optimization approach.
- Data fusion studies jointly analyze multiple sources represented as matrices, tensors, or heterogeneous combinations of both.Applications include rating prediction and analysis of multiple relations among entities.
- Collective Matrix Factorization simultaneously factorizes coupled matrices using shared factors and alternating algorithms.The formulation uses factor matrices U, V, and W with R factors.
- Earlier work also includes canonical correlation, simultaneous Gramian factorization, and principal-component methods for multiple matrices.
- Neither collective matrix factorization nor tensor factorization alone handles coupled heterogeneous data consisting of matrices and higher-order tensors.
- CMTF extends coupled factorization to a tensor and matrix sharing one mode, with the tensor represented by CP factors.The formulation is related to multi-way multi-block data analysis.
- CMTF-OPT solves for all factor matrices simultaneously with gradient-based optimization, targeting overfactoring and missing-data issues associated with ALS.The paper contrasts this all-at-once approach with the CMTF-ALS algorithm.
4. CMTF-OPT ALGORITHM
CMTF-OPT formulates coupled matrix–tensor factorization as a differentiable least-squares optimization problem and extends it to incomplete tensor data using weighted fitting.
- The algorithm jointly analyzes an Nth-order tensor and a matrix that share one mode, using R-component CP and matrix factorizations.
- CMTF-OPT minimizes a squared-error objective over all tensor factor matrices A(i) and matrix factor V.
- Any gradient-based optimizer can solve the resulting problem; the experiments use nonlinear conjugate gradient with Hestenes–Stiefel updates and Moré–Thuente line search.
- The objective separates tensor-fitting and matrix-fitting terms, whose partial derivatives are combined into a full gradient.The gradient is formed by vectorizing and concatenating derivatives for every factor matrix.
- For missing tensor entries, a binary indicator W weights the objective so only known entries contribute to tensor fitting.The matrix-fitting term remains unchanged, while the tensor term becomes a weighted least-squares problem.
- The incomplete-data gradient combines the weighted tensor derivative with the unchanged matrix derivative.
5. EXPERIMENTS
The experiments compare CMTF-OPT with CMTF-ALS on synthetic coupled matrices and tensors under correct-factor and overfactored settings. CMTF-OPT is especially robust to overfactoring, while noise and unequal component norms make factor recovery harder.
- Experimental setup: The experiments compare CMTF-OPT and CMTF-ALS when extracting the true number of factors and when overfactoring with R̄ = R + 1.Three synthetic coupling scenarios are evaluated: a tensor and matrix, two coupled tensors, and a tensor with two coupled matrices.
- Evaluation: Accuracy is measured by factor match score, which equals 1 for perfect factor recovery and treats values above (0.99)^N as successful.The score uses normalized factor columns and component weights combining tensor and matrix contributions.
- Results: When the correct number of factors is extracted, both algorithms have compatible success ratios and statistically indistinguishable average factor match scores across 30 runs.This result applies to the unit-norm component experiments.
- Results: CMTF-OPT significantly outperforms CMTF-ALS under overfactoring, where CMTF-OPT remains accurate but CMTF-ALS has substantially lower accuracy.The algorithms use relative function-value change as a stopping condition, with additional iteration and gradient settings specified for CMTF-OPT.
- Results: With randomly assigned component norms, CMTF-OPT remains more robust to overfactoring, but increasing noise lowers accuracy even when the true factor count is extracted.In one scenario at noise level 0.35, CMTF-OPT reaches 60% accuracy under the original criterion; a relaxed criterion raises average accuracy to around 73%.
6. CONCLUSIONS
The paper introduces all-at-once optimization for coupled matrix and tensor factorization, including an extension for incomplete data. Experiments compare it with alternating least squares, while the discussion identifies unresolved scaling and objective-weighting issues.
- Contributions: CMTF-OPT jointly solves for all factor matrices using first-order optimization under squared Euclidean loss.The incomplete-data extension is called CMTF-WOPT and can be extended to multiple incomplete data sets.
- Results: Numerical results show that all-at-once optimization is more robust to overfactoring than the alternating least squares approach.This comparison is reported as consistent with earlier tensor-model findings.
- Limitations: The current formulation does not account for differing component scalings when a data set’s factor matrices are shared across all other data sets.The authors state that additional scalar parameters are needed to address these scaling ambiguities.
- Future work: The paper leaves open how to weight objective-function terms associated with different data sets.A Bayesian framework is identified as a potentially promising direction for this issue.
APPENDIX
The appendix describes how the synthetic clustering example constructs coupled tensor and matrix data from factor matrices encoding two different groupings.
- Data construction: The example constructs a third-order tensor X and a matrix Y coupled in their first mode.The factor matrices are generated for a rank R = 2 construction.
- Factor generation: A1 assigns contrasting noisy values to G1∪G2 versus G3∪G4 across its first factor column, with the second column reversed.This creates one grouping pattern in the factor matrix.
- Factor generation: A2 is generated similarly, but groups G1∪G3 against G2∪G4.The two factor matrices therefore encode different cluster partitions.