Plug-and-Play of Least Squares based Tensor Decomposition Algorithms for Tensor Learning

Presented in RIKEN AIP seminar at 2025/8/4.
https://tensorworkshop.github.io/RIKENAIP_TRML2025/

Transcript

1. Plug-and-Play of Least Squares based Tensor Decomposition Algorithms for Tensor Learning Tatsuya Yokota Nagoya Institute of Technology / RIKEN AIP [AIP Progress Report Meeting Series] Workshop on Tensor Representation for Machine Learning
2. 3 Summary of my projects (since 2019) Hankelization in tensor learning ⚫ [IEEE SPL, 2020] Matrix and Tensor Completion in Multiway Delay Embedded Space Using Tensor Train, with Application to Signal Reconstruction ⚫ [AAAI, 2020] Block Hankel Tensor ARIMA for Multiple Short Time Series Forecasting ⚫ [IEEE TNNLS, 2022] Manifold Modeling in Embedded Space: An Interpretable Alternative to Deep Image Prior ⚫ [CVPR, 2022] Fast Algorithm for Low-rank Tensor Completion in Delay-embedded Space ⚫ [IEEE Access, 2023] A New Model for Tensor Completion: Smooth Convolutional Tensor Factorization Sparse regularization in tensor learning ⚫ [SN Computer Science, 2022] Bayesian tensor completion and decomposition with automatic CP rank determination using MGP shrinkage prior ⚫ [IEEE CAI Workshop, 2024] Tensor Completion with Adaptive Block Multi-layer Sparsity-based CP Decomposition ⚫ [EUSIPCO, 2024] Adaptive Block Sparse Regularization under Arbitrary Linear Transform Algorithm development in tensor learning ⚫ [IEEE CAI Workshop, 2024] ADMM-MM Algorithm for General Tensor Decomposition ⚫ [Frontiers in Applied Mathematics and Statistics, 2025] Expectation-Maximization Alternating Least Squares for Tensor Network Logistic Regression Medical imaging using tensor learning ⚫ [ICCV, 2019] “Dynamic PET Image Reconstruction Using Nonnegative Matrix Factorization Incorporated with Deep Image Prior ⚫ [HPC Asia, 2024] "Efficient implementation and acceleration of DIP-NMF-MM algorithm for high-precision 4D PET image reconstruction“
3. 4 Book 1 Tensors for Data Processing, Elsevier, 2021 [link] Outline Chapter 1: Tensor decompositions: Computations, applications, and challenges Chapter 2: Transform-based tensor SVD in multidimensional image recovery Chapter 3: Partensor Chapter 4: A Riemannian approach to low-rank tensor learning Chapter 5: Generalized thresholding for low-rank tensor recovery Chapter 6: Tensor principal component analysis Chapter 7: Tensors for deep learning theory Chapter 8: Tensor network algorithms for image classification Chapter 9: High-performance TD for compressing and accelerating DNN Chapter 10: Coupled tensor decomposition for data fusion Chapter 11: Tensor methods for low-level vision T. Yokota, CF. Caiafa, and Q. Zhao Summary of Optimization Algorithms for Image Reconstruction Chapter 12: Tensors for neuroimaging Chapter 13: Tensor representation for remote sensing images Chapter 14: Structured TT decomposition for speeding up kernel learning Qibin Zhao (RIKEN AIP) Cesar F. Caiafa (CONICET)
4. 5 Book 2 (in Japanese) テ ン ソ ル デ ー タ 解 析 の 基 礎 と 応 用 - テ ン ソ ル 表 現 ， 縮 約 計 算 ， テ ン ソ ル 分 解 と 低 ラ ン ク 近 似 - 1. Tensor representation of information 1.1 Fundamentals of Vectors, Matrices, and Tensors 1.2 Examples of Tensor Expressions 2. Tensor Transformation and Calculation 2.1 Basics 2.2 Tensor Variants 2.3 Calculating Tensors 3. Linear Algebra and Principal Component Analysis 3.1 Linear Algebra Highlights 3.2 Principal component analysis 4. Tensor decomposition 4.1 Rank 1 Tensor 4.2 CP Decomposition 4.3 Tucker Decomposition 4.4 Tensor Train Decomposition 4.5 Other Tensor Decomposition Models 5. Tensor Data Analysis 5.1 Linear Observation Models and Inverse Problems of Tensor Data 5.2 Tensor Data Analysis Methodology 5.3 Preparing for Optimization 5.4 Analysis of Tensor Data with Missing Values 5.5 Analysis of Tensor Data with Sparse Components [link]
5. 6 Very Basics of Tensors … (in arXiv) It is partially translated in arXiv.
6. 7 Tensor Learning Typical flow (1) Data Tensor Representation Tensor Decomposition Results + + ◦ ◦ ◦ Noise reduction Inpainting / completion Background modeling Foreground modeling Tracking Anomaly detection …
7. 8 Tensor Learning Typical flow (2) ⚫ Models are parameterized with tensors ⚫ If order of tensors are too high… (curse of dimensionality) ⚫ Tensors are compressively represented by tensor networks (to be tractable) Data Learning Model Results + + ◦ ◦ ◦ Pattern analysis Regression model Classification model Segmentation model Generative model …
8. 9 Tensor Learning One of Goals in “ Tensor Learning ” ⚫ Approximation of function ➢If we learn a tensor ➔ then we can predict any entries by inner product sampling Continuous function Learn a tensor pick 1 entry One-hot tensor unit vectors unknown We have some data about unknown func. Discrete function
9. 10 Tensor Learning One of Goals in “ Tensor Learning ” ⚫ Approximation of function ➢If we learn a tensor ➔ then we can predict any value by inner product, too Continuous function Learn a tensor pick 1 value basis function rank-1 basis function unknown We have some data about unknown func. Continuous function
10. 11 An essential issue of tensor learning Curse of dimensionality D＝1 D＝2 D＝3 ・・・ order / dim #entries D=3 1,000 D=4 10,000 D=5 100,000 D=6 1,000,000 ・・・ rank-1 basis function unit vectors ・・・ ・・・ I=10
11. 12 ・・・ Bressing dimensionality by using Tensor Networks Tensor Network Decomposition solves rank-1 basis function unit vectors ・・・ ・・・ (full) Tensor Tensor-Train format I I I I I I I I R R R order / dim #entries #params D=3 1,000 1,200 D=4 10,000 2,200 D=5 100,000 3,200 D=6 1,000,000 4,200 rank-1 basis function unit vectors ・・・ I=10, R=10
12. 13 Tensor learning for classification Supervised Learning with Tensor Networks [Stoudenmire+, 2016 (in NeurIPS)] ⚫ Model: TT decomposition ⚫ Loss: l2 loss ⚫ Optimization: Sweep ➢ Gradient descent (GD) + SVD
13. 14 Our Motivation Let us consider to extend / modify it as follows: ⚫ Model: TT decomposition ➔ other tensor networks ⚫ Loss: l2 loss ➔ other loss functions ⚫ Optimization: Sweep ➢ Gradient descent (GD) + SVD ➔ alternating least squares (ALS)
14. 15 Subject 1: Development of LS solver We show that l2 minimization can be solved by ALS one sample representation ・・・ ・・・ n samples representation super-diagonal tensor (D) 2 ー ー
15. 16 Subject 1: Development of LS solver Alternating Least Squares (ALS) algorithm ・・・ D ー ・・・ D ー ・・・ D ー … D ー For TT decomposition, each step essentially solves
16. 17 Subject 1: Development of LS solver Tensor-Train for classification ⚫ ALS is much faster than GD ⚫ ALS has no hyper-parameter ⚫ Monotonically non-increasing
17. 18 Subject 1.5: Development of LS solver for any TNs Developing universal solver for learning any TNs (ongoing work) ⚫ Representing the structure of TN as a graph ➔ Automatically generating algorithms ⚫ Best environment: freely design architecture, and optimized automatically ⚫ Technical challenges ➢ vanishing gradient (or there are many bad local optima) ➢ searching best order of contraction ➢ efficient optimization like stochastic / randomized method D D D D D D D D
18. 19 Subject 2: Plug-and-Play LS solver in MM / ADMM Basically, ALS is for l2-loss ⚫ Here, we propose to use ALS for other loss ⚫ Loss functions are important to model noise statistics of data Two approaches to Plug-and-Play (PnP) LS solver ⚫ MM (Majorization-Minimization) ⚫ ADMM (Alternating Direction Method of Multipliers) MM / ADMM Apply LS solver Update other sub-params Depends only on the loss function Depends only on the tensor network PnP … logistic l1 loss l2 loss PnP
19. 20 Subject 2: Plug-and-Play LS solver in MM / ADMM MM (majorization-minimization) algorithm ⚫ An optimization method to solve ⚫ Iterative minimization of surrogate functions ➢ Two conditions are required ➢ Objective function is monotonically non-increasing [Sun+, IEEE TSP 2017] Apply LS solver Update other sub- params majorization minimization majoriz ation minimiz ation
20. 21 Application of MM to logistic regression MM-ALS Majorization by Polya-Gamma (PG) augmentation Logistic loss Value of and are determined by current solution It can be minimized by using ALS Apply LS solver Update other sub-params Update of and Update of
21. 22 Logistic Regression with Tensor Learning Tensor Train for logistic regression ⚫ MM-ALS is much faster than GD ⚫ MM-ALS has no hyper-parameter ⚫ Monotonically non-increasing Yamauchi, Hontani and Yokota (2025) Frontiers in Applied Mathematics and Statistics.
22. 23 Subject 2: Plug-and-Play LS solver in MM / ADMM ADMM algorithm ⚫ Problem ⚫ 3 step algorithm: Apply LS solver Update other sub- params
23. 24 Subject 2: Plug-and-Play LS solver in MM / ADMM ADMM algorithm ⚫ We consider to solve ⚫ 3 step algorithm: It can be minimized by using ALS Typical losses are having closed form solution
24. 25 Application of ADMM for Robust Tensor Learning Apply LS solver Update other sub-params Update of Update of and l1 loss KLdiv CPD TKD TRD Mukai, Hontani and Yokota (2025) arXiv.
25. 26 Summary MM and ADMM can be used for Tensor Learning Different TNs and losses can be easily combined in PnP manner!! ⚫ #combinations = #models × #losses Now, we can apply many TNs for many SP / ML tasks in a PnP manner!! MM / ADMM Apply LS solver Update other sub-params Depends only on the loss function Depends only on the tensor network PnP … logistic l1 loss l2 loss PnP