Saarland University, Machine Learning Group, Fak. MI - Mathematik und Informatik, Campus E1 1, 66123 Saarbrücken, Germany     

Machine Learning Group
Department of Mathematics and Computer Science - Saarland University

POWER METHOD FOR THE MAXIMAL -SINGULAR VALUE OF NON-NEGATIVE TENSORS

by Antoine Gautier and Matthias Hein

TENSOR PROJECTIVE NORM

Given a tensor of order m and , we propose in our paper, a power method type algorithm for computing a maximizer of the following problem:

 

 

where denotes the usual pi-norm on and is the multi-linear form associated to the tensor , i.e.

 

 

with .

 

Matrix case: When the tensor is of order m = 2, i.e. is a matrix, the maximization problem above reduces to the so-called matrix p, q-norm, namely

 

 

with .

 

Remark 1. Provided that the convergence assumptions are fulfilled, the algorithm produces two monotonic sequences such that

 

 

and thus can also be used to simply obtain an upper bound on .

 

CONVERGENCE GUARANTEE

The method is guaranteed to converge to a global maximizer of the optimization problem above if:


a) is non-negative, i.e. for all .

 

b) and there exists such that

Example:

 

c) The tensor is weakly irreducible. That is, the undirected m-partite graph G(T) = (V,E) is connected where

 

is the disjoint union of and

 

such that

 

Example:

     with          and     

 

 

Matrix case: When the tensor is a matrix, then the three conditions above reduce to:


a) A is non-negative, i.e. for every .


b) and .


c) A is weakly irreducible (see definition above).


Example: If , then the undirected graph G(A) is given by

 


and therefore A is weakly irreducible because G(A) is connected.


DOWNLOAD AND LICENSE

Please include a reference to our preprint

if you find this code useful for your research.

Download TensorNorm.zip