Smart Initialization for Smooth and Sparse Tensor Factorization 公开

Abstract

Spatiotemporal data can come from any event that describes phenomena that exist at certain combinations of time and spaces. Its analysis has great real-life implications, such as identifying traffic hot spots. However, the complex nature of spatiotemporal data poses challenges for its analysis. Tensor, a multidimensional array structure, can serve as a container for spatiotemporal data of high dimensions. Tensor decompositions can extract latent patterns in time and space from the data. The CP decomposition is one widely used tensor decomposition model. Fitting a CP model for a tensor can be viewed as a least squares problem.

A gradient based optimization algorithm, CP_OPT, solves the problem by explicating calculate the gradient of the objective function that minimizes the tensor norm of the difference between the original tensor and the CP model. In this study, we customize this general CP_OPT framework for sparse containing spatiotemporal data in the following aspects:

Adding the smoothness constraints on factor matrices to control the change in magnitudes between neighboring entries in the same column; Using high order singular value decomposition (HOSVD) to capture the sparsity patterns in factor matrices generated by CP_OPT; Generating a interlaced HOSVD for the original tensor and truncating trivial entries with magnitudes below a certain threshold; using this HOSVD with truncation as initialization to accelerate the optimization process by utilizing the sparsity.

Table of Contents

1 Introduction 1

1.1 Tensors............................... 4

1.1.1 TensorInnerProduct................... 4

1.1.2 TensorNorm........................ 5

1.1.3 Rank-OneTensors..................... 5

1.2 Notations.............................. 7

1.2.1 Matricization ....................... 8

1.2.2 Then-modeProduct ................... 10

1.2.3 KroneckerProduct .................... 10

1.2.4 Khatri-RaoProduct.................... 11

2 CP Decomposition 12

2.1 TensorRank ............................ 13

2.2 FittingaCPModel ........................ 14

2.3 CPOPT............................... 14

2.3.1 ObjectiveFunction .................... 15

2.3.2 CPGradient ........................ 15

2.4 CPOPTwithSmoothnessPenalty................ 17

2.4.1 Objective Function with Smoothness Penalty . . . . . 17

2.4.2 UpdatedGradient..................... 18

2.5 OptimizationMethodforCPOPT................ 18

3 Experiment Outline 20

3.1 DataDescription.......................... 20

3.2 Setup................................ 21

3.2.1 DatasetResize....................... 21

3.2.2 Determine Rank: Fit and Core Consistency Diagnostic 21

3.3 Select Penalty Strength for the Smoothness Penalty . . . . . . 24

3.4 Visualization of Smoothness Improvement . . . . . . . . . . . 26

3.5 RunningPerformance....................... 31

4 Exploring Sparsity 33

4.1 TuckerDecompositionandHOSVD............... 35

4.2 HOSVD............................... 35

4.3 HOSVDasInitialization ..................... 37

4.3.1 Comparisons between Different Initializations . . . . 38

4.4 SparsityoftheExperimentTensor................ 39

4.5 Learning Sparsity Pattern through HOSVD . . . . . . . . . . 40

4.5.1 Experiments:SparsityPatterns . . . . . . . . . . . . . 41

4.6 HOSVDwithTruncation ..................... 44

4.6.1 Visualization........................ 44

4.7 Experiments ............................ 47

4.7.1 Truncated HOSVD as Initialization for CP OPT . . . . 47

4.7.2 Truncated HOSVD as Initialization for CP OPT with SmoothnessConstraints ................. 48

5 Conclusions 50

5.1 SmoothnessConstraints ..................... 51

5.2 InitializationUsingHOSVD ................... 51

5.3 FutureWork ............................ 52

Bibliography 54

About this Honors Thesis

Rights statement

• Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.

School	Emory College
Department	Mathematics
Degree	B.S.
Submission	Honors Thesis
Language	English
Research Field	Computer Science Mathematics
关键词	tensor CP decomposition sparse tensor HOSVD tensor decomposition
Committee Chair / Thesis Advisor	Joyce C. Ho, Emory University
Committee Members	James G. Nagy, Emory University Yuanzhe Xi, Emory University

最新修改

Primary PDF

Thumbnail	Title	Date Uploaded	Actions
	Smart Initialization for Smooth and Sparse Tensor Factorization ()	2019-04-17 17:07:39 -0400	Press to Select an action Download

Supplemental Files

Thumbnail	Title	Date Uploaded	Actions