Tensor Decomposition with Smoothness (ICML2017)
Masaaki Imaizumi1Kohei Hayashi2,3

1 Institute of Statistical Mathematics
2 National Institute of Advanced Industrial Science and Technology
3 RIKEN Center for Advanced Intelligence ProjectAugust 4, 2017

M.Imaizumi and K.Hayashi

Tensor Decomposition with Smoothness (ICML2017)

August 4, 2017

1 / 18Tensor Decomposition

Tensor Data
Tensor data
Data as a multi-dimensional array.
X ∈ RI1 ×···×IK
K : mode, Ik : # elements

3D fMRI image

Recommendation system(X-axis × Y -axis × Z-axis)(item × time × user)M.Imaizumi and K.Hayashi

Tensor Decomposition with Smoothness (ICML2017)

August 4, 20172 / 18Tensor Decomposition

Tensor Decomposition : Low Rank
Tensor data are high-dimensional.
E.g., 3D image : 1000 pixels for each axis ⇒ 109 pixels

Dimension Reduction is important

M.Imaizumi and K.Hayashi

Tensor Decomposition with Smoothness (ICML2017)

August 4, 20173 / 18Tensor Decomposition

Tensor Decomposition : Low Rank
Tensor data are high-dimensional.
E.g., 3D image : 1000 pixels for each axis ⇒ 109 pixels

Dimension Reduction is important
Tensors are low-rank ⇒ Tucker Decomposition (Tucker (1966))
X=

R1 ,...,RXK(k)(k)
gr1 ,··· ,rK x(k)r1 ⊗ xr2 ⊗ . . . xrK

r1 ,...,rK =1
X(R1X , . . . , RK) : rank of X, gr1 ,...,rK : coefficients

M.Imaizumi and K.Hayashi

Tensor Decomposition with Smoothness (ICML2017)

August 4, 20173 / 18

Idea of Smoothness

New Approach for Dimension Reduction
Smoothness appears in real data.
A pair of adjacent elements are similar.

Time Series data
(Smooth in Time)

M.Imaizumi and K.Hayashi

Image data(Smooth in Location)

Tensor Decomposition with Smoothness (ICML2017)

August 4, 20174 / 18

Idea of Smoothness

Idea of Smoothness
Generating Process for Smooth Tensor
Tensor data are generated by smooth functions.

Tensor (matrix)
with Smoothness

M.Imaizumi and K.Hayashi

Tensor Decomposition with Smoothness (ICML2017)

August 4, 2017

5 / 18

Idea of Smoothness

Idea of Smoothness
Generating Process for Smooth Tensor
Tensor data are generated by smooth functions.

⇐GenerateTensor (matrix)
with Smoothness

M.Imaizumi and K.Hayashi

Generating Process(Smooth Function)

Tensor Decomposition with Smoothness (ICML2017)

August 4, 2017

5 / 18

Idea of Smoothness

Idea of Smoothness
Generating Process for Smooth Tensor
Tensor data are generated by smooth functions.

⇐GenerateTensor (matrix)
with Smoothness

Generating Process(Smooth Function)

Our Idea
Introduce the smooth generating function into the tensor data.
M.Imaizumi and K.Hayashi

Tensor Decomposition with Smoothness (ICML2017)

August 4, 2017

5 / 18

Idea of Smoothness

Smoothness Formation of Tensors
Let X ∈ RI1 ×···×IK be K-mode tensor.
Function : fX : [0, 1]K → R, Grids : {(gj1 , . . . , gjK ) ∈ [0, 1]K }X is represented by observed value of fX on the grids.
[X]j1 ...jK = fX (gj1 , . . . , gjK ).

K = 2 (matrix) casefX (·, ·){(gj1 , gj2 ) ∈ [0, 1]2 }fX (gj1 , gj2 )Main Assumption
fX is smooth ( differentiable ).
M.Imaizumi and K.Hayashi

Tensor Decomposition with Smoothness (ICML2017)

August 4, 20176 / 18

Idea of Smoothness

Functional Representation of Tensors
Representation Theorem{φj (·) : [0, 1] → R}∞
j=1 : orthonormal basis (given)fX (g1 , . . . , gK ) =X···

m1X

wm1 ...mK φm1 (g1 ) · · · φmK (gK ).

mK⇓ Discretize ([X]j1 ...jK = fX (gj1 , . . . , gjK ))Smooth Tensor Formation
WX ∈ RM(1) ×···×M (K)[X]j1 ...jK =(1)
MX

m1 =1

M.Imaizumi and K.Hayashi: coefficient tensor (M (k) : # basis, M (k) ≤ Ik )···(K)MX

mK =1[WX ]m1 ...mK φm1 (gj1 ) · · · φmK (gjK ) .
|{z}|{z}coefficient
givenTensor Decomposition with Smoothness (ICML2017)

August 4, 20177 / 18

Idea of Smoothness

Image of the formation(φ1 , ..., φM ) is given.
fX is smooth ⇒ small M (k) can represent fX ⇒ WX is small
Dimension Reduction by Smoothness.
M.Imaizumi and K.Hayashi

Tensor Decomposition with Smoothness (ICML2017)

August 4, 20178 / 18

Idea of Smoothness

Decomposition Method
A model for tensor completion (n elements are observed).
Y = X(X ∗ ) + E.
X ∗ ∈ RI1 ×···×IK : true tensor (unknown)
Y ∈ Rn : observed vector
X : RI1 ×···×IK → Rn : rearranging operator (known)
E ∈ Rn : noise vector (each element is i.i.d. Gaussian)

Method for Tucker decomposition with low-rank X ∗ (Liu et al.(2009))12
kY − X(X)k + λn |||X|||s ,minX
2nwhere |||·|||s is the Schatten-1 norm (rank regularization for X).
M.Imaizumi and K.Hayashi

Tensor Decomposition with Smoothness (ICML2017)

August 4, 20179 / 18

Idea of Smoothness

Our Decomposition Method

Decomposition method for smooth X
Regularize the coefficient tensor WX .

Smooth Tucker Decomposition (STD)
1minkY − X(X)k2F + λn |||WX |||s + µn |||WX |||2F,
WX 2n| {z }| {z }|{z}
Rank Penalty Volume Penalty
Empirical Loss|||·|||F : the Frobenius norm, |||·|||s : Schatten-1 norm
Solved by the alternating direction method of multipliers (ADMM).

M.Imaizumi and K.Hayashi

Tensor Decomposition with Smoothness (ICML2017)

August 4, 201710 / 18

Evaluation

Error Bound
Decomposition Accuracyb : estimated by STDX ∗ : true tensor, XWW(R1 , . . . , RK ) : the Tucker rank of WX .
Theorem 1Suppose the smoothness and some assumptions hold, then with high probability,b − X ∗ |||2 ≤ C
|||X
FK−1

K pq
X
Ik + I\k!2K−1

k=1|

K q
X!2RkW.

k=1{zFrom Noise}|{z}:=ABy the original Tucker decomposition (Tomioka et al.(2011)),
A=K −1

K q
X!2RkX.

(RkX is rank of X, RkW ≤ RkX in general.)k=1
M.Imaizumi and K.Hayashi

Tensor Decomposition with Smoothness (ICML2017)

August 4, 201711 / 18

Evaluation

Experiments for Accuracy

Experiments : Recovery X ∗ with noise
Compare the squared error with a smooth X ∗ and a nonsmooth X ∗ .
The proposed method outperforms when X ∗ is smooth

ProposedTucker 1
Tucker 2
MatrixM.Imaizumi and K.Hayashi

Tensor Decomposition with Smoothness (ICML2017)

August 4, 201712 / 18

Evaluation

Function Estimation
We can estimate fX , not only X ∗cX : the minimizer of the problem of STD.
WDefine the estimator for fX asfb :=(1)MX

m1 =1···(K)MXcX ]m ...m φm · · · φm
[W11KKmK =1

Theorem 2
Suppose the conditions for Theorem 1 hold. Then, we havesup |fb(g) − fX (g)| ≤ Same Boundg∈[0,1]K

M.Imaizumi and K.Hayashi

Tensor Decomposition with Smoothness (ICML2017)

August 4, 201713 / 18

Evaluation

Experiments (image interpolation)
Interpolate amino acid data (Kier et al.(1998)).
Shed light to amino acids and measure the volume of absorbed andreflected light with each wavelength.

Observed

Tucker

STD(proposed)

Figure: Completion of missing elements of the acid data.
M.Imaizumi and K.Hayashi

Tensor Decomposition with Smoothness (ICML2017)

August 4, 201714 / 18

Evaluation

Experiments (motion interpolation)
Interpolate video data (Schuldt et al.(2004)).
0.18 sec(50% missing)
Tucker
STD(proposed)
0.22 sec

0.14 sec(100% missing)
Tucker
STD(proposed)

M.Imaizumi and K.Hayashi

Tensor Decomposition with Smoothness (ICML2017)

August 4, 201715 / 18

Summary

Summary

TopicsHigh-dimensional tensor data.

Idea
Using information of real data improves analysis.
Smoothness is a key factor for dimension reduction.

ResultAccurate and good analysis.

M.Imaizumi and K.Hayashi

Tensor Decomposition with Smoothness (ICML2017)

August 4, 201716 / 18

Summary

Reference
Liu, Ji, Musialski, Przemyslaw, Wonka, Peter, and Ye, Jieping. Tensor
completion for estimating missing values in visual data. In ICCV,2009.
Tomioka, Ryota, Suzuki, Taiji, Hayashi, Kohei, and Kashima, Hisashi.
Statistical performance of convex tensor decomposition. In NIPS,
2011.
Tucker, Ledyard R. Some mathematical notes on three-mode factor
analysis. Psychometrika, 31(3):279–311, 1966.
Kiers, Henk AL. A three-step algorithm for candecomp/parafac
analysis of large data sets with multi- collinearity. Journal ofChemometrics, 12(3):155–171, 1998.
Schuldt, Christian, Laptev, Ivan, and Caputo, Barbara. Recognizing
human actions: A local svm approach. In Pat- tern Recognition,
2004. In ICPR 2004.
M.Imaizumi and K.Hayashi

Tensor Decomposition with Smoothness (ICML2017)

August 4, 201717 / 18

SummaryImages

Irasuto-ya http://www.irasutoya.com
Slicer Web http://slicer.org
http://mymilitarybases.com/military-finance/

M.Imaizumi and K.Hayashi

Tensor Decomposition with Smoothness (ICML2017)

August 4, 201718 / 18