Author:

Keywords:

tensor rank decomposition, CANDECOMP/PARAFAC, identifiability, Schmidt-Eckart-Young decomposition

Abstract:

Multidimensional data, or tensors, arise natura lly in data analysis applications. Hitchcock&##39;s rank decomposition is one of several tensor¨ decompositions that can reveal a regular structure ¨underlying such data, and it has found applicatio n in algebraic statistics, chemometrics, mach ine learning and signal processing, among others.¨ This rank decomposition can be regarded as a¨ generalization of the singular value decompos ition ofsecond-order tensors, i.e., matrices. ¨Contrary to the case of matrices,Hitchcock d ecompositions of tensors of order at least three a re not yetthoroughly comprehended at present. Ther efore, in the first part of this thesis, several t heoretical properties of the rank decomposition th at are of practical significance are investigated. ¨The dimension of the setof Hitchcock decompositio ns of a fixed rank is studied with a randomiz ed algorithm that provides probabilistic statement s about this dimension.Since the dimension is usua lly as expected, a more refined inquiry intothe un iqueness of Hitchcock decompositions is undertaken . An efficient algorithm is proposed for proving t hat a generic tensor of low rank admits a unique H itchcock decomposition; it is additionally extende d to certify uniqueness of a given decomposit ion. Thereafter, as a consequence ofthe foreg oing results, it is shown that a Hitchcock decompo sition of a generic tensor of low rank cannot be truncated optimally, in contrast tothe case of matrices. It is demonstrated, moreover, that ¨a rank decomposition, unfortunately, cannot, in g eneral, be computed through a simple greedy algori thm that computes successive rank-1 approximations ¨of the tensor. The second part of the thesis deve lops computational kernels associated with ra nk decompositions. The higher-order singular value ¨decomposition is often employed as a means for re ducing the computational complexity of algori thms for computing Hitchcock&##39;s decomposition.¨ An alternative algorithm for computing the fo rmer, which is more efficient than theclassic ¨approach, is proposed. A strategy for efficiently truncating itis then derived from this alter native algorithm. Finally, an implementation¨ of the computation of the gradient of the obj ective function associated with the rank deco mposition is developed; it attains a throughput th at is close to the theoretical limit of the comput er system while employing only a constant amount o f memory, hereby improving upon the currentstate-o f-the-art algorithms.