Matlab Codes of Semidefinite Relaxations

For Best Rank-1 Tensor Approximations

by Jiawang Nie and Li Wang

Purposes of the Codes

They are for finding the best rank-1 approximations for symmetric and nonsymmetric tensors.

They are based on the methods in the paper:
Jiawang Nie and Li Wang, Semidefinite Relaxations For Best Rank-1 Tensor Approximations, arxiv:...

Installation

Download the zip file tensor1aprx.zip and extract it to the directory where you save this file.
Make sure your computer has installed C++ compliers and Matlab 7.10 or above.

Then do the following steps in Matlab:

(1) Install the SDP solver SDPNAL by Xinyuan Zhao, Defeng Sun, and Kim-Chuan Toh.
It is available from Professor Toh's website: http://www.math.nus.edu.sg/~mattohkc/SDPNAL.html

(2) unzip the file tensor1aprx.zip, and the files are extracted to the directory tensor1aprx; open a Matlab window in this directory.

(3) mex -setup, choose a C++ compiler;

(4) run installmex.m;

(5) run startup.m.

How to use the code?

There are two main functions:
  • symtensor1aprx.m is used to find best symmetric rank-1 approximations to symmetric tensors;
  • nsymtensor1aprx.m is used to find best rank-1 approximations to nonsymmetric tensors.
  • In Matlab window, type
    help symtensor1aprx
    help nsymtensor1aprx
    
    for the help of using them.

    Symmetric Tensor Example

    There are two input formats for symmetric tensors, with order m and dimension n.

    Consider the following 3 x 3 x 3 symmetric tensor:

    F_{111} = -0.1281, F_{112} = 0.0516, F_{113} = -0.0954, F_{122} = -0.1958, F_{123} = -0.1790,
    F_{133} = -0.2676, F_{222} = 0.3251, F_{223} =  0.2513, F_{233} =  0.1773, F_{333} =  0.0338. 
  • Format 1: A tensor F is represented by a matrix T of (m+1) columns, whose i-th row is (i_1, ..., i_m, f_i) such that F_{i_1,...,i_m} = f_i.
    input:
          tensor: given in format 1
               n: the dimension of the symmetric tensor
            pars: a structure pars.fmt = 1; (tensor is given in format 1)
    
    output:
     bstrk1_tensor: the computed rank-1 tensor approximation
        runtimesdp: time consumed to solve semidefinite relaxations
           runinfo: a structure listing approximation quality
    
    For the above tensor, we can run as follows:
     tensor = ...
             [ 1 1 1 -0.1281;  ...
               1 1 2  0.0516;  ...
               1 1 3 -0.0954;  ...
               1 2 2 -0.1958;  ...
               1 2 3 -0.1790;  ...
               1 3 3 -0.2676;  ...
               2 2 2  0.3251;  ...
               2 2 3  0.2513;  ...
               2 3 3  0.1773;  ...
               3 3 3  0.0338];
     n = 3;
     pars.fmt = 1;
     [bstrk1_tensor,runtimesdp,runinfo] = symtensor1aprx(tensor,n,pars);
     
  • Format 2: A tensor F is represented by a mutli-dimensional array T in the space R^{n x ... x n} such that T(i_1, ..., i_m) = F_{i_1,...,i_m}.
    input:
          tensor: given in format 2
               n: the dimension of the symmetric tensor
            pars: a structure pars.fmt = 2; (tensor is given in format 2)
    
    output:
     bstrk1_tensor: the computed rank-1 tensor approximation
        runtimesdp: time consumed to solve semidefinite relaxations
           runinfo: a structure listing approximation quality
    
    For the above tensor, we can run as follows:
    tensor(1,1,1) = -0.1281;
    tensor(1,2,1) =  0.0516;
    tensor(1,3,1) = -0.0954;
    tensor(2,1,1) =  0.0516;
    tensor(2,2,1) = -0.1958;
    tensor(2,3,1) = -0.1790;
    tensor(3,1,1) = -0.0954;
    tensor(3,2,1) = -0.1790;
    tensor(3,3,1) = -0.2676;
    tensor(1,1,2) =  0.0516;
    tensor(1,2,2) = -0.1958;
    tensor(1,3,2) = -0.1790;
    tensor(2,1,2) = -0.1958;
    tensor(2,2,2) =  0.3251;
    tensor(2,3,2) =  0.2513;
    tensor(3,1,2) = -0.1790;
    tensor(3,2,2) =  0.2513;
    tensor(3,3,2) =  0.1773;
    tensor(1,1,3) = -0.0954;
    tensor(1,2,3) = -0.1790;
    tensor(1,3,3) = -0.2676;
    tensor(2,1,3) = -0.1790;
    tensor(2,2,3) =  0.2513;
    tensor(2,3,3) =  0.1773;
    tensor(3,1,3) = -0.2676;
    tensor(3,2,3) =  0.1773;
    tensor(3,3,3) =  0.0338;
    n = 3;
    pars.fmt = 2;
    [bstrk1_tensor,runtimesdp,runinfo] = symtensor1aprx(tensor,n,pars);
    
  • Nonsymmetric Tensor Example

    Format: Use Matlab multidimensional arrays to represent the tensor.

    input:
          tensor: given in format of multi-dimensional arrays
            tdim: [n_1, ..., n_m], the dimensions of the tensor
    
    output:
     bstrk1_tensor: the computed rank-1 tensor approximation
        runtimesdp: time consumed to solve semidefinite relaxations
           runinfo: a structure listing approximation quality
    
    For the following 3 x 3 x 3 nonsymmetric tensor
    F_{111} = 0.4333, F_{121} = 0.4278, F_{131} = 0.4140, F_{211} = 0.8154, F_{221} = 0.0199, F_{231} = 0.5598, F_{311} = 0.0643, F_{321} = 0.3815, F_{331} = 0.8834,
    F_{112} = 0.4866, F_{122} = 0.8087, F_{132} = 0.2073, F_{212} = 0.7641, F_{222} = 0.9924, F_{232} = 0.8752, F_{312} = 0.6708, F_{322} = 0.8296, F_{332} = 0.1325,
    F_{113} = 0.3871, F_{123} = 0.0769, F_{133} = 0.3151, F_{213} = 0.1355, F_{223} = 0.7727, F_{233} = 0.4089, F_{313} = 0.9715, F_{323} = 0.7726, F_{333} = 0.5526.
    we can run as follows in Matlab:
    tdim = [3  3  3];
    tensor(1,1,1) = 0.4333;
    tensor(1,2,1) = 0.4278;
    tensor(1,3,1) = 0.4140;
    tensor(2,1,1) = 0.8154;
    tensor(2,2,1) = 0.0199;
    tensor(2,3,1) = 0.5598;
    tensor(3,1,1) = 0.0643;
    tensor(3,2,1) = 0.3815;
    tensor(3,3,1) = 0.8834;
    tensor(1,1,2) = 0.4866;
    tensor(1,2,2) = 0.8087;
    tensor(1,3,2) = 0.2073;
    tensor(2,1,2) = 0.7641;
    tensor(2,2,2) = 0.9924;
    tensor(2,3,2) = 0.8752;
    tensor(3,1,2) = 0.6708;
    tensor(3,2,2) = 0.8296;
    tensor(3,3,2) = 0.1325;
    tensor(1,1,3) = 0.3871;
    tensor(1,2,3) = 0.0769;
    tensor(1,3,3) = 0.3151;
    tensor(2,1,3) = 0.1355;
    tensor(2,2,3) = 0.7727;
    tensor(2,3,3) = 0.4089;
    tensor(3,1,3) = 0.9715;
    tensor(3,2,3) = 0.7726;
    tensor(3,3,3) = 0.5526;
    [bstrk1_tensor,runtimesdp,runinfo] = nsymtensor1aprx(tensor,tdim);