Cross approximation in the TT format
Using the torchtt.TT constructor, a TT decomposition of a given tensor can be obtained. However, in the cases where the entries of the tensor are computed using a given function, building full tensors becomes unfeasible. It is possible to construct a TT decomposition using only a part of the entries of the full tensor. This is called the cross approximation method.
Imports:
[1]:
import torch as tn
try:
import torchtt as tntt
except:
print('Installing torchTT...')
%pip install git+https://github.com/ion-g-ion/torchTT
import torchtt as tntt
/home/yonnss/Repos/torchTT/.venv/lib/python3.12/site-packages/torchtt/_tt_base.py:71: SyntaxWarning: invalid escape sequence '\`'
"""
Cross interpolation of a tensor in TT format
We want to approximate the tensor \(\mathsf{x}_{i_1...i_d}=\frac{1}{2+i_1+\cdots+i_d}\). Since the passed indices are integers of type torch.int64, casting is used.
[2]:
func1 = lambda I: 1/(2+tn.sum(I+1,1).to(dtype=tn.float64))
Call the torchtt.interpolate.dmrg_cross() method.
[3]:
N = [20]*4
x = tntt.interpolate.dmrg_cross(func1, N, eps = 1e-7)
Compute the full tensor and compare to the reference.
[4]:
Is = tntt.meshgrid([tn.arange(0,n,dtype=tn.float64) for n in N])
x_ref = 1/(2+Is[0].full()+Is[1].full()+Is[2].full()+Is[3].full()+4)
print('Relative error ',tn.linalg.norm(x.full()-x_ref)/tn.linalg.norm(x_ref))
Relative error tensor(5.5025e-09, dtype=torch.float64)
We consider the case \(d=10\), \(n_i=32\). the full tensor would contain \(32^{10}\) entries. The total number of functions calls is in this case 25000000 compared to \(32^{10}\) of the total number of entries.
[5]:
N = [32]*10
x = tntt.interpolate.dmrg_cross(func1, N, eps = 1e-10, verbose=True)
Sweep 1:
LR supercore 1,2
number evaluations 2048
rank updated 2 -> 8, local error 8.011303e+05
LR supercore 2,3
number evaluations 16384
rank updated 2 -> 8, local error 1.107770e+00
LR supercore 3,4
number evaluations 16384
rank updated 2 -> 9, local error 1.061156e+00
LR supercore 4,5
number evaluations 18432
rank updated 2 -> 9, local error 1.158413e+00
LR supercore 5,6
number evaluations 18432
rank updated 2 -> 10, local error 1.083112e+00
LR supercore 6,7
number evaluations 20480
rank updated 2 -> 11, local error 1.142525e+00
LR supercore 7,8
number evaluations 22528
rank updated 2 -> 11, local error 1.108836e+00
LR supercore 8,9
number evaluations 22528
rank updated 2 -> 12, local error 1.093962e+00
LR supercore 9,10
number evaluations 12288
rank updated 2 -> 12, local error 1.195789e+00
RL supercore 9,10
number evaluations 12288
rank updated 12 -> 12, local error 1.933094e-12
RL supercore 8,9
number evaluations 135168
rank updated 12 -> 14, local error 4.387990e-08
RL supercore 7,8
number evaluations 157696
rank updated 11 -> 14, local error 8.947160e-07
RL supercore 6,7
number evaluations 143360
rank updated 11 -> 15, local error 2.988662e-06
RL supercore 5,6
number evaluations 138240
rank updated 10 -> 15, local error 3.359481e-05
RL supercore 4,5
number evaluations 138240
rank updated 9 -> 15, local error 5.643826e-04
RL supercore 3,4
number evaluations 122880
rank updated 9 -> 14, local error 2.966111e-04
RL supercore 2,3
number evaluations 114688
rank updated 8 -> 14, local error 4.592120e-04
RL supercore 1,2
number evaluations 14336
rank updated 8 -> 13, local error 1.287281e-04
Max error 801130
Sweep 2:
LR supercore 1,2
number evaluations 14336
rank updated 13 -> 13, local error 2.561590e-13
LR supercore 2,3
number evaluations 186368
rank updated 14 -> 14, local error 3.362729e-12
LR supercore 3,4
number evaluations 215040
rank updated 14 -> 14, local error 6.297698e-12
LR supercore 4,5
number evaluations 215040
rank updated 15 -> 14, local error 4.181148e-12
LR supercore 5,6
number evaluations 215040
rank updated 15 -> 14, local error 1.071323e-11
LR supercore 6,7
number evaluations 200704
rank updated 15 -> 14, local error 2.148397e-11
LR supercore 7,8
number evaluations 200704
rank updated 14 -> 13, local error 1.074529e-11
LR supercore 8,9
number evaluations 159744
rank updated 14 -> 13, local error 6.931534e-11
LR supercore 9,10
number evaluations 13312
rank updated 12 -> 11, local error 4.229439e-11
RL supercore 9,10
number evaluations 13312
rank updated 11 -> 11, local error 1.028534e-11
RL supercore 8,9
number evaluations 146432
rank updated 13 -> 13, local error 4.974640e-11
RL supercore 7,8
number evaluations 186368
rank updated 13 -> 13, local error 2.329756e-10
RL supercore 6,7
number evaluations 186368
rank updated 14 -> 13, local error 1.446916e-11
RL supercore 5,6
number evaluations 186368
rank updated 14 -> 14, local error 1.628535e-11
RL supercore 4,5
number evaluations 200704
rank updated 14 -> 14, local error 1.384431e-11
RL supercore 3,4
number evaluations 200704
rank updated 14 -> 14, local error 1.549829e-11
RL supercore 2,3
number evaluations 186368
rank updated 14 -> 14, local error 2.468872e-12
RL supercore 1,2
number evaluations 14336
rank updated 13 -> 13, local error 1.240978e-12
Max error 2.32976e-10
Sweep 3:
LR supercore 1,2
number evaluations 14336
rank updated 13 -> 13, local error 2.101737e-13
LR supercore 2,3
number evaluations 186368
rank updated 14 -> 14, local error 1.360479e-12
LR supercore 3,4
number evaluations 200704
rank updated 14 -> 14, local error 5.534922e-12
LR supercore 4,5
number evaluations 200704
rank updated 14 -> 14, local error 6.608827e-12
LR supercore 5,6
number evaluations 186368
rank updated 14 -> 14, local error 8.716560e-12
LR supercore 6,7
number evaluations 186368
rank updated 13 -> 13, local error 1.319055e-11
LR supercore 7,8
number evaluations 173056
rank updated 13 -> 13, local error 7.579591e-11
LR supercore 8,9
number evaluations 146432
rank updated 13 -> 12, local error 6.835033e-11
LR supercore 9,10
number evaluations 12288
rank updated 11 -> 12, local error 3.081456e-10
RL supercore 9,10
number evaluations 12288
rank updated 12 -> 12, local error 5.072243e-13
RL supercore 8,9
number evaluations 159744
rank updated 12 -> 12, local error 2.535733e-10
RL supercore 7,8
number evaluations 159744
rank updated 13 -> 13, local error 1.439999e-10
RL supercore 6,7
number evaluations 186368
rank updated 13 -> 14, local error 1.601744e-10
RL supercore 5,6
number evaluations 200704
rank updated 14 -> 14, local error 1.542714e-11
RL supercore 4,5
number evaluations 200704
rank updated 14 -> 14, local error 1.824728e-11
RL supercore 3,4
number evaluations 200704
rank updated 14 -> 14, local error 7.452563e-12
RL supercore 2,3
number evaluations 186368
rank updated 14 -> 14, local error 4.158401e-12
RL supercore 1,2
number evaluations 14336
rank updated 13 -> 12, local error 8.907987e-13
Max error 3.08146e-10
Sweep 4:
LR supercore 1,2
number evaluations 14336
rank updated 12 -> 12, local error 2.173909e-12
LR supercore 2,3
number evaluations 172032
rank updated 14 -> 14, local error 1.474032e-11
LR supercore 3,4
number evaluations 200704
rank updated 14 -> 14, local error 4.456454e-12
LR supercore 4,5
number evaluations 200704
rank updated 14 -> 14, local error 4.375434e-12
LR supercore 5,6
number evaluations 200704
rank updated 14 -> 14, local error 1.135623e-11
LR supercore 6,7
number evaluations 186368
rank updated 14 -> 14, local error 1.391331e-11
LR supercore 7,8
number evaluations 172032
rank updated 13 -> 13, local error 3.589758e-11
LR supercore 8,9
number evaluations 159744
rank updated 12 -> 12, local error 6.663063e-11
LR supercore 9,10
number evaluations 12288
rank updated 12 -> 12, local error 3.837426e-10
RL supercore 9,10
number evaluations 12288
rank updated 12 -> 12, local error 5.769756e-13
RL supercore 8,9
number evaluations 159744
rank updated 12 -> 12, local error 3.728510e-10
RL supercore 7,8
number evaluations 172032
rank updated 13 -> 13, local error 1.092365e-10
RL supercore 6,7
number evaluations 186368
rank updated 14 -> 14, local error 3.066868e-11
RL supercore 5,6
number evaluations 200704
rank updated 14 -> 14, local error 1.955186e-11
RL supercore 4,5
number evaluations 200704
rank updated 14 -> 14, local error 3.380903e-11
RL supercore 3,4
number evaluations 200704
rank updated 14 -> 14, local error 3.820963e-12
RL supercore 2,3
number evaluations 172032
rank updated 14 -> 14, local error 4.414198e-12
RL supercore 1,2
number evaluations 14336
rank updated 12 -> 13, local error 5.405301e-12
Max error 3.83743e-10
Sweep 5:
LR supercore 1,2
number evaluations 14336
rank updated 13 -> 13, local error 1.728230e-13
LR supercore 2,3
number evaluations 186368
rank updated 14 -> 14, local error 3.515868e-12
LR supercore 3,4
number evaluations 200704
rank updated 14 -> 14, local error 3.604524e-12
LR supercore 4,5
number evaluations 200704
rank updated 14 -> 14, local error 1.061518e-11
LR supercore 5,6
number evaluations 200704
rank updated 14 -> 14, local error 1.987601e-11
LR supercore 6,7
number evaluations 186368
rank updated 14 -> 14, local error 1.442279e-11
LR supercore 7,8
number evaluations 172032
rank updated 13 -> 13, local error 1.742675e-11
LR supercore 8,9
number evaluations 159744
rank updated 12 -> 12, local error 6.784308e-11
LR supercore 9,10
number evaluations 12288
rank updated 12 -> 12, local error 3.487840e-10
RL supercore 9,10
number evaluations 12288
rank updated 12 -> 12, local error 5.376883e-13
RL supercore 8,9
number evaluations 159744
rank updated 12 -> 12, local error 3.758679e-10
RL supercore 7,8
number evaluations 172032
rank updated 13 -> 13, local error 7.241544e-11
RL supercore 6,7
number evaluations 186368
rank updated 14 -> 14, local error 2.322491e-11
RL supercore 5,6
number evaluations 200704
rank updated 14 -> 14, local error 1.311894e-11
RL supercore 4,5
number evaluations 200704
rank updated 14 -> 14, local error 1.737606e-11
RL supercore 3,4
number evaluations 200704
rank updated 14 -> 14, local error 8.616969e-12
RL supercore 2,3
number evaluations 186368
rank updated 14 -> 14, local error 2.838546e-12
RL supercore 1,2
number evaluations 14336
rank updated 13 -> 13, local error 1.375318e-12
Max error 3.75868e-10
Sweep 6:
LR supercore 1,2
number evaluations 14336
rank updated 13 -> 13, local error 2.265714e-13
LR supercore 2,3
number evaluations 186368
rank updated 14 -> 14, local error 1.537291e-12
LR supercore 3,4
number evaluations 200704
rank updated 14 -> 14, local error 3.921249e-12
LR supercore 4,5
number evaluations 200704
rank updated 14 -> 14, local error 5.628661e-12
LR supercore 5,6
number evaluations 200704
rank updated 14 -> 14, local error 1.496981e-11
LR supercore 6,7
number evaluations 186368
rank updated 14 -> 14, local error 1.664877e-11
LR supercore 7,8
number evaluations 172032
rank updated 13 -> 13, local error 8.974218e-12
LR supercore 8,9
number evaluations 159744
rank updated 12 -> 13, local error 1.100912e-10
LR supercore 9,10
number evaluations 13312
rank updated 12 -> 11, local error 3.186311e-11
RL supercore 9,10
number evaluations 13312
rank updated 11 -> 11, local error 9.420963e-12
RL supercore 8,9
number evaluations 146432
rank updated 13 -> 13, local error 3.144098e-11
RL supercore 7,8
number evaluations 186368
rank updated 13 -> 13, local error 1.206896e-10
RL supercore 6,7
number evaluations 186368
rank updated 14 -> 13, local error 1.812926e-11
RL supercore 5,6
number evaluations 186368
rank updated 14 -> 14, local error 3.370399e-11
RL supercore 4,5
number evaluations 200704
rank updated 14 -> 14, local error 2.647010e-11
RL supercore 3,4
number evaluations 200704
rank updated 14 -> 14, local error 7.142087e-12
RL supercore 2,3
number evaluations 186368
rank updated 14 -> 14, local error 7.700651e-12
RL supercore 1,2
number evaluations 14336
rank updated 13 -> 12, local error 6.074188e-13
Max error 1.2069e-10
Sweep 7:
LR supercore 1,2
number evaluations 14336
rank updated 12 -> 12, local error 2.029093e-12
LR supercore 2,3
number evaluations 172032
rank updated 14 -> 14, local error 1.601786e-11
LR supercore 3,4
number evaluations 200704
rank updated 14 -> 14, local error 3.916745e-12
LR supercore 4,5
number evaluations 200704
rank updated 14 -> 14, local error 7.994614e-12
LR supercore 5,6
number evaluations 186368
rank updated 14 -> 14, local error 1.615342e-11
LR supercore 6,7
number evaluations 186368
rank updated 13 -> 13, local error 3.012795e-11
LR supercore 7,8
number evaluations 173056
rank updated 13 -> 13, local error 9.954921e-11
LR supercore 8,9
number evaluations 146432
rank updated 13 -> 13, local error 1.045172e-10
LR supercore 9,10
number evaluations 13312
rank updated 11 -> 11, local error 4.186615e-11
RL supercore 9,10
number evaluations 13312
rank updated 11 -> 11, local error 1.116858e-11
RL supercore 8,9
number evaluations 146432
rank updated 13 -> 14, local error 4.723477e-11
RL supercore 7,8
number evaluations 186368
rank updated 13 -> 13, local error 1.255822e-10
RL supercore 6,7
number evaluations 186368
rank updated 13 -> 14, local error 1.276743e-10
RL supercore 5,6
number evaluations 200704
rank updated 14 -> 14, local error 4.778793e-11
RL supercore 4,5
number evaluations 200704
rank updated 14 -> 14, local error 1.211883e-11
RL supercore 3,4
number evaluations 200704
rank updated 14 -> 14, local error 7.765330e-12
RL supercore 2,3
number evaluations 172032
rank updated 14 -> 14, local error 3.652481e-12
RL supercore 1,2
number evaluations 14336
rank updated 12 -> 13, local error 9.569811e-12
Max error 1.27674e-10
Sweep 8:
LR supercore 1,2
number evaluations 14336
rank updated 13 -> 13, local error 2.665059e-13
LR supercore 2,3
number evaluations 186368
rank updated 14 -> 14, local error 1.598184e-12
LR supercore 3,4
number evaluations 200704
rank updated 14 -> 14, local error 2.921344e-12
LR supercore 4,5
number evaluations 200704
rank updated 14 -> 14, local error 6.408126e-12
LR supercore 5,6
number evaluations 200704
rank updated 14 -> 14, local error 1.242468e-11
LR supercore 6,7
number evaluations 186368
rank updated 14 -> 14, local error 1.536151e-11
LR supercore 7,8
number evaluations 200704
rank updated 13 -> 13, local error 3.195804e-11
LR supercore 8,9
number evaluations 146432
rank updated 14 -> 14, local error 1.133186e-10
LR supercore 9,10
number evaluations 14336
rank updated 11 -> 11, local error 1.257866e-11
RL supercore 9,10
number evaluations 14336
rank updated 11 -> 11, local error 5.861977e-12
RL supercore 8,9
number evaluations 146432
rank updated 14 -> 13, local error 4.484371e-12
RL supercore 7,8
number evaluations 186368
rank updated 13 -> 13, local error 1.857574e-10
RL supercore 6,7
number evaluations 186368
rank updated 14 -> 14, local error 3.070013e-11
RL supercore 5,6
number evaluations 200704
rank updated 14 -> 14, local error 1.855032e-11
RL supercore 4,5
number evaluations 200704
rank updated 14 -> 14, local error 2.821237e-11
RL supercore 3,4
number evaluations 200704
rank updated 14 -> 14, local error 1.641763e-11
RL supercore 2,3
number evaluations 186368
rank updated 14 -> 14, local error 4.237183e-12
RL supercore 1,2
number evaluations 14336
rank updated 13 -> 13, local error 1.624154e-12
Max error 1.85757e-10
Sweep 9:
LR supercore 1,2
number evaluations 14336
rank updated 13 -> 13, local error 2.453447e-13
LR supercore 2,3
number evaluations 186368
rank updated 14 -> 14, local error 1.844952e-12
LR supercore 3,4
number evaluations 200704
rank updated 14 -> 14, local error 5.687889e-12
LR supercore 4,5
number evaluations 200704
rank updated 14 -> 14, local error 1.391953e-11
LR supercore 5,6
number evaluations 200704
rank updated 14 -> 14, local error 1.888737e-11
LR supercore 6,7
number evaluations 186368
rank updated 14 -> 14, local error 1.828244e-11
LR supercore 7,8
number evaluations 186368
rank updated 13 -> 13, local error 1.902433e-11
LR supercore 8,9
number evaluations 146432
rank updated 13 -> 13, local error 8.896204e-11
LR supercore 9,10
number evaluations 13312
rank updated 11 -> 11, local error 3.340366e-11
RL supercore 9,10
number evaluations 13312
rank updated 11 -> 11, local error 9.831399e-12
RL supercore 8,9
number evaluations 146432
rank updated 13 -> 13, local error 3.408791e-11
RL supercore 7,8
number evaluations 186368
rank updated 13 -> 13, local error 1.122546e-10
RL supercore 6,7
number evaluations 186368
rank updated 14 -> 13, local error 1.768783e-11
RL supercore 5,6
number evaluations 186368
rank updated 14 -> 14, local error 1.906563e-11
RL supercore 4,5
number evaluations 200704
rank updated 14 -> 14, local error 1.711690e-11
RL supercore 3,4
number evaluations 200704
rank updated 14 -> 14, local error 1.460717e-11
RL supercore 2,3
number evaluations 186368
rank updated 14 -> 14, local error 1.525997e-11
RL supercore 1,2
number evaluations 14336
rank updated 13 -> 13, local error 2.157881e-12
Max error 1.12255e-10
Sweep 10:
LR supercore 1,2
number evaluations 14336
rank updated 13 -> 13, local error 3.002163e-13
LR supercore 2,3
number evaluations 186368
rank updated 14 -> 14, local error 2.918720e-12
LR supercore 3,4
number evaluations 200704
rank updated 14 -> 14, local error 6.844514e-12
LR supercore 4,5
number evaluations 200704
rank updated 14 -> 14, local error 3.902040e-12
LR supercore 5,6
number evaluations 186368
rank updated 14 -> 14, local error 1.749885e-11
LR supercore 6,7
number evaluations 186368
rank updated 13 -> 13, local error 1.407230e-11
LR supercore 7,8
number evaluations 173056
rank updated 13 -> 13, local error 1.035718e-10
LR supercore 8,9
number evaluations 146432
rank updated 13 -> 13, local error 1.362737e-10
LR supercore 9,10
number evaluations 13312
rank updated 11 -> 11, local error 3.890318e-11
RL supercore 9,10
number evaluations 13312
rank updated 11 -> 11, local error 1.040580e-11
RL supercore 8,9
number evaluations 146432
rank updated 13 -> 13, local error 3.631073e-11
RL supercore 7,8
number evaluations 173056
rank updated 13 -> 14, local error 5.391511e-10
RL supercore 6,7
number evaluations 200704
rank updated 13 -> 14, local error 1.459877e-10
RL supercore 5,6
number evaluations 200704
rank updated 14 -> 14, local error 1.875476e-11
RL supercore 4,5
number evaluations 200704
rank updated 14 -> 14, local error 2.952445e-11
RL supercore 3,4
number evaluations 200704
rank updated 14 -> 14, local error 1.782633e-11
RL supercore 2,3
number evaluations 186368
rank updated 14 -> 14, local error 3.183040e-12
RL supercore 1,2
number evaluations 14336
rank updated 13 -> 13, local error 1.580564e-12
Max error 5.39151e-10
number of function calls 25056256
The adaptive cross method used only a fraction of function calls from the original tensor. Check some entries (full tensor cannot be computed this time) and show the rank and the storage requirements.
[6]:
print(x[1,2,3,4,5,6,7,8,9,11], ' reference ', func1(tn.tensor([[1,2,3,4,5,6,7,8,9,11]])))
print(x[12,23,17,25,30,0,7,8,9,11], ' reference ', func1(tn.tensor([[12,23,17,25,30,0,7,8,9,11]])))
print(x)
tensor(0.0147, dtype=torch.float64) reference tensor([0.0147], dtype=torch.float64)
tensor(0.0065, dtype=torch.float64) reference tensor([0.0065], dtype=torch.float64)
TT with sizes and ranks:
N = [32, 32, 32, 32, 32, 32, 32, 32, 32, 32]
R = [1, 13, 14, 14, 14, 14, 14, 14, 13, 11, 1]
Device: cpu, dtype: torch.float64
#entries 48352 compression 4.2945202949340455e-11
Element wise application of an univariate function on a TT tensor.
Let \(f:\mathbb{R}\rightarrow\mathbb{R}\) be a function and \(\mathsf{x}\in\mathbb{R}^{N_1\times\cdots\times N_d}\) be a tensor with a known TT approximation. The goal is to determine the TT approximation of \(\mathsf{y}_{i_1...i_d}=f(\mathsf{x}_{i_1...i_d})\) within a prescribed relative accuracy \(\epsilon\) (passed as argument). In this case the function is torchtt.interpoalte.function_interpolate() and takes as arguments a function handle, the tensor \(\mathsf{x}\),
the accuracy epsilon, a initial tensor (starting point), number of sweeps (nswp) and the size of the rank enrichment (kick). Further arguments are the dtype of the result and the verbose flag.
The function handle as argument gets as arguments torch vectors and has to return torch vectors of the same size.
The following example computes the elemntwise natural logarithm of a tensor. The relative error of the result is also reported.
[7]:
x = tntt.TT(x_ref)
func = lambda t: tn.log(t)
y = tntt.interpolate.function_interpolate(func, x, 1e-9)
print('Relative error ',tn.linalg.norm(y.full()-func(x_ref))/tn.linalg.norm(func(x_ref)))
Relative error tensor(2.6127e-11, dtype=torch.float64)
Element wise application of an multivariate function on a TT tensor.
Let \(f:\mathbb{R}\rightarrow\mathbb{R}\) be a function and \(\mathsf{x}^{(1)},...,\mathsf{x}^{(d)}\in\mathbb{R}^{N_1\times\cdots\times N_d}\) be tensors with a known TT approximation. The goal is to determine the TT approximation of \(\mathsf{y}_{i_1...i_d}=f(\mathsf{x}_{i_1...i_d}^{(1)},...,\mathsf{x}^{(d)}_{i_1...i_d})\) within a prescribed relative accuracy \(\epsilon\) (passed as argument). The function is the same as in the previous case
tochtt.interpoalte.function_interpolate(), but the second argument in this case is a list of torchtt.TT tensors. The function handle takes as argument a \(M\times d\) torch.tensor and every of the \(M\) lines corresponds to an evaluation of the function \(f\) at a certain tensor entry. The function handle returns a torch tensor of length \(M\).
The following example computes the same tensor as in the previous case, but with the tochtt.interpoalte.function_interpolate() method.
[8]:
z = tntt.interpolate.function_interpolate(func1, Is, callback=lambda tt, sweep, error: print(f'Sweep {sweep}, Relative error {error}, rank {tt.R}'), eps=1e-9)
print('Relative error ',tn.linalg.norm(z.full()-x_ref)/tn.linalg.norm(x_ref))
Sweep 0, Relative error 447.539677001294, rank [1, 11, 12, 11, 1]
Sweep 1, Relative error 4.826682030377584e-11, rank [1, 12, 12, 11, 1]
Relative error tensor(3.1469e-11, dtype=torch.float64)