Fast Tucker Rank Reduction for Non-Negative Tensors
Using Mean-Field Approximation
Kazu Ghalamkari1,2,Mahito Sugiyama1,2

1 : The Graduate University for Advanced Studies, SOKENDAI
2 : National Institute of Informatics
github.com/gkazunii/Legendre-tucker-rank-reduction

Conference on Neural Information Processing Systems 2021

1

Tensor low-rank approximation

𝒫𝐾𝐾𝑁

𝐶
𝐵

𝒢𝐽

𝑀

𝑁𝒫𝑖𝑗𝑘 = ෍ ෍ ෍ 𝒢𝑖𝑗𝑘 𝐴𝑖𝑙 𝐵𝑗𝑚 𝐶𝑘𝑛
𝑙=1 𝑚=1 𝑛=1

𝑀

≈

I𝐿

I 𝐴
𝐽Tucker rank of 𝒫 : 𝐿, 𝑀, 𝑁𝐿 ≤ 𝐼, 𝑀 ≤ 𝐽, 𝑁 ≤ 𝐾

In this presentation, Tucker rank is simply referred to as Rank.

Rank (1,1,1) is called just rank１．

𝐿Approximating tensors with low rank tensors reduce memory requirements.
Frobenius error or KL error minimization

Many non-negative low-rank approximation methods are based on a gradient method.
→ It requires appropriate settings for initial values, stopping criterion, and learning rates. 😢😢
This study...
・Maps non-negative tensors to distributions, and derive a formula for the best rank-1 approximation
・Understands the rank-1 approximation of a non-negative tensor as a mean-field approximation
・Proposes a fast Tucker rank approximation (LTR) for nonnegative tensors based on the formula 2

Contents◆Best Rank-1 Approximation for Minimizing the KL divergence
ー Make a mapping from a tensor to a distribution
ー A rank-1 condition using parameters of the distribution
ー Rank-1 Approximation as a mean-field approximation◆Legendre Tucker Rank Reduction(LTR)ー A fast low-rank approximation for non-negative tensors
ー Not based on a gradient method.

◆Experiment◆

Conclusion
3

Introduction of log-linear model on poset
Poset

𝑆 is a poset ⇔ for all 𝑠1 , 𝑠2 , 𝑠3 ∈ 𝑆 the following three properties are satisfied.

(1) Reflexivity: 𝑠1 ≤ 𝑠1

(2) Antisymmetry: 𝑠1 ≤ 𝑠2 , 𝑠2 ≤ 𝑠1 ⇒ 𝑠1 = 𝑠2

(3) transitivity:𝑠1 ≤ 𝑠2 , 𝑠2 ≤ 𝑠3 ⇒ 𝑠1 ≤ 𝑠3

Log-linear model on poset SWe define the log-linear model on a poset S as a mapping 𝑝: 𝑆 → 0,1 ．Natural parameters 𝜽 describe the model.
𝑝𝜃 𝑥 = exp ෍ 𝜃 𝑠𝑥∈𝑆𝑠≤𝑥

We can also describe the model by expectation parameters 𝜼 if we use Zeta function.
𝑝𝜂 𝑥 = ෍ 𝜇 𝑥, 𝑠 𝜂 𝑠𝜂 𝑥 = ෍𝑝 𝑠

Möbius function
1𝑠∈𝑆𝑠≥𝑥𝜂-space𝜃-space𝜂(s3 )

𝜃(s3 )●𝑝●𝜃(s2 )
𝜃(s1 )

𝜇 𝑥, 𝑠 = ቐ− σ𝑥≤𝑠<𝑦 𝜇 𝑥, 𝑠0

if 𝑥 = 𝑦
if 𝑥 < 𝑦otherwise𝑝𝜂(s2 )

𝜂(s1 )

Mahito Sugiyama, Hiroyuki Nakahara and4Koji Tsuda"Tensor balancing on statistical manifold“(2017) ICML.

Mapping a poset to a non-negative matrix/tensor.
Matrix
𝑆=𝑖1 , 𝑗1 ≤ 𝑖2 , 𝑗2 ⟺ 𝑖1 ≤ 𝑖2 and 𝑗1 ≤ 𝑗2𝑖, 𝑗 |𝑖, 𝑗 = 1,2, ⋯ 𝑛Normalizer 𝜽11𝟏𝟏

𝜽𝟏𝟐1231𝑝𝜃 (2,2) = exp 𝜃11 + 𝜃12 + 𝜃21 + 𝜃22𝑝𝜂 (2,2) = 𝜂22 − 𝜂23 − 𝜂32 + 𝜂33

21

𝜽𝟐𝟐

𝜽𝟐𝟏

31

2223

𝜼𝟐𝟑

𝜼𝟐𝟐

𝑝𝜃 (𝑖, 𝑗) = exp ෍ ෍ 𝜃𝑖 ′ 𝑗 ′33

32

𝑖 ′ ≤𝑖 𝑗 ′ ≤𝑗

Relation between distribution and matrix

Random Variable
Sample space
Value of the probability：index 𝑖, 𝑗：index set：element 𝑃𝑖𝑗

𝜼𝟑𝟑

𝜼𝟑𝟐
Tensor
𝑆=𝑖, 𝑗, 𝑘 |𝑖, 𝑗, 𝑘 = 1,2, ⋯ 𝑛
211

212

Normalizer
112

111
221

𝑖1 , 𝑗1 , 𝑘1 ≤ 𝑖2 , 𝑗2 , 𝑘2 ⟺ 𝑖1 ≤ 𝑖2 and 𝑗1 ≤ 𝑗2 and 𝑘1 ≤ 𝑘2
𝑝𝜃 (1,1,2) = exp 𝜃111 + 𝜃112𝑝𝜂 1,1,2 = 𝜂222 − 𝜂221 − 𝜂122 + 𝜂112222𝑝𝜃 (𝑖, 𝑗, 𝑘) = exp ෍ ෍ ෍ 𝜃𝑖 ′ 𝑗 ′𝑘 ′
121

122

𝑖 ′ ≤𝑖 𝑗 ′ ≤𝑗 𝑘 ′ ≤𝑘Relation between distribution and matrix

Random Variable
Sample space
Value of the probability：index 𝑖, 𝑗, 𝑘：index set：element 𝑃𝑖𝑗𝑘
5

Various representations of a normalized tensor
Element representation

𝒫𝑖𝑗𝑘

OnetoOne𝜼- representation

𝜽- representation𝑝𝜃 (𝑖, 𝑗, 𝑘)

OnetoOne𝑝𝜂 (𝑖, 𝑗, 𝑘)

We can describe matrix properties by using 𝜽- and 𝜼- representations.

𝐄𝐚𝐬𝐢𝐞𝐫 𝐭𝐨 𝐟𝐨𝐫𝐦𝐮𝐥𝐚𝐭𝐞 𝐚𝐬 𝐚 𝐜𝐨𝐧𝐯𝐞𝐱 𝐩𝐫𝐨𝐛𝐥𝐞𝐦.

6

Describe the rank-1 condition of a tensor using (𝜃,𝜂)
one-body parameters𝜃𝑖11 , 𝜃1𝑗1 , 𝜃11𝑘

many-body parameters𝜂𝑖11 , 𝜂1𝑗1 , 𝜂11𝑘

A parameter other than a one-body parameter

Only one index is 1.

Rank-1 condition (𝜽-representation)
rank 𝒫 = 1 ⟺ its all many-body 𝜃 parameters are 0⟸𝐼𝐽𝐾𝐼𝐽𝐾

𝒫𝑖𝑗𝑘 = exp ෍ ෍ ෍ 𝜃𝑖𝑗𝑘 = exp 𝜃111 exp ෍ 𝜃𝑖11 exp ෍ 𝜃1𝑗1 exp ෍ 𝜃11𝑘
𝑖=1 𝑗=1 𝑘=1

𝒫 = 𝑒 𝜃111

𝑖=2𝑗=2𝑘=2111𝑒 𝜃211𝑒 𝜃121𝑒 𝜃211𝑒 𝜃211+𝜃311⋮
𝑒 𝜃211+𝜃311+⋯+𝜃𝐼11⊗

𝑒 𝜃121+𝜃131⋮
𝑒 𝜃121+𝜃131+⋯+𝜃1𝐽1⊗

𝑒 𝜃211+𝜃311⋮
𝑒 𝜃211+𝜃311+⋯+𝜃11𝐾

The rank of the tensor that can be represented by the Kronecker product of three vectors is 1∎

7

Projection onto rank-1 space
The rank-1 approximation is a projection onto a subspace 𝓑
with all zero many-body natural parameters.
𝜃123

Input tensor●𝜼𝟏𝟏𝒌

I×J×K𝒫

The projection from any input tensor 𝒫 ∈ ℝ>0

𝐷𝐾𝐿 𝒫, 𝒫ത𝑚-projection

But!! It takes too much time to get 𝒫ത using the gradient method.😢😢

𝜃11𝑘𝒫ത 𝜼𝟏𝟏𝒌

𝜃𝐼11

Projection from 𝒫 𝑜𝑛𝑡𝑜 ℬ

Number of natural parameters to optimize is (𝐼+ 𝐽+𝐾)
The computational complexity of the Newton method is 𝑂 𝐼 + 𝐽 + 𝐾 3

●

𝜃1𝑗1

to ℬ is convex.

ℬ…
⋮𝜃𝑖𝑗𝑘 = 0

𝜃1𝐽1

The one-body η is invariant to this 𝑚-projection
Summation in each axial direction is invariant for rank-1 approximation

Let us describe the rank-1 condition with the expectation parameter 𝜼.

𝜃11𝐾8Describe the rank-1 condition using (𝜃,𝜂)Rank-1 condition (𝜽-representation)
rank 𝒫 = 1 ⟺ its all many-body 𝜃 parameters are 0

Rank-1 condition (𝜼-representation)

rank 𝒫 = 1 ⟺ its all many-body 𝜂 parameters are factorizable as 𝜂𝑖𝑗𝑘 = 𝜂𝑖11 𝜂1𝑗1 𝜂11𝑘

9

The closed-formula of the best rank 1 approximation
Rank-1 condition (𝜽-representation)
rank 𝒫 = 1 ⟺ its all many-body 𝜃 parameters are 0
Rank-1 condition (𝜼-representation)

rank 𝒫 = 1 ⟺ its all many-body 𝜂 parameters are factorizable as 𝜂𝑖𝑗𝑘 = 𝜂𝑖11 𝜂1𝑗1 𝜂11𝑘
We derive a solution formula of the best rank-1 approximation.

Best rank-1 tensor formula for minimizing KL divergence (𝑑 = 3 )For any given positive tensor 𝒫 ∈ ℝ𝐼×𝐽×𝐾, its best rank-1 approximation is>0𝐽𝒫ത𝑖𝑗𝑘 =𝐾𝐾𝐼

𝐼

By the way,
Frobenius error
minimization
is NP-hard𝐽෍ ෍ 𝒫𝑖𝑗 ′ 𝑘 ′෍ ෍ 𝒫𝑖 ′ 𝑗𝑘 ′

෍ ෍ 𝒫𝑖 ′ 𝑗 ′ 𝑘 ,𝑗 ′ =1 𝑘 ′ =1𝑘 ′ =1 𝑖 ′ =1𝑖 ′ =1 𝑗 ′ =1

that is, it is hold that𝒫ത = argmin 𝐷KL 𝒫; 𝒬 .
𝒬:rank 𝒬 =1

10

We reproduce the result in K.Huang, et al. "Kullback-Leibler principal component for tensors is not NP-hard." ACSSC 2017

Mean-field approximation and rank-1 approximation
Best rank-1 tensor formula for minimizing KL divergence (𝑑 = 3 )For any given positive tensor 𝒫 ∈ ℝ𝐼×𝐽×𝐾, its best rank-1 approximation is>0𝐽𝒫ത𝑖𝑗𝑘 =𝐾𝐾𝐼𝐼𝐽෍ ෍ 𝒫𝑖𝑗 ′ 𝑘 ′෍ ෍ 𝒫𝑖 ′ 𝑗𝑘 ′෍ ෍ 𝒫𝑖 ′ 𝑗 ′ 𝑘𝑗 ′ =1 𝑘 ′ =1𝑘 ′ =1 𝑖 ′ =1𝑖 ′ =1 𝑗 ′ =1

Normalized vector
Normalized vector
depending on only 𝑖 depending on only 𝑗Normalized vector
depending on only 𝑘A tensor with 𝑑 indices is a joint distribution with 𝑑 random variables.
A vector with only 1 index is an independent distribution with only one random variable.

Rank-1 approximation approximates a joint distribution by a product of independent distributions.
Mean-field approximation : a methodology in physics for reducing a many-body problem to a one-body problem.
11◆Best Rank-1 Approximation for Minimizing the KL divergence
ー Make a mapping from a tensor to a distribution
ー A rank-1 condition using parameters of the distribution
ー Rank-1 Approximation as a mean-field approximation◆Legendre Tucker Rank Reduction (LTR)ー A fast low-rank approximation for non-negative tensors
ー Not based on Gradient method.
ー No need to discuss learning rate, stopping criterion, or initial values◆

Experiment◆

Conclusion
12Formulate Tucker rank reduction by relaxing the rank-1 condition
Rank-1 condition (𝜽-representation)
rank 𝒫 = 1 ⟺ its all many-body 𝜃 parameters are 0𝜃311
𝜃211

Expand the tensor by focusing on the 𝑘-th axis into a rectangular matrix 𝜃 (𝑘)(mode-𝑘 expansion)

𝜃112 𝜃113
𝜃121 𝜃𝑖𝑗𝑘 = 0

The first row and first column are the scaling factors

𝜃131

𝜃111
𝜃 (1) = 𝜃211
𝜃311

𝜃121
00

𝜃131
00

𝜃112
000
0
0000

𝜃113
000 00 00 0

𝜃111
𝜃 (2) = 𝜃121
𝜃131

𝜃211
00

𝜃311
00

𝜃112
000
0
0

0
00

𝜃311
0
0

000000

Two bingos

𝜃111
𝜃 (3) = 𝜃112
𝜃113

𝜃211
00

𝜃311
00

𝜃121
00000000

𝜃131
00000000Two bingos

Rank 1,1,1

Two bingos

13

The relationship between bingo and rank
𝜃111
𝜃 (1) = 𝜃211
𝜃311

𝜃1210
𝜃321

𝜃1310
𝜃331

𝜃1120
𝜃312

00
𝜃322

00
𝜃332

𝜃1130
𝜃313

0000

𝜃323

𝜃333

One bingo

𝜃123
●

𝜃111
𝜃 (2) = 𝜃121
𝜃131

𝜃211
00

𝜃311
𝜃321
𝜃331

𝜃112
00000

𝜃312
𝜃322
𝜃332

𝜃311
00000

𝜃313
𝜃323
𝜃333

No bingo

𝜃111
𝜃 (3) = 𝜃112
𝜃113

𝜃211
00

𝜃311
𝜃312
𝜃313

𝜃121
00000

𝜃321
𝜃322
𝜃323

𝜃131
00000

𝜃331
𝜃332
𝜃333

No bingo

Rank 2,3,3

𝒫 Input tensor
𝐷𝐾𝐿 𝒫 , 𝒫 ′●𝒫′

Subspace with one bingo in the mode-1 direction ℬ 1

Bingo rule (𝑑 = 3 )𝐼 ×𝐼 ×𝐼3

1 2The mode-𝑘 expansion 𝜃 (𝑘) of the natural parameter of a tensor 𝒫 ∈ ℝ>0⇒ rank 𝒫 ≤ 𝐼1 − 𝑏1 , 𝐼2 − 𝑏2 , 𝐼3 − 𝑏3

has 𝑏𝑘 bingos

14

Example: Reduce the rank of (8,8,3) tensor to (5,8,3) or less
𝜃 can be any𝜃 is zero

STEP1 : Choose a bingo location.

Bingo

Bingo

Bingo

15

Example: Reduce the rank of (8,8,3) tensor to (5,8,3) or less
𝜃 can be any𝜃 is zero

STEP1 : Choose a bingo location.

The shaded areas do not change their values in the projection.
16

Example: Reduce the rank of (8,8,3) tensor to (5,8,3) or less
𝜃 can be any𝜃 is zero

STEP1 : Choose a bingo location.
STEP2 : Replace the bingo part withthe best rank-1 tensor.

Replace the partial tensor in the red box using the best rank 1 approximation formula
The best tensor is obtained in the specified bingo space. 😄
There is no guarantee that it is the best rank (5,8,3) approximation.

😢

17

Example: Reduce the rank of (8,8,3) tensor to (5,7,3) or less.
𝜃 can be any𝜃 is zero

STEP1 : Choose a bingo location.
STEP2 : Replace the bingo part withthe best rank-1 tensor.

The shaded areas do not change in the projection.

18

Experimental results (synthetic data)

LTR is faster with the competitive approximation performance.
19Experimental results (real data)(92, 112, 400)

(9, 9, 512, 512, 3)

LTR is faster with the competitive approximation performance.
20

Conclusion■ Describe the rank-1 condition using (𝜃,𝜂)Low-rank condition (𝜽-representation)

Rank-1 condition (𝜼-representation)

Bingo reduces rank𝜂ҧ 𝑖𝑗𝑘 = 𝜂ҧ 𝑖11 𝜂ҧ1𝑗1 𝜂ҧ11𝑘

Rank-1 condition (𝜽-representation)

𝜃𝑖𝑗𝑘
Input 𝒫

ҧ are 0All many body 𝜃𝑖𝑗𝑘

●𝐷𝐾𝐿 𝒫, 𝒫ത

We discuss low-rank approximation as a problem of projection in (𝜽, 𝜼)-space■ Best rank-1 tensor formula for minimizing KL divergence𝐽𝒫ത𝑖𝑗𝑘 =𝐾𝐾𝐼𝐼𝐽෍ ෍ 𝒫𝑖𝑗 ′ 𝑘 ′෍ ෍ 𝒫𝑖𝑗 ′ 𝑘 ′෍ ෍ 𝒫𝑖 ′ 𝑗 ′ 𝑘𝑗 ′ =1 𝑘 ′ =1𝑘 ′ =1 𝑖 ′ =1𝑖 ′ =1 𝑗 ′ =1

■ Legendre Tucker Rank Reduction (LTR)

𝒫ത
𝜃1𝑗1

𝜃11𝑘●ℬ・LTR is based on mean-field approximation．
・LTR is faster with the competitive approximation performance as existing methods.
・No need to discuss learning rate, stopping criteria, or initial values
21