### 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*

### =

*M*

**Ã** **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_{1} a

i_{1} = 1, . . . ,I_{1}

2nd-order tensor

I_{1}

### A

i_{2} = 1, . . . ,I_{2}

I_{2}

3rd-order tensor

I_{2}

I_{1}

### A

i_{3} = 1, . . . ,I_{3}

I_{3}

### a

0-order tensor ...

• Individual elements of a vector * a* are given by

*a*

*i*

_{1}, from a matrix

**A**by

*a*

*i*

_{1},

*i*

_{2}

and from a tensor

**A**

^{ by }

^{a}

^{i}^{1}

^{,}

^{i}^{2}

^{,}

^{i}^{3}

• 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**

^{∈}

^{ ℝ}

^{3}

### 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 **

(or 3D volume)
• The *n*-rank of a tensor is typically defined
on an unfolding

‣ *n*-rank *R**n* = rank*n*(

**A**

) = rank(A(n))
‣ multilinear rank-(R1, R2, …, R*N*) of

**A**

I_{2} I_{3}

A

A

I_{1}

I_{1}

I_{2}

I_{3} I_{2}

I_{3}
I_{1}

I_{2}

I_{1}

A

I_{1}

I_{2} I_{3}

I_{3}

I_{3} I_{3}

I_{2} I_{2}

I_{1} I_{1}

A_{(3)}
A_{(1)}

A_{(2)}

I_{2} ·I_{1}
I_{1} ·I_{3}
I_{3} ·I_{2}

### Unfolding and Ranks

14

### Rank-one Tensor

• *N*-mode tensor

**A**

^{∈}

^{ ℝ}

^{I}^{1}

^{×…×I}

^{N}

^{ that can }

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_{3}
I_{2}

### I

_{1}

### A ^{=}

b^{(}^{1}^{)}

b^{(}^{2}^{)}
b^{(}^{3}^{)}

### Tensor Decomposition Models

16

I_{3}
I_{1}

I_{2}

### A

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

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

**Tucker**

*I*1

**U**(1)

*I*2

**U**^{(2)}
*I*3

**U**^{(3}

)

R2

*R*1

*R*3

*R*2

*R*3

*R*1

core tensor *B*
basis matrices U^{(n)}

### B

• **PARAFAC (parallel factors) [ Harshman, 1970 ]**

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

**CP**

*I*1

**U**(1)

*I*2

**U**^{(2)}
*I*3

**U**^{(3}

)

R
*R*

*R*

*R*

coefficients

• Higher order tensor

**A**

^{∈}

^{ ℝ}

^{I}^{1}

^{×…×I}

^{N}^{ }

represented as a product of a core
tensor ^{ }

*B*∈ ℝ

^{R}^{1}

^{×…×R}

*and*

^{N}*N*factor matrices

**U**

^{(n)}∈ ℝ

^{I}

^{n}^{×R}

^{n}‣ using *n*-mode products ×*n*

U^{(}^{3}^{)}
U^{(}^{1}^{)} U^{(}^{2}^{)}

I_{1} I_{2}

I_{1}

I_{2} I_{3}

I_{3}

R_{1} R_{2} R_{3}

R_{1}

R_{2} R_{3}

= B ^{+}

### e

### A

### A = B ⇥

^{1}

### U

^{(}

^{1}

^{)}

### ⇥

^{2}

### U

^{(}

^{2}

^{)}

### ⇥

^{3}

### ··· ⇥

^{N}

### U

^{(}

^{N}

^{)}

### + e

### Tucker Model

17

### CANDECOMP-PARAFAC Model

• *Canonical decomposition or parallel factor analysis model (CP)*

• Higher order tensor

**A**

factorized into a sum of rank-one tensors
‣ normalized column vectors **u***r*(n) define factor

matrices **U**^{(n)}∈ ℝ^{I}^{n}^{×R} and weighting factors *λ**r*

18

U^{(3)}
U^{(}^{1}^{)}

U^{(2)}
I_{1}

I_{2}
I_{1}

I_{2} I_{3}

I_{3}

R R R

### 0

### 0

l_{1}
l_{2}

l_{R}
l_{R} _{1}

A _{=} ... ^{+} e

### A =

### Â

R r=1### l

_{r}

### · u

^{(1)}

_{r}

### u

^{(2)}

_{r}

### . . . u

^{(N}

_{r}

^{)}

### + e

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

### Linear Combination of Rank-one Tensors

19

I_{3}
I_{2}

I_{1}

l_{1}

u^{(1)}_{1}

u^{(2)}_{1}
u^{(3)}_{1}

+^{l}^{2} + . . . _{+}

l_{R}

u^{(2)}_{2}
u^{(1)}_{2}

u^{(3)}_{2} u^{(3)}_{R}

u^{(2)}_{R}
u^{(1)}_{R}

A ^{=} ^{+} e

### A =

### Â

R r=1### l

_{r}

### · u

^{(}r

^{1}

^{)}

### u

^{(}r

^{2}

^{)}

### . . . u

^{(N}r

^{)}

### + 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_{1}
r

### Â

_{1}=1

R_{2}

r

### Â

_{2}=1

### ···

R_{N}
r_{N}

### Â

=1### b

_{r}

_{1}

_{r}

_{2}

_{...r}

_{N}

### · u

^{(}r

^{1}

_{1}

^{)}

### u

^{(}r

^{2}

_{2}

^{)}

### . . . u

^{(N}r

_{N}

^{)}

### + e

u^{(1)}_{R}_{1}

u^{(2)}_{R}_{2}
u^{(3)}_{R}_{3}

u^{(3)}r_{3}

u^{(2)}r_{2}

u^{(1)}r_{1}

I_{3}
I_{2}

I_{1} _{A} _{=} ^{b}^{r}^{1}^{r}^{2}^{r}^{3} + . . . _{+} ^{b}^{R}^{1}^{R}^{2}^{R}^{3} ^{+} e

I_{3}
I_{1}

I_{2}

I_{3}

I_{1}

U^{(3)}

U^{(1)}

I_{2}
U^{(2)}

Af ^{⇡}

R

R R

l_{1}

l_{R}

...

### CP a Special Case of Tucker

20

*I*1

**U**(1)

*I*2

**U**^{(2)}
*I*3

**U**^{(3}

)

R
*R*

*R*

*R* *I*1

**U**(1)

*I*2

**U**^{(2)}
*I*3

**U**^{(3}

)

R2

*R*1

*R*3

*R*2

*R*3

*R*1

### B

### CP Tucker

I_{3}
I_{1}

I_{2}

I_{3}

I_{1}

U^{(3)}
R_{3}

R_{1}

R_{2}
U^{(1)}

I_{2}
U^{(2)}

⇡ B

Af

• Any special form of core and corresponding factor matrices

‣ e.g. blocks along diagonal

B_{1}

I_{1}

I_{2}
I_{1}

I_{2} I_{3}

I_{3}

R R R

### 0

A _{=} _{...}

### 0

^{+}

### e

U^{(1)}_{1} _{U}^{(1)}_{2} . . . _{U}^{(1)}_{P}

. . .

. . .

B_{P}

U^{(3)}_{2}

U^{(}_{P}^{2}^{)}
U^{(2)}_{1} U^{(2)}_{2}

U^{(3)}_{1} U^{(3)}_{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 *R*1, 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^{(}^{3}^{)}
U^{(}^{1}^{)} U^{(}^{2}^{)}

I_{1} I_{2} I_{3}

R_{1} R_{2} R_{3}

R_{1}

R_{2} R_{3}

l_{1}

### B

l_{R}

...

I_{3}
I_{1}

I_{2}

I_{1}

Af ⇡

R

l..._{1} ^{l}^{R}

I_{3}

R

U^{(1)}

U^{(3)}

I_{2}
U^{(2)} R

I_{3}
I_{1}

I_{2}

I_{3}

I_{1}

U^{(3)}

U^{(1)}

I_{2}
U^{(2)}

Af ⇡

R

R R

l_{1}

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 =

### Â

R r=1### l

_{r}

### · u

^{(1)}r

### u

^{(2)}r

### . . . u

^{(N}r

^{)}

I_{3}
I_{1}

I_{2}

I_{3}

I_{1}

U^{(3)}
R_{3}

R_{1}

R_{2}
U^{(1)}

I_{2}
U^{(2)}

f B

A ⇡

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

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

‣

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

‣ Tucker model with limited ranks *R**i*

24

### A f = B ⇥

^{1}

### U

^{(}

^{1}

^{)}

### ⇥

^{2}

### U

^{(}

^{2}

^{)}

### ⇥

^{3}

### ··· ⇥

^{N}

### U

^{(N}

^{)}

I_{3}
I_{1}

I_{2}

I_{3}

I_{1}

U^{(3)}
R_{3}

R_{1}

R_{2}
U^{(1)}

I_{2}
U^{(2)}

⇡ 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 ⇥^{1} U^{(1)} ⇥^{2} U^{(2)} ⇥^{3} U^{(3)}

=

I_{3}
I_{1}

I_{2}

A˜

I_{3}

I_{1}

U^{(3)}
R_{3}

R_{1}

R_{2}
U^{(1)}

I_{2}
U^{(2)}

B

typical high-quality data reduction:

*R**k* ≤ I*k* / 2

### A f = argmin ( A f ) A A f

^{2}

### 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^{(3)}
U^{(1)}

U^{(2)}
I_{1}

I_{2}
I_{1}

I_{2} I_{3}

I_{3}

R R R

### 0

### 0

l_{1}
l_{2}

l_{R}
l_{R} _{1}

A _{=} ... ^{+} e

U^{(3)}
U^{(1)} U^{(2)}

I_{1} I_{2}

I_{1}

I_{2} I_{3}

I_{3}

R_{1} R_{2} R_{3}

R_{1}

R_{2} R_{3}

= B ^{+} e

A