3_Fundamental_tensor_decompositions.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Fundamental tensor decompositions.\n",
    "### Last modification (05.06.2018)\n",
    "\n",
    "In this tutorial we provide a theoretical backgound on the fundamental tensor decompositions of multidimensional arrays and show how these data algorithms can be used with [hottbox](https://github.com/hottbox/hottbox) through **CPD**, **HOSVD**, **HOOI** and **TTSVD** classes.\n",
    "\n",
    "More details on **CPD**, **HOSVD**, **HOOI** and **TTSVD** classes can be found on the [documentation page](https://hottbox.github.io/stable/api/hottbox.algorithms.decomposition).\n",
    "\n",
    "**Note:** this tutorial assumes that you are familiar with the basics of tensor algebra, tensor representaitons in different forms and the corresponding conventional notation. If you are new to these topics, check out our previous tutorials: [tutorial_1](https://github.com/hottbox/hottbox-tutorials/blob/master/1_N-dimensional_arrays_and_Tensor_class.ipynb) and [tutorial_2](https://github.com/hottbox/hottbox-tutorials/blob/master/2_Efficient_representations_of_tensors.ipynb).\n",
    "\n",
    "**Requirements:** ``hottbox==0.1.3``\n",
    "\n",
    "**Authors:** \n",
    "Ilya Kisil (ilyakisil@gmail.com); \n",
    "Giuseppe G. Calvi (ggc115@ic.ac.uk)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from hottbox.core import Tensor, residual_tensor\n",
    "from hottbox.algorithms.decomposition import TTSVD, HOSVD, HOOI, CPD\n",
    "from hottbox.metrics import residual_rel_error"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Tensor decompositions and their API\n",
    "\n",
    "In [previous tutorial](https://github.com/hottbox/hottbox-tutorials/blob/master/2_Efficient_representations_of_tensors.ipynb), we have introduced various efficient representations of the multi-dimensional arrays (tensors) and how they can be created using the **`hottbox`** API. Here were show how these representations can obtained for a given tensor.\n",
    "\n",
    "For these purposes, the following algorithms have been implemented in **``hottbox>=0.1.2``**:\n",
    "\n",
    "- CPD: produces instance of **TensorCPD** class\n",
    "- HOSVD: produces instance of **TensorTKD** class\n",
    "- HOOI: produces instance of **TensorTKD** class\n",
    "- TTSVD: produces instance of **TensorTT** class\n",
    "\n",
    "By analogy with the computation algorithms in **`sklearn`**, you first need to create an instance of this algorithm. Then you use its method **`decompose`** in order to obtain an efficient representation of the original tensor. See [tutorial_2](https://github.com/hottbox/hottbox-tutorials/blob/master/2_Efficient_representations_of_tensors.ipynb) for more information on various efficient resentations of multi-dimensional arrays. For simplicity and ease of visualisation, the following matrial is provided for the tensors of order $3$, but can be easily generalised to a case of $N$-th order.\n",
    "\n",
    "In all computational examples below we will decompose the same 3-D array with randomly generated values, while all algorithms will be initialised with default parameters."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "This tensor is of order 3 and consists of 210 elements.\n",
      "Sizes and names of its modes are (5, 6, 7) and ['mode-0', 'mode-1', 'mode-2'] respectively.\n"
     ]
    }
   ],
   "source": [
    "np.random.seed(0)\n",
    "I, J, K = 5, 6, 7\n",
    "\n",
    "array_3d = np.random.rand(I * J * K).reshape((I, J, K)).astype(np.float)\n",
    "\n",
    "tensor = Tensor(array_3d)\n",
    "print(tensor)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Canonical Polyadic Decomposition (CPD)\n",
    "![tensorcpd](./images/TensorCPD.png)\n",
    "## Theoretical background\n",
    "\n",
    "The **Canonical Polyadic Decomposition (CPD)** (also referred to as PARAFAC or CANDECOMP) is an algorithms that factorizes an $3$-rd order tensor $\\mathbf{\\underline{X}} \\in \\mathbb{R}^{I \\times J \\times K}$ into a linear combination of terms $\\mathbf{\\underline{X}}_r = \\mathbf{a}_r \\circ \\mathbf{b}_r \\circ \\mathbf{c}_r$, which are rank-$1$ tensors. In other words the tensor $\\mathbf{\\underline{X}}$ is decomposed as\n",
    "\n",
    "$$\n",
    "\\begin{equation}\n",
    "\\begin{aligned}\n",
    "\\mathbf{\\underline{X}} & \\simeq \\sum_{r=1}^{R} \\lambda_r \\mathbf{a}_r \\circ \\mathbf{b}_r \\circ \\mathbf{c}_r\\\\\n",
    "& = \\mathbf{\\underline{\\Lambda}} \\times_1 \\mathbf{A} \\times_2 \\mathbf{B} \\times_3 \\mathbf{C}\\\\\n",
    "& = \\Big[    \\mathbf{\\underline{\\Lambda}} ;  \\mathbf{A},  \\mathbf{B}, \\mathbf{C}      \\Big]\n",
    "\\end{aligned}\n",
    "\\end{equation}\n",
    "$$\n",
    "\n",
    "where \n",
    "\n",
    "- $\\mathbf{\\underline{\\Lambda}}$ is an $3$-rd order core tensor having $\\lambda_r$ as entries in positions $\\mathbf{\\underline{\\Lambda}}[i, j, k]$, where $i = j = k$, and zeroes elsewhere\n",
    "\n",
    "- $\\mathbf{A}, \\mathbf{B}, \\mathbf{C}$ are factor matrix obtained as the concatenation of the corresponding factor vectors, i.e  $ \\mathbf{A} = \\Big[    \\mathbf{a}_1 \\mathbf{a}_2  \\cdots \\mathbf{a}_R   \\Big] $ \n",
    "\n",
    "Assuming the kruskal rank is fixed, there are many algorithms to compute a CPD. The most popular aproach is via the alternating least squares (ALS) method. The goal is to find such CP represenation $[ \\mathbf{\\underline{\\Lambda}} ; \\mathbf{A}, \\mathbf{B}, \\mathbf{C} ]$ which provides the best approximation of the original tensor $\\mathbf{\\underline{X}}$:\n",
    "\n",
    "$$\n",
    "\\text{min} \\| \\mathbf{\\underline{X}} - [ \\mathbf{\\underline{\\Lambda}} ; \\mathbf{A}, \\mathbf{B}, \\mathbf{C} ] \\|^2_F\n",
    "$$\n",
    "\n",
    "The alternating least squares approach fixes $\\mathbf{B}$ and $\\mathbf{C}$ to solve for $\\mathbf{A}$, then fixes $\\mathbf{A}$ and $\\mathbf{C}$ to solve for $\\mathbf{B}$, then fixes $\\mathbf{A}$ and $\\mathbf{B}$ to solve for $\\mathbf{C}$, and continues to repeat the\n",
    "entire procedure until some convergence criterion is satisfied.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## CPD class in hottbox\n",
    "\n",
    "In **`hottbox`**, the CPD-ALS algorithm is implemented by the **`CPD`** class. Despite of the parameters used to initialise this algorithm, it outputs an instance of **`TensorCPD`** class after each call of the **`decompose`** method. This method takes an object of **`Tensor`** class and desired value of kruskal rank passed as a tuple of length 1. \n",
    "\n",
    "**Note:** the Kruskal rank is passed as a tuple so to keep the same format with other algorithms for tensor decompositions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "CPD(epsilon=0.01, init='svd', max_iter=50, random_state=None, tol=0.0001,\n",
       "    verbose=False)"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "alg = CPD()\n",
    "alg"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\tOutput of the CPD algorithm:\n",
      "Kruskal representation of a tensor with rank=(5,).\n",
      "Factor matrices represent properties: ['mode-0', 'mode-1', 'mode-2']\n",
      "With corresponding latent components described by (5, 6, 7) features respectively.\n",
      "\n",
      "\tFactor matrices\n",
      "Mode-0 factor matrix is of shape (5, 5)\n",
      "Mode-1 factor matrix is of shape (6, 5)\n",
      "Mode-2 factor matrix is of shape (7, 5)\n",
      "\n",
      "\tCore tensor\n",
      "This tensor is of order 3 and consists of 125 elements.\n",
      "Sizes and names of its modes are (5, 5, 5) and ['mode-0', 'mode-1', 'mode-2'] respectively.\n"
     ]
    }
   ],
   "source": [
    "kruskal_rank = (5,)\n",
    "\n",
    "tensor_cpd = alg.decompose(tensor, rank=kruskal_rank)\n",
    "print(\"\\tOutput of the {} algorithm:\".format(alg.name))\n",
    "print(tensor_cpd)\n",
    "\n",
    "print('\\n\\tFactor matrices')\n",
    "for mode, fmat in enumerate(tensor_cpd.fmat):\n",
    "    print('Mode-{} factor matrix is of shape {}'.format(mode, fmat.shape))\n",
    "    \n",
    "print('\\n\\tCore tensor')\n",
    "print(tensor_cpd.core)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As we can see, the produced object of the **`TensorCPD`** class also contains general information about the underlying tensor, such as its shape, order etc, which can be accessed through the corresponding properties"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The shape of the underlying tensor is (5, 6, 7)\n",
      "The order of the underlying tensor is 3\n"
     ]
    }
   ],
   "source": [
    "full_shape = tensor_cpd.ft_shape\n",
    "order = tensor_cpd.order\n",
    "print('The shape of the underlying tensor is {}'.format(full_shape))\n",
    "print('The order of the underlying tensor is {}'.format(order))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Tucker Decomposition\n",
    "\n",
    "![tensortkd](./images/TensorTKD.png)\n",
    "\n",
    "**Tucker Decomposition** represents a given tensor $\\mathbf{\\underline{X}} \\in \\mathbb{R}^{I \\times J \\times K}$ if the form of a dense core tensor $\\mathbf{\\underline{G}}$ with multi-linear rank $(Q, R, P)$ and a set of\n",
    "factor matrices $\\mathbf{A} \\in \\mathbb{R}^{I \\times Q}, \\mathbf{B} \\in \\mathbb{R}^{J \\times R}$ and $\\mathbf{C} \\in\n",
    "\\mathbb{R}^{K \\times P}$ as illustrated above. In other words, the tensor $\\mathbf{\\underline{X}}$ can represented in tucker form as\n",
    "\n",
    "$$\n",
    "\\begin{equation}\n",
    "\\begin{aligned}\n",
    "\\mathbf{\\underline{X}} & \\simeq \\sum_{q=1}^{Q} \\sum_{r=1}^{R} \\sum_{p=1}^{P} g_{qrp} \\mathbf{a}_q \\circ \\mathbf{b}_r \\circ \\mathbf{c}_p\\\\\n",
    "& = \\mathbf{\\underline{G}} \\times_1 \\mathbf{A} \\times_2 \\mathbf{B} \\times_3 \\mathbf{C}\\\\\n",
    "& = \\Big[    \\mathbf{\\underline{G}} ;  \\mathbf{A},  \\mathbf{B}, \\mathbf{C}      \\Big]\n",
    "\\end{aligned}\n",
    "\\end{equation}\n",
    "$$\n",
    "\n",
    "On practice, there exist several algorithms to represent a given tensor in the Tucker format. The two most used ones are Higher Order Singular Value Decomposition (HOSVD), and Higher Order Orthogonal Iteration (HOOI), which are implemented through the **`HOSVD`** and **`HOOI`** classes respectively."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Higher Order Singular Value Decomposition (HOSVD)\n",
    "\n",
    "Consider an $3$-rd order tensor $\\mathbf{\\underline{X}} \\in \\mathbb{R}^{I \\times J \\times K}$, decomposed in the Tucker format as\n",
    "\n",
    "$$\n",
    "\\mathbf{\\underline{X}} = \\mathbf{\\underline{G}} \\times_1 \\mathbf{A} \\times_2 \\mathbf{B} \\times_3 \\mathbf{C}\n",
    "$$\n",
    "\n",
    "The HOSVD is a special case of the Tucker decomposition, in which all the factor matrices are constrained to be orthogonal. They are computed as truncated version of the left singular matrices of all possible mode-$n$ unfoldings of tensor $\\mathbf{\\underline{X}}$:\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "\\mathbf{X}_{(1)} &= \\mathbf{U}_1  \\mathbf{\\Sigma}_1 \\mathbf{V}_1^T \\quad \\rightarrow \\quad \\mathbf{A} = \\mathbf{U}_1[1:R_1]\\\\\n",
    "\\mathbf{X}_{(2)} &= \\mathbf{U}_2  \\mathbf{\\Sigma}_2 \\mathbf{V}_2^T \\quad \\rightarrow \\quad \\mathbf{B} = \\mathbf{U}_2[1:R_2] \\\\\n",
    "\\mathbf{X}_{(3)} &= \\mathbf{U}_3  \\mathbf{\\Sigma}_3 \\mathbf{V}_3^T \\quad \\rightarrow \\quad \\mathbf{C} = \\mathbf{U}_3[1:R_3] \\\\\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "For a general order-$N$ tensor, the $N$-tuple $(R_1, \\ldots, R_N)$ is called the **multi-linear rank** and provides flexibility in compression and approximation of the original tensor. For our order-$3$ tensor in the multilinear rank is therefore $(R_1, R_2, R_3)$. After factor matrices are obtained, the core tensor $\\mathbf{\\underline{G}}$ is computed as\n",
    "$$\n",
    "\\mathbf{\\underline{G}} = \\mathbf{\\underline{X}} \\times_1 \\mathbf{A}^T \\times_2 \\mathbf{B}^T \\times_3 \\mathbf{C}^T        \n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## HOSVD class in hottbox\n",
    "\n",
    "In **`hottbox`**, the HOSVD algorithm is implemented by the **`HOSVD`** class. Despite of the parameters used to initialise this algorithm, it outputs an instance of **`TensorTKD`** class after each call of the **`decompose`** method. This method takes an object of **`Tensor`** class and desired values of multi-linear rank passed as a tuple. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "HOSVD(process=(), verbose=False)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "alg = HOSVD()\n",
    "alg"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\tOutput of the HOSVD algorithm:\n",
      "Tucker representation of a tensor with multi-linear rank=(4, 5, 6).\n",
      "Factor matrices represent properties: ['mode-0', 'mode-1', 'mode-2']\n",
      "With corresponding latent components described by (5, 6, 7) features respectively.\n",
      "\n",
      "\tFactor matrices\n",
      "Mode-0 factor matrix is of shape (5, 4)\n",
      "Mode-1 factor matrix is of shape (6, 5)\n",
      "Mode-2 factor matrix is of shape (7, 6)\n",
      "\n",
      "\tCore tensor\n",
      "This tensor is of order 3 and consists of 120 elements.\n",
      "Sizes and names of its modes are (4, 5, 6) and ['mode-0', 'mode-1', 'mode-2'] respectively.\n"
     ]
    }
   ],
   "source": [
    "ml_rank = (4, 5, 6)\n",
    "tensor_tkd_hosvd = alg.decompose(tensor, ml_rank)\n",
    "print(\"\\tOutput of the {} algorithm:\".format(alg.name))\n",
    "print(tensor_tkd_hosvd)\n",
    "\n",
    "print('\\n\\tFactor matrices')\n",
    "for mode, fmat in enumerate(tensor_tkd_hosvd.fmat):\n",
    "    print('Mode-{} factor matrix is of shape {}'.format(mode, fmat.shape))\n",
    "    \n",
    "print('\\n\\tCore tensor')\n",
    "print(tensor_tkd_hosvd.core)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As we can see, the produced object of the **`TensorTKD`** class also contains general information about the underlying tensor, such as its shape, order etc, which can be accessed through the corresponding properties"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The shape of the underlying tensor is (5, 6, 7)\n",
      "The order of the underlying tensor is 3\n"
     ]
    }
   ],
   "source": [
    "full_shape = tensor_tkd_hosvd.ft_shape\n",
    "order = tensor_tkd_hosvd.order\n",
    "print('The shape of the underlying tensor is {}'.format(full_shape))\n",
    "print('The order of the underlying tensor is {}'.format(order))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Higher Order Orthogonal Iteration (HOOI)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "HOOI algorithm is another special case of the Tuker decomposition. Like HOSVD, it decomposes a tensor into a dense core tensor and orthogonal factor matrices. The difference between the two lies in the fact that in HOOI the factor matrices are optimized iteratively using an Alternating Least Squares (ALS) approach. (In practice HOSVD is usually used within HOOI to initialize the factor matrices). In other words, the tucker representation $[ \\mathbf{\\underline{G}};\\mathbf{A}^{(1)}, \\mathbf{A}^{(2)}, \\cdots,\\mathbf{A}^{(N)} ]$ of the given tensor $\\mathbf{\\underline{X}}$ is obtained through the HOOI as follows\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "&\\mathbf{\\underline{Y}} = \\mathbf{\\underline{X}} \\times_1 \\mathbf{A}^{(1)T} \\times_2 \\cdots \\times_{n-1} \\mathbf{A}^{(n-1)T} \\times_{n+1} \\mathbf{A}^{(n+1)} \\times \\cdots \\times_N \\mathbf{A}^{(N)} \\\\\n",
    "&\\mathbf{A}^{(n)} \\leftarrow R_n \\text{ leftmost singular vectors of } \\mathbf{Y}_{(n)}\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "The above is repeated until convergence, then the core tensor $\\mathbf{\\underline{G}} \\in \\mathbb{R}^{R_1 \\times R_2 \\times \\cdots \\times R_N}$ is computed as\n",
    "\n",
    "$$\n",
    "\\mathbf{\\underline{G}} = \\mathbf{\\underline{X}} \\times_1 \\mathbf{A}^{(1)T}  \\times_2 \\mathbf{A}^{(2)T} \\times_3 \\cdots  \\times_N \\mathbf{A}^{(N)T}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## HOOI class in hottbox\n",
    "\n",
    "In **`hottbox`**, the HOOI algorithm is implemented by the **`HOOI`** class. Despite of the parameters used to initialise this algorithm, it outputs an instance of **`TensorTKD`** class after each call of the **`decompose`** method. This method takes an object of **`Tensor`** class and desired values of multi-linear rank passed as a tuple. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "HOOI(epsilon=0.01, init='hosvd', max_iter=50, process=(),\n",
       "     random_state=None, tol=0.0001, verbose=False)"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "alg = HOOI()\n",
    "alg"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\tOutput of the HOOI algorithm:\n",
      "Tucker representation of a tensor with multi-linear rank=(4, 5, 6).\n",
      "Factor matrices represent properties: ['mode-0', 'mode-1', 'mode-2']\n",
      "With corresponding latent components described by (5, 6, 7) features respectively.\n",
      "\n",
      "\tFactor matrices\n",
      "Mode-0 factor matrix is of shape (5, 4)\n",
      "Mode-1 factor matrix is of shape (6, 5)\n",
      "Mode-2 factor matrix is of shape (7, 6)\n",
      "\n",
      "\tCore tensor\n",
      "This tensor is of order 3 and consists of 120 elements.\n",
      "Sizes and names of its modes are (4, 5, 6) and ['mode-0', 'mode-1', 'mode-2'] respectively.\n"
     ]
    }
   ],
   "source": [
    "ml_rank = (4, 5, 6)\n",
    "tensor_tkd_hooi = alg.decompose(tensor, ml_rank)\n",
    "print(\"\\tOutput of the {} algorithm:\".format(alg.name))\n",
    "print(tensor_tkd_hooi)\n",
    "\n",
    "print('\\n\\tFactor matrices')\n",
    "for mode, fmat in enumerate(tensor_tkd_hooi.fmat):\n",
    "    print('Mode-{} factor matrix is of shape {}'.format(mode, fmat.shape))\n",
    "    \n",
    "print('\\n\\tCore tensor')\n",
    "print(tensor_tkd_hooi.core)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As we can see, the produced object of the **`TensorTKD`** class also contains general information about the underlying tensor, such as its shape, order etc, which can be accessed through the corresponding properties"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The shape of the underlying tensor is (5, 6, 7)\n",
      "The order of the underlying tensor is 3\n"
     ]
    }
   ],
   "source": [
    "full_shape = tensor_tkd_hooi.ft_shape\n",
    "order = tensor_tkd_hooi.order\n",
    "print('The shape of the underlying tensor is {}'.format(full_shape))\n",
    "print('The order of the underlying tensor is {}'.format(order))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Tensor Train Decomposition via SVD\n",
    "\n",
    "![tensortt](./images/TensorTT.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Theoretical background\n",
    "\n",
    "**Tensor train decomposition** represents a given tensor a set of sparsely interconnected lower-order tensors and factor matrices. Mathematically speaking, the obtained TT representation of an $N$-th order tensor $\\mathbf{\\underline{X}} \\in \\mathbb{R}^{I_1 \\times I_2 \\times \\cdots \\times I_N}$ can be expressed as a TT as\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "\\mathbf{\\underline{X}}\n",
    "&= \\Big[  \\mathbf{A}, \\mathbf{\\underline{G}}^{(1)}, \\mathbf{\\underline{G}}^{(2)}, \\cdots, \\mathbf{\\underline{G}}^{(N-1)}, \\mathbf{B}  \\Big]\\\\\n",
    "&= \\mathbf{A} \\times^1_2 \\mathbf{\\underline{G}}^{(1)}  \\times^1_3 \\mathbf{\\underline{G}}^{(2)}   \\times^1_3 \\cdots \\times^1_3 \\mathbf{\\underline{G}}^{(N-1)} \\times^1_3 \\mathbf{B} \n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "Each element of a TT is generally referred to as **tt-core** with sizesof its dimensions: $\\mathbf{A} \\in \\mathbb{R}^{I_1 \\times R_1}$, $\\mathbf{B} \\in \\mathbb{R}^{R_{N-1}\\times I_N}$, $\\mathbf{\\underline{G}}^{(n)} \\in \\mathbb{R}^{R_n \\times I_{n+1} \\times R_{n+1}}$\n",
    "\n",
    "\n",
    "The TTSVD algorithm involves iteratively performing a series of foldings and unfoldings on an original tensor $\\mathbf{\\underline{X}} \\in \\mathbb{R}^{I_1 \\times I_2 \\times \\cdots \\times I_N}$ in conjunction with SVD. At every iteration a core $\\mathbf{\\underline{G}}^{(n)} \\in \\mathbb{R}^{R_n \\times I_{n+1} \\times R_{n+1}}$ is computed, where the TT-rank $(R_1, R_2, \\dots, R_N)$ has been specified a priori. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## TTSVD class in hottbox\n",
    "\n",
    "In **`hottbox`**, the TTSVD algorithm is implemented by the **`TTSVD`** class. Despite of the parameters used to initialise this algorithm, it outputs an instance of **`TensorTT`** class after each call of the **`decompose`** method. This method takes an object of **`Tensor`** class and desired values of tt-rank passed as a tuple. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "TTSVD(verbose=False)"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "alg = TTSVD()\n",
    "alg"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\tOutput of the TTSVD algorithm:\n",
      "Tensor train representation of a tensor with tt-rank=(2, 3).\n",
      "Shape of this representation in the full format is (5, 6, 7).\n",
      "Physical modes of its cores represent properties: ['mode-0', 'mode-1', 'mode-2']\n",
      "\n",
      "\tTT-Core #0\n",
      "This tensor is of order 2 and consists of 10 elements.\n",
      "Sizes and names of its modes are (5, 2) and ['mode-0', 'mode-1'] respectively.\n",
      "\n",
      "\tTT-Core #1\n",
      "This tensor is of order 3 and consists of 36 elements.\n",
      "Sizes and names of its modes are (2, 6, 3) and ['mode-0', 'mode-1', 'mode-2'] respectively.\n",
      "\n",
      "\tTT-Core #2\n",
      "This tensor is of order 2 and consists of 21 elements.\n",
      "Sizes and names of its modes are (3, 7) and ['mode-0', 'mode-1'] respectively.\n"
     ]
    }
   ],
   "source": [
    "tt_rank = (2,3)\n",
    "\n",
    "tensor_tt = alg.decompose(tensor, tt_rank)\n",
    "print(\"\\tOutput of the {} algorithm:\".format(alg.name))\n",
    "print(tensor_tt)\n",
    "\n",
    "for i, core in enumerate(tensor_tt.cores):\n",
    "    print('\\n\\tTT-Core #{}'.format(i))\n",
    "    print(core)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As we can see, the produced object of the **`TensorTT`** class also contains general information about the underlying tensor, such as its shape, order etc, which can be accessed through the corresponding properties"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The shape of the underlying tensor is (5, 6, 7)\n",
      "The order of the underlying tensor is 3\n"
     ]
    }
   ],
   "source": [
    "full_shape = tensor_tt.ft_shape\n",
    "order = tensor_tt.order\n",
    "print('The shape of the underlying tensor is {}'.format(full_shape))\n",
    "print('The order of the underlying tensor is {}'.format(order))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Evaluating results of tensor decompositions\n",
    "\n",
    "For each result of the tensor decomposition we can compute a residual tensor and calculate relative error of approximation:\n",
    "```python\n",
    "    tensor_res = residual_tensor(tensor, tensor_cpd)\n",
    "    rel_error = tensor_res.frob_norm / tensor.frob_norm        \n",
    "```\n",
    "Or can do it in one line:\n",
    "```python\n",
    "    rel_error = residual_rel_error(tensor, tensor_cpd)\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\tResidual tensor\n",
      "This tensor is of order 3 and consists of 210 elements.\n",
      "Sizes and names of its modes are (5, 6, 7) and ['mode-0', 'mode-1', 'mode-2'] respectively.\n"
     ]
    }
   ],
   "source": [
    "tensor_cpd_res = residual_tensor(tensor, tensor_cpd)\n",
    "print('\\tResidual tensor')\n",
    "print(tensor_cpd_res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Relative error of CPD approximation = 0.31\n",
      "Relative error of CPD approximation = 0.31\n"
     ]
    }
   ],
   "source": [
    "rel_error = tensor_cpd_res.frob_norm / tensor.frob_norm \n",
    "print('Relative error of CPD approximation = {:.2f}'.format(rel_error))\n",
    "\n",
    "rel_error = residual_rel_error(tensor, tensor_cpd)\n",
    "print('Relative error of CPD approximation = {:.2f}'.format(rel_error))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Relative error of HOSVD approximation = 0.21\n"
     ]
    }
   ],
   "source": [
    "rel_error = residual_rel_error(tensor, tensor_tkd_hosvd)\n",
    "print('Relative error of HOSVD approximation = {:.2f}'.format(rel_error))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Relative error of HOOI approximation = 0.21\n"
     ]
    }
   ],
   "source": [
    "rel_error = residual_rel_error(tensor, tensor_tkd_hooi)\n",
    "print('Relative error of HOOI approximation = {:.2f}'.format(rel_error))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Relative error of TT approximation = 0.39\n"
     ]
    }
   ],
   "source": [
    "rel_error = residual_rel_error(tensor, tensor_tt)\n",
    "print('Relative error of TT approximation = {:.2f}'.format(rel_error))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Further reading list\n",
    "- Tamara G. Kolda and Brett W. Bader, \"Tensor decompositions and applications.\" SIAM REVIEW, 51(3):455–500, 2009.\n",
    "\n",
    "- Lieven De Lathauwer, Bart De Moor, and Joos Vandewalle, \"A multilinear singular value decomposition.\" SIAM journal on Matrix Analysis and Applications 21.4 (2000): 1253-1278.\n",
    "\n",
    "- Ivan V. Oseledets,  \"Tensor-train decomposition.\" SIAM Journal on Scientific Computing 33.5 (2011): 2295-2317."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "hottbox-tutorials",
   "language": "python",
   "name": "hottbox-tutorials"
  },
  "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.6.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}