Feasibility of singular values in the Tensor Train format
A 4th-order example
We will go through one example of feasibility for a th-order tensor using different algorithms. Let be as follows:
d = 4;
sigma = cell(1,5);
sigma{1} = sqrt(13);
sigma{2} = [3,2];
sigma{3} = [sqrt(10),sqrt(2),1];
sigma{4} = [2,sqrt(3),sqrt(2.5),sqrt(2),sqrt(1.5)];
sigma{5} = sqrt(13);
sigma{:}
1. Using linear programming and hives:
For each pair we can use the linear programming algorithm linear_programming_check construct hives and determine the minimal required more size n such that the pair is feasible for that value.
help linear_programming_check
Be aware that indices must be shifted sigma{mu+1}.
For and however, there is nothing to do, since we know that the pair is feasible for and is feasible for and (and no less) just by looking at the respective ranks.
n = [2,0,0,5];
The plots and output are nicer if the code is used outside of a live skript:
close all
drawoptions = struct;
drawoptions.compact = 0;
drawoptions.single = 0;
n(2) = linear_programming_check(sigma{2},sigma{3},drawoptions);
drawoptions.single = 1;
n(3) = linear_programming_check(sigma{3},sigma{4},drawoptions);
Thereby we know that σ is feasible for and no less (except if instabilities should have corrupted our results, which is not to be expected for such small examples).
n
2. Using the alternating iteration
For each pair we may also use the second algorithm and enforce these singular values iteratively to actually construct a representation. In order to use alternating_core_generation we need to specify a suspected .
help alternating_core_generation
Again, the output is nicer if used outside of a live skript.
G = cell(1,d);
G{1} = alternating_core_generation(2,sigma{1},sigma{2});
G{2} = alternating_core_generation(2,sigma{2},sigma{3});
alternating_core_generation(3,sigma{3},sigma{4}); % this will fail
G{3} = alternating_core_generation(4,sigma{3},sigma{4});
G{4} = alternating_core_generation(5,sigma{4},sigma{5});
The cell G now contains a representation of a tensor which has singular values σ. Additionally, G is the standard representation of A. Without previously finding n, we can also use construct_tensor_with_sv to find n and construct all cores in G in parallel.
help construct_tensor_with_sv
We may specify a minimal mode size to start from. We choose here. The first call may require much more time since Matlab needs to connect to the workers in order to proceed with the parfor loop.
construct_tensor_with_sv([1,1,1,1],sigma);
In this case, the alternating iteration converges in all cases to the desired result. Note that none of the calls of alternating_core_generation need to communicate. In this sense, the algorithm runs completely parallel.
3. Diagonal core generation
Based on the Theorem which provides the feasibility of a pair for , the algorithm diagonal_core_generation constructs the required core of length n.
G{1} = diagonal_core_generation(sigma{1},sigma{2});
G{2} = diagonal_core_generation(sigma{2},sigma{3});
If lucky, the required mode size turns out to be less than maximal. The algorithm will notice this (as in the following case), but still output a core of length n. It might however still not be the minimal possible mode size.
G{3} = diagonal_core_generation(sigma{3},sigma{4});
G{3}
G{4} = diagonal_core_generation(sigma{4},sigma{5});
Again, the cell G now contains the standard representation of the tensor which has singular values σ. This time, all cores are rather sparsely populated.