Datasets: dense, incomplete, sparse and structured¶

Dense tensors¶

A dense (or full) tensor is simply a MATLAB array, e.g., A = randn(10,10) or T = randn(5,5,5). MATLAB supports a few basic operations on tensors, for example:

T = randn(10,20,30);
S = randn(10,20,30);
V = T + S;            % Elementwise addition
W = T.*S;             % Elementwise multiplication

Incomplete tensors¶

An incomplete tensor is a dataset in which some (or most) of the entries are unknown. An incomplete tensor is efficiently represented in Tensorlab by a structure that contains the necessary information. The efficient representation of an incomplete tensor of which the unknown entries are padded with NaN can be obtained by using the format command fmt. In the following example, a MATLAB array of size \(9\times 9 \times 9\) with only three known elements is replaced by its efficient representation:

T = NaN(9,9,9);
T(1,2,3) = -1;
T(4,5,6) = -2;
T(7,8,9) = -3;
T = fmt(T)

T =
    matrix: [9x81 double]
      size: [9 9 9]
       ind: [3x1 int64]
       val: [3x1 double]
incomplete: 1
    sparse: 0
       sub: {[3x1 int32]  [3x1 int32]  [3x1 int32]}

Note that if there are no entries equal to NaN, then fmt(T) returns T itself. On the other hand, from the set of known entries, their positions, the tensor’s size and an incomplete flag, the efficient representation can be constructed directly such as in the following example:

T = struct;
T.val = [-1 -2 -3];              % The known elements
T.sub = [1 2 3; 4 5 6; 7 8 9];   % Their positions
T.size = [9 9 9];                % The size of the tensor
T.incomplete = true;             % The incomplete flag

T = fmt(T);                      % Complete the representation

Note that for obtaining a valid efficient representation, fmt needs to be used such that additional fields needed for computational purposes are inserted, e.g., T.matrix. Alternatively, the user may supply linear indices with T.ind instead of subindices with T.sub. To convert linear indices to subindices and vice versa, see the MATLAB functions ind2sub and sub2ind, respectively.

Given the representation of an incomplete tensor, the MATLAB array with NaN values for the unknown entries can be obtained using the command ful:

T = struct;
T.val = [1 2 3];
T.ind = [1 5 9];
T.size = [3 3];
T.incomplete = true;
T = fmt(T);
S = ful(T)

S =
   1   NaN   NaN
 NaN     2   NaN
 NaN   NaN     3

Sparse tensors¶

A sparse tensor is a dataset in which most of the entries are zero, e.g., a large diagonal matrix. Tensorlab supports efficient representations of sparse tensors of which at least 95% of the entries are zero. The efficient representation can be obtained using the format command fmt:

T = zeros(5,5,5);
T(1:31:end) = 1;
T = fmt(T)

T =
    matrix: [5x25 double]
      size: [5 5 5]
       ind: [5x1 int64]
       val: [5x1 double]
incomplete: 0
    sparse: 1
       sub: {[5x1 int32]  [5x1 int32]  [5x1 int32]}

If less than 95% of the entries are zero, then fmt returns T itself. To construct an efficient representation of a sparse tensor directly, define a structure containing the tensor’s nonzero elements in the same way as for incomplete tensors and set the sparse flag. Afterwards, fmt should be called to insert additional necessary fields for computational purposes and to obtain a valid efficient representation:

T.val = [-1 -2 -3];              % The non-zero elements
T.sub = [1 2 3; 4 5 6; 7 8 9];   % Their positions
T.size = [9 9 9];                % The size of the tensor
T.sparse = true;                 % The sparse flag

T = fmt(T);

The ful command can be used to convert the representation to the corresponding MATLAB array:

T = struct;
T.val = [1 2 3];
T.ind = [1 5 9];
T.size = [3 3];
T.sparse  = true;
T = fmt(T);
S = ful(T)

S =
  1     0     0
  0     2     0
  0     0     3

Structured tensors¶

Tensorlab 3.0 introduces additional support for structured tensors. Two groups of structured tensors can be handled: structured tensors resulting from the tensorization of data and tensors that are given under the form of an explicit factorization.

H = hankelize(1:7,'full',false);

H =
       type: 'hankel'
        val: [7x1 double]
        dim: 1
      order: 2
        ind: 4
 ispermuted: 0
repermorder: [1 2]
       size: [4 4]
    subsize: [1x1 struct]

H = ful(H)

H =
 1     2     3     4
 2     3     4     5
 3     4     5     6
 4     5     6     7

Useful commands for efficient representations¶

Besides generating the entire dense tensor given an efficient representation of an incomplete, sparse or structured tensor, the command ful provides an additional feature allowing the user to pass indices for specific elements of the tensor to be calculated or extracted. Given an efficient representation of the following Hankel matrix \(\mat{H}\):

the following returns the diagonal of \(\mat{H}\) using linear indices:

ful(H,[1 6 11 16])

ans =
  1     3     5     7

Alternatively, subindexing can be used to extract fibers or slices. For example:

ful(H,2,':')
ful(H,2:3,':')

ans =
  2     3     4     5

ans =
  2     3     4     5
  3     4     5     6

Further, getstructure returns the type of efficient representation. The functions getorder and getsize return the order and the size of the tensor. Given a dense tensor, the function detectstructure will try to detect structure present in the dataset. Currently, only symmetry and Hankel structure is detected. If the detected structure corresponds to a supported efficient representation in Tensorlab, the representation is also returned. Finally, the function isvalidtensor determines if the given efficient representation is a valid tensor representation. In the following example, the tensor representation is not valid as the field size is not present:

T = struct;
T.val = [1 2 3];
T.ind = [1 2 3];
T.incomplete = true;
isvalidtensor(T)

Matricization and tensorization¶

A dense tensor T can be flattened or unfolded into a matrix with M = tens2mat(T,mode_row,mode_col). Let size_tens = size(T), then the resulting matrix M is of size prod(size_tens(mode_row)) by prod(size_tens(mode_col)). For example,

T = randn(3,5,7,9);
M = tens2mat(T,[1 3],[4 2]);
size(M)

outputs [21 45]. In tens2mat, a given column (row) of M is generated by fixing the indices corresponding to mode_col (mode_row) and then looping over the remaining indices in the order mode_row (mode_col). To transform a matricized tensor M back into its original size size_tens, use mat2tens(M,size_tens,mode_row,mode_col).

The most common use case is to matricize a tensor by placing its mode-\(n\) vectors as columns in a matrix, also called a mode-\(n\) matricization. This can be achieved by

T = randn(3,5,7);
n = 2;
M = tens2mat(T,n);

where the optional argument mode_col is implicitly equal to [1:n-1 n+1:ndims(T)].

The commands tens2mat and mat2tens currently only support dense tensors. For other matricization and detensorization methods, we refer to Tensorization techniques.

Tensor-matrix product¶

In a mode-\(n\) tensor-matrix product, the tensor’s mode-\(n\) fibers are premultiplied by a given matrix. In other words, U*tens2mat(T,n) is a mode-\(n\) matricization of the mode-\(n\) tensor-matrix product \(\texttt{T} \tmprod_n \texttt{U}\). The function tmprod(T,U,mode) computes the tensor-matrix product \(\texttt{T} \tmprod_{\texttt{mode(1)}} \texttt{U{1}} \tmprod_{\texttt{mode(2)}} \texttt{U{2}}\, \cdots\). For example,

T = randn(3,5,7);
U = {randn(11,3),randn(13,5),randn(15,7)};
S = tmprod(T,U,1:3);
size(S)

outputs [11 13 15]. To compute a single tensor-matrix product, a cell array is not necessary. The following is an example of a single mode-2 tensor-matrix product:

T = randn(3,5,7);
S = tmprod(T,randn(13,5),2);

Note that tmprod currently only supports dense tensors.

The contract(T,v,n) command computes contractions between the tensor T with the vectors v in the modes given by n.

Kronecker and Khatri–Rao product¶

Tensorlab includes a fast implementation of the Kronecker product \(A \otimes B\) with the function kron(A,B), which overrides MATLAB’s built-in implementation. Let \(A\) and \(B\) be matrices of size \(I\times J\) and \(K\times L\), respectively, then the Kronecker product of \(A\) and \(B\) is the \(IK \times JL\) matrix

More generally, kron(A,B,C,...) and kron(U) compute the Kronecker products \(((\texttt{A} \otimes \texttt{B}) \otimes \texttt{C}) \otimes \cdots\) and \(((\texttt{U\{1\}} \otimes \texttt{U\{2\}}) \otimes \texttt{U\{3\}}) \otimes \cdots\), respectively.

The Khatri–Rao product \(A\odot B\) can be computed by kr(A,B). Let \(A\) and \(B\) both be matrices with \(N\) columns, then the Khatri–Rao product of \(A\) and \(B\) is the column-wise Kronecker product

More generally, kr(A,B,C,...) and kr(U) compute the Khatri–Rao products \(((\texttt{A} \odot \texttt{B}) \odot \texttt{C}) \odot \cdots\) and \(((\texttt{U\{1\}} \odot \texttt{U\{2\}}) \odot \texttt{U\{3\}}) \odot \cdots\), respectively.

Note that kr and kron currently only support dense tensors.

Matricized-tensor times Kronecker and Khatri–Rao product¶

tens2mat(T,n)*conj(kron(U([end:-1:n+1 n-1:-1:1])))

T(:).'*conj(kron(U(end:-1:1)))

tens2mat(T,n)*conj(kron(U([end:-1:n+1 n-1:-1:1])))

T(:).'*conj(kr(U(end:-1:1)))

Frobenius norm¶

The Frobenius norm of a tensor is the square root of the sum of square moduli of its (known) elements. Given a tensor T, its Frobenius norm can be computed with frob(T). If the tensor is dense, this is equivalent with norm(T(:)), i.e., the two-norm of the vectorized tensor. The squared Frobenius norm can be computed with frob(T,'squared').

The command supports dense, sparse, incomplete and structured tensors. For structured tensors, the norm is computed in a very efficient way. Consider a third-order Hankel tensor \(H\) of size \(334\times 334\times 334\), constructed using the hankelize method (see Tensorization techniques). We compare the time needed for the computation of the Frobenius norm given the dense tensor H with the time needed for the computation given its efficient representation Heff:

[H,Heff] = hankelize(linspace(0,1,1000),'order',3);
tic; disp(frob(H)); toc;        % Using the dense tensor H
tic; disp(frob(Heff)); toc;     % Using the efficient representation of H

3.2181e+03
Elapsed time is 0.026401 seconds.

3.2181e+03
Elapsed time is 0.000832 seconds.

Inner and outer product¶

Given two tensors T1 and T2, the command inprod(T1,T2) computes the inner product T2(:)'*T1(:). The result is a scalar. The command supports dense, sparse, incomplete and structured tensors for both T1 and T2.

The command outprod(T1,T2) computes the outer product of two tensors T1 and T2. If T1 has size \(I_1\times \cdots \times I_M\) and T2 has size \(J_1\times \cdots \times J_N\), then the resulting tensor has size \(I_1\times \cdots \times I_M \times J_1 \times \cdots \times J_N\). If T1, respectively T2, is a row or column vector, the singleton dimension is discarded. Currently, the command outprod supports only dense tensors.

Noisy versions of tensors and representations¶

The noisy command can be used to create a noisy version of dense, incomplete, sparse and structured tensors given a signal-to-noise ratio. For example,

T = randn(10,10,10);
SNR = 20;
That = noisy(U,SNR);
frob(That-T)/frob(T)

ans =
  0.1000

Note that for efficient representations of incomplete, sparse and structured tensors, noise is added to the variables of the representation rather than to the full tensor. For example, given the efficient representation Heff of a \(3\times 3\) Hankel matrix H, a Hankel matrix is returned with constant perturbations along the anti-diagonals:

[H,Heff] = hankelize(1:5);
SNR = 20;
Heffhat = noisy(Heff,SNR);
H
ful(Heffhat)

H =
  1     2     3
  2     3     4
  3     4     5


 ans =
  1.2691    2.2507    3.3571
  2.2507    3.3571    3.5825
  3.3571    3.5825    4.9737

The noisy command can be used for cell arrays as well. Noise is then added on every entry of the cell. For example:

U = {randn(10,2),randn(15,2),randn(20,2)};
SNR = 20;
Uhat = noisy(U,SNR);

creates a cell array U and a noisy version of that cell array called Uhat. This is equivalent to adding noise to the efficient representation of factorized tensors as discussed in the previous paragraph.