Tensor Decomposition Models

Tutorial: Tensor Approximation in Visualization and Computer Graphics

Tensor Decomposition Models

Renato Pajarola, Susanne K. Suter, and Roland Ruiters

Data Reduction and Approximation

• A fundamental concept of data reduction is to remove redundant and irrelevant information while preserving the relevant features

‣ e.g. through frequency analysis by projection onto pre-defined bases, or extraction of data intrinsic principal components

– identify spatio-temporal and frequency redundancies

‣ maintain strongest and most significant signal components

• Data reduction linked to concepts and techniques of data compression, noise reduction as well as feature extraction and recognition/extraction

8

Data Approximation using SVD

• Singular Value Decomposition (SVD) standard tool for matrices, i.e., 2D input datasets

‣ see also principal component analysis (PCA)

left singular vectors

(column-space)

right singular vectors

(row-space) singular

values M: rows

N: columns

=

A

N N

M N

N N 0

0

U ∑ V^T

9

M

N

=

à U V^T

N

N 0 R 0

R

∑

0

N N

N

Low-rank Approximation

10

• Exploit ordered singular values: s1 ≥ s2 ≥ ... ≥ sN

• Select first r singular values (rank reduction)

N N

M N

~ =

N

à U N

R

V^T R R

R

∑ M

N

Low-rank Approximation

10

• Exploit ordered singular values: s1 ≥ s2 ≥ ... ≥ sN

• Select first r singular values (rank reduction)

‣ use only bases (singular vectors) of corresponding subspace

• Matrix SVD

‣ rank reducibility

‣ orthonormal row/column matrices

Matrix SVD Properties

N N

M N

=

N N 0

0

A U ∑ V^T

M

N

11

What is a Tensor?

• Data sets are often multidimensional arrays (tensors)

‣ images, image collections, video, volume data etc.

12

1st-order tensor

I₁ a

i₁ = 1, . . . ,I₁

2nd-order tensor

I₁

A

i₂ = 1, . . . ,I₂

I₂

3rd-order tensor

I₂

I₁

A

i₃ = 1, . . . ,I₃

I₃

a

0-order tensor ...

• Individual elements of a vector a are given by ai₁, from a matrix A by ai₁,i₂

and from a tensor

A

• The generalization of rows, columns (and tubes) is a fiber in a particular mode

• Two dimensional sections of a tensor are called slices

‣ frontal, horizontal and lateral for

A

Fibers and Slices

13

• Operations with tensors often performed as matrix operations using unfolded tensor

representations

‣ different tensor unfolding strategies possible

• Forward cyclic unfolding A(n) of a 3rd order tensor

A

• The n-rank of a tensor is typically defined on an unfolding

‣ n-rank Rn = rankn(

A

‣ multilinear rank-(R1, R2, …, RN) of

A

I₂ I₃

A

A

I₁

I₁

I₂

I₃ I₂

I₃ I₁

I₂

I₁

A

I₁

I₂ I₃

I₃

I₃ I₃

I₂ I₂

I₁ I₁

A₍₃₎ A₍₁₎

A₍₂₎

I₂ ·I₁ I₁ ·I₃ I₃ ·I₂

Unfolding and Ranks

14

Rank-one Tensor

• N-mode tensor

A

be expressed as the outer product of N vectors

‣ Kruskal tensor

• Useful to understand principles of rank-reduced tensor reconstruction

‣ linear combination of rank-one tensors

15

A = b ^{( 1 )} b ^{( 2 )} ··· b ^{(N )}

I₃ I₂

I

A ⁼

b⁽¹⁾

b⁽²⁾ b⁽³⁾

Tensor Decomposition Models

16

I₃ I₁

I₂

A

• Three-mode factor analysis (3MFA/Tucker3) [ Tucker, 1964+1966 ]

• Higher-order SVD (HOSVD) [ De Lathauwer et al., 2000a ]

Tucker

I1

U(1)

I2

U⁽²⁾ I3

U⁽³

)

R2

R1

R3

R2

R3

R1

core tensor B basis matrices U⁽ⁿ⁾

B

• PARAFAC (parallel factors) [ Harshman, 1970 ]

• CANDECOMP (CAND) (canonical decomposition) [ Caroll & Chang, 1970 ]

CP

I1

U(1)

I2

U⁽²⁾ I3

U⁽³

)

R R

R

R

coefficients

• Higher order tensor

A

‣ using n-mode products ×n

U⁽³⁾ U⁽¹⁾ U⁽²⁾

I₁ I₂

I₁

I₂ I₃

I₃

R₁ R₂ R₃

R₁

R₂ R₃

= B ⁺

e

A

A = B ⇥

U

⇥

U

⇥

··· ⇥

U

+ e

Tucker Model

17

CANDECOMP-PARAFAC Model

• Canonical decomposition or parallel factor analysis model (CP)

• Higher order tensor

A

‣ normalized column vectors ur(n) define factor

matrices U⁽ⁿ⁾∈ ℝ^In×R and weighting factors λr

18

U⁽³⁾ U⁽¹⁾

U⁽²⁾ I₁

I₂ I₁

I₂ I₃

I₃

R R R

0

0

l₁ l₂

l_R l_{R 1}

A ₌ ... ⁺ e

A =

Â

l

· u

u

. . . u

+ e

• The CP model is defined as a linear combination of rank-one tensors

Linear Combination of Rank-one Tensors

19

I₃ I₂

I₁

l₁

u⁽¹⁾₁

u⁽²⁾₁ u⁽³⁾₁

+^l2 + . . . ₊

l_R

u⁽²⁾₂ u⁽¹⁾₂

u⁽³⁾₂ u⁽³⁾_R

u⁽²⁾_R u⁽¹⁾_R

A ^{= +} e

A =

Â

l

· u

u

. . . u

+ e

• The CP model is defined as a linear combination of rank-one tensors

• The Tucker model can be interpreted as linear combination of rank-one tensors

Linear Combination of Rank-one Tensors

19

A =

R₁ r

Â

R₂

r

Â

···

R_N r_N

Â

b

· u

u

. . . u

+ e

u⁽¹⁾_R1

u⁽²⁾_R2 u⁽³⁾_R3

u⁽³⁾r₃

u⁽²⁾r₂

u⁽¹⁾r₁

I₃ I₂

I_{1 A =} ^br1r2r3 + . . . ₊ ^{bR1R2R3 +} e

I₃ I₁

I₂

I₃

I₁

U⁽³⁾

U⁽¹⁾

I₂ U⁽²⁾

Af ^⇡

R

R R

l₁

l_R

...

CP a Special Case of Tucker

20

I1

U(1)

I2

U⁽²⁾ I3

U⁽³

)

R R

R

R I1

U(1)

I2

U⁽²⁾ I3

U⁽³

)

R2

R1

R3

R2

R3

R1

B

CP Tucker

I₃ I₁

I₂

I₃

I₁

U⁽³⁾ R₃

R₁

R₂ U⁽¹⁾

I₂ U⁽²⁾

⇡ B

Af

• Any special form of core and corresponding factor matrices

‣ e.g. blocks along diagonal

B₁

I₁

I₂ I₁

I₂ I₃

I₃

R R R

0

A _{= ...}

0

e

U⁽¹⁾_{1 U}⁽¹⁾₂ . . . _U⁽¹⁾_P

. . .

. . .

B_P

U⁽³⁾₂

U⁽_P²⁾ U⁽²⁾₁ U⁽²⁾₂

U⁽³⁾₁ U⁽³⁾_P

Generalizations

21

• Full reconstruction using a Tucker or CP model may require excessively many coefficients and wide factor matrices

‣ large rank values R (CP), or R1, R2 … RN (Tucker)

• Quality of approximation increases with the rank, and number of column vectors of the factor matrices

‣ best possible fit of these bases matrices discussed later

22

Reduced Rank Approximation

U⁽³⁾ U⁽¹⁾ U⁽²⁾

I₁ I₂ I₃

R₁ R₂ R₃

R₁

R₂ R₃

l₁

B

l_R

...

I₃ I₁

I₂

I₁

Af ⇡

R

l...₁ ^lR

I₃

R

U⁽¹⁾

U⁽³⁾

I₂ U⁽²⁾ R

I₃ I₁

I₂

I₃

I₁

U⁽³⁾

U⁽¹⁾

I₂ U⁽²⁾

Af ⇡

R

R R

l₁

l_R

...

Rank- R Approximation

• Approximation of a tensor as a linear

combination of ranke-one tensors using a limited number R of terms

‣ CP model of limited rank R

23

A f =

Â

l

· u

u

. . . u

I₃ I₁

I₂

I₃

I₁

U⁽³⁾ R₃

R₁

R₂ U⁽¹⁾

I₂ U⁽²⁾

f B

A ⇡

Rank- (R 1 , R 2 , …, R N ) Approximation

• Decomposition into a tensor with reduced, lower multilinear rank(R1, R2, …, RN)

‣

• n-mode products of factor matrices and core tensor in a given reduced rank space

‣ Tucker model with limited ranks Ri

24

A f = B ⇥

U

⇥

U

⇥

··· ⇥

U

I₃ I₁

I₂

I₃

I₁

U⁽³⁾ R₃

R₁

R₂ U⁽¹⁾

I₂ U⁽²⁾

⇡ B

Af

rank_n(Af) = R_n  rank_n(A ) = rank(A_(n))

Best Rank Approximation

25

• Rank reduced approximation that minimizes least-squares cost

‣

• Alternating least squares (ALS) iterative algorithm that converges to a minimum approximation error based on the

Frobenius norm ||…||F

‣ rotation of components in basis matrices

Af= B ⇥¹ U⁽¹⁾ ⇥² U⁽²⁾ ⇥³ U⁽³⁾

=

I₃ I₁

I₂

A˜

I₃

I₁

U⁽³⁾ R₃

R₁

R₂ U⁽¹⁾

I₂ U⁽²⁾

B

typical high-quality data reduction:

Rk ≤ Ik / 2

A f = argmin ( A f ) A A f

Generalization of the Matrix SVD

26

A U ⌃ V^T

M

N

M

N N

N N

N

=

higher orders

CP model

higher orders

Tucker model

U⁽³⁾ U⁽¹⁾

U⁽²⁾ I₁

I₂ I₁

I₂ I₃

I₃

R R R

0

0

l₁ l₂

l_R l_{R 1}

A ₌ ... ⁺ e

U⁽³⁾ U⁽¹⁾ U⁽²⁾

I₁ I₂

I₁

I₂ I₃

I₃

R₁ R₂ R₃

R₁

R₂ R₃

= B ⁺ e

A