{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Cross-approximation\n",
"\n",
"Often, we would like to build a $N$-dimensional tensor from a **black-box function** $f: \\Omega \\subset \\mathbb{R}^N \\to \\mathbb{R}$, where $\\Omega$ is a tensor product grid. That is, we are free to sample *whatever entries we want* within our domain $\\Omega$, but we cannot afford to sample the entire domain (as it contains an **exponentially large number of points**). One way to build such a tensor is using **cross-approximation** ([I. Oseledets, E. Tyrtyshnikov: \"TT-cross Approximation for Multidimensional Arrays\"](http://www.mat.uniroma2.it/~tvmsscho/papers/Tyrtyshnikov5.pdf)) from well-chosen fibers in the domain.\n",
"\n",
"We support two major use cases of cross-approximation in the TT format.\n",
"\n",
"## Approximating a Function over a Domain\n",
"\n",
"This is the more basic setting. We just need to specify:\n",
"\n",
"- Our function of interest\n",
"- The tensor product domain $\\Omega = u_1 \\otimes \\dots \\otimes u_N$"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Cross-approximation over a 5D domain containing 3.35544e+07 grid points:\n",
"iter: 0 | eps: 9.221e-01 | total time: 0.0110 | largest rank: 1\n",
"iter: 1 | eps: 4.867e-03 | total time: 0.0350 | largest rank: 4\n",
"iter: 2 | eps: 4.295e-06 | total time: 0.0609 | largest rank: 7\n",
"iter: 3 | eps: 8.606e-09 | total time: 0.1027 | largest rank: 10 <- converged: eps < 1e-06\n",
"Did 33984 function evaluations, which took 0.001594s (2.133e+07 evals/s)\n",
"\n",
"5D TT tensor:\n",
"\n",
" 32 32 32 32 32\n",
" | | | | |\n",
" (0) (1) (2) (3) (4)\n",
" / \\ / \\ / \\ / \\ / \\\n",
"1 10 10 10 10 1\n",
"\n"
]
}
],
"source": [
"import tntorch as tn\n",
"import torch\n",
"torch.set_default_dtype(torch.float64)\n",
"\n",
"def function(x, y, z, t, w): # Input arguments are vectors\n",
" return 1 / (x + y + z + t + w) # Hilbert tensor\n",
"\n",
"domain = [torch.arange(1, 33) for n in range(5)]\n",
"t = tn.cross(function=function, domain=domain)\n",
"\n",
"print(t)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Sometimes it's more convenient to work with functions that accept matrices (instead of a list of vectors) as input. We can do this with the `function_arg='matrix'` flag:"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Cross-approximation over a 5D domain containing 3.35544e+07 grid points:\n",
"iter: 0 | eps: 9.355e-01 | total time: 0.0138 | largest rank: 1\n",
"iter: 1 | eps: 4.148e-03 | total time: 0.0341 | largest rank: 4\n",
"iter: 2 | eps: 5.244e-06 | total time: 0.0610 | largest rank: 7\n",
"iter: 3 | eps: 7.581e-09 | total time: 0.0961 | largest rank: 10 <- converged: eps < 1e-06\n",
"Did 33984 function evaluations, which took 0.00437s (7.777e+06 evals/s)\n",
"\n"
]
}
],
"source": [
"def function(Xs): # Matrix (one row per sample, one column per input variable) and return a vector with one result per sample\n",
" return 1/torch.sum(Xs, dim=1)\n",
"\n",
"t = tn.cross(function=function, domain=domain, function_arg='matrix')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Element-wise Operations on Tensors\n",
"\n",
"Here we have one (or several) $N$-dimensional tensors that we want to transform element-wise. For instance, we may want to square each element of our tensor:"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Cross-approximation over a 5D domain containing 3.35544e+07 grid points:\n",
"iter: 0 | eps: 9.539e-01 | total time: 0.0062 | largest rank: 1\n",
"iter: 1 | eps: 2.066e-02 | total time: 0.0174 | largest rank: 4\n",
"iter: 2 | eps: 5.644e-05 | total time: 0.0338 | largest rank: 7\n",
"iter: 3 | eps: 6.255e-08 | total time: 0.0627 | largest rank: 10 <- converged: eps < 1e-06\n",
"Did 33984 function evaluations, which took 0.0005157s (6.59e+07 evals/s)\n",
"\n"
]
}
],
"source": [
"t2 = tn.cross(function=lambda x: x**2, tensors=t)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Just for practice, let's do this now in a slightly different way by passing two tensors:"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Cross-approximation over a 5D domain containing 3.35544e+07 grid points:\n",
"iter: 0 | eps: 9.757e-01 | total time: 0.0081 | largest rank: 1\n",
"iter: 1 | eps: 2.939e-02 | total time: 0.0228 | largest rank: 4\n",
"iter: 2 | eps: 1.086e-04 | total time: 0.0440 | largest rank: 7\n",
"iter: 3 | eps: 8.331e-08 | total time: 0.0675 | largest rank: 10 <- converged: eps < 1e-06\n",
"Did 33984 function evaluations, which took 0.0005171s (6.572e+07 evals/s)\n",
"\n"
]
}
],
"source": [
"t2 = tn.cross(function=lambda x, y: x*y, tensors=[t, t])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's check the accuracy of our cross-approximated squaring operation, compared to the groundtruth `t*t`:"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"tensor(8.6986e-08)"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"tn.relative_error(t*t, t2)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"See [this notebook](arithmetics.ipynb) for more examples on element-wise tensor operations."
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.7.3"
}
},
"nbformat": 4,
"nbformat_minor": 2
}
