Tensor CP Decomposition and Its Applications

Abstract

A tensor is formally defined as a multidimensional array in general. It is a faithful representation format for a variety of complex real-world data, including but not limited to images, videos, multichannel audio signals, high-order networks, contextual recommender systems, and multi-arm spatial-temporal data. Preserving the original and essential information, tensor data are usually huge in size. Therefore, sophisticated techniques should be developed to store the data easily, carry out computation scalably and conduct statistical inference accurately, while minimizing the potential information loss. With the rapid development of such techniques in recent decades, low-rank tensor decomposition is the most prevalent and efficient set of tools to analyze tensor data, such as CANDECOMP/PARAFAC (CP) decomposition, Tucker decomposition, CUR decomposition, and tensor train decomposition. It is known that different tensor decomposition formats have different advantages and limitations. In this thesis, we are interested in the tensor CP decomposition and its applications, particularly in high-order network analysis and multi-arm spatial-temporal data analysis.

In the first part of the thesis, we provide a comprehensive review on tensor CP decomposition. After introducing the relevant concepts, algebraic operators, and their properties, we will provide a formal definition of tensor CP decomposition and tensor CP rank, accompanied with efficient algorithms to conduct CP decomposition. A set of identifiability conditions on the decomposition will be discussed. For completeness, other tensor decomposition formats together with their essentials are also summarized.

In the second part of the thesis, we apply the tensor CP decomposition to high-order networks, particularly in hypergraph networks and multi-layer networks. Conventional network data has largely focused on pairwise interactions between two entities in a single-layer network, yet multi-way interactions among multiple entities or pairwise interactions in multiple relations have been frequently observed in reality, leading to the necessity of hypergraph networks and multi-layer networks. In this part, we first propose a novel method for detecting community structure in general hypergraph networks, uniform or non-uniform. The proposed method introduces a null vertex to augment a non-uniform hypergraph into a uniform multi-hypergraph, and then embeds the multi-hypergraph into a low-dimensional vector space such that vertices within the same community are close to each other. The resultant optimization task can be efficiently tackled by an alternative updating scheme. The asymptotic consistencies of the proposed method are established in terms of both community detection and hypergraph estimation, which are also supported by numerical experiments on some synthetic and real-life hypergraph networks. We next parallelly extend the methodology to multi-layer networks by developing a generative tensor-based latent space model (TLSM). It simultaneously embeds vertices and network layers into low-dimensional latent spaces so that not only vertices within the same community are close to each other in the ambient space but layer heterogeneity can be captured through a layer-effect factor matrix. Simulation results and application of the proposed methods to certain real-life multi-layer networks yield satisfactory results.

In the third part of the thesis, we propose a novel non-negative tensor completion method to predict the potential counterfactual outcomes of multifaceted social mobility restriction policies of different countries over time. The COVID-19 data is a multi-arm spatial temporal data in that only one human mobility restriction policy out of multiple policies, or one arm out of many arms, is implemented to a country at a give day. The proposed method builds upon a non-negative tensor CP decomposition of the COVID-19 pandemic data, which also explicitly characterizes the ordinal nature of the mobility restriction strength and the smooth trend of the pandemic evolution over time. Its application to the COVID-19 pandemic data reveals some interesting facts regarding the impact of social mobility restriction policy on the spread of the virus. The effectiveness of the proposed method is also supported by its asymptotic estimation consistency and extensive numerical experiments on the synthetic datasets.

Date of Award	3 Aug 2023
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Junhui WANG (Supervisor) & Xinyue LI (Supervisor)