{ "cells": [ { "cell_type": "markdown", "id": "39957b9d", "metadata": {}, "source": [ "# Tensor completion with Riemannian optimization\n", "\n", "Tensor completion recovers a tensor from a small subset of its entries, assuming that the tensor has a low tensor-train (TT) rank.\n", "Given noisy observations $y_m \\approx \\mathsf{x}_{\\mathbf{i}_m}$ of the entries at the multi-indices $\\mathbf{i}_1, \\dots, \\mathbf{i}_M$, we minimize the misfit\n", "\n", "$$ f(\\mathsf{x}) = \\sum_{m=1}^{M} \\big( \\mathsf{x}_{\\mathbf{i}_m} - y_m \\big)^2 $$\n", "\n", "over the set $\\mathcal{M}_{\\mathbf{r}}$ of TT tensors with a fixed TT rank $\\mathbf{r}$.\n", "This set is a smooth manifold, so we use Riemannian gradient descent ([Steinlechner, 2016](https://doi.org/10.1137/15M1010506)): the gradient is projected onto the tangent space at the current iterate, a step is taken along it, and TT rounding to rank $\\mathbf{r}$ brings the result back onto the manifold.\n", "The [manifold notebook](manifold.ipynb) introduces the Riemannian gradient in more detail.\n", "\n", "Imports:" ] }, { "cell_type": "code", "execution_count": 1, "id": "0de091b6", "metadata": { "execution": { "iopub.execute_input": "2026-09-28T17:48:07.324832Z", "iopub.status.busy": "2026-09-28T17:48:07.324722Z", "iopub.status.idle": "2026-09-28T17:48:08.240001Z", "shell.execute_reply": "2026-09-28T17:48:08.239563Z" } }, "outputs": [], "source": [ "import datetime\n", "import numpy as np\n", "import torch as tn\n", "try:\n", " import torchtt as tntt\n", "except:\n", " print('Installing torchTT...')\n", " %pip install git+https://github.com/ion-g-ion/torchTT\n", " import torchtt as tntt" ] }, { "cell_type": "markdown", "id": "c3952a35", "metadata": {}, "source": [ "## Test problem\n", "\n", "The tensor to recover samples the function $g(x_1, x_2, x_3, x_4) = 1 + x_1 + x_2 + x_3 + x_4 + x_1 x_2 + x_2 x_3 + \\sin(x_1)$ on a uniform $20 \\times 20 \\times 20 \\times 20$ grid of $[0,1]^4$.\n", "It has 160,000 entries but a small TT rank." ] }, { "cell_type": "code", "execution_count": 2, "id": "35c01b47", "metadata": { "execution": { "iopub.execute_input": "2026-09-28T17:48:08.241679Z", "iopub.status.busy": "2026-09-28T17:48:08.241533Z", "iopub.status.idle": "2026-09-28T17:48:08.252469Z", "shell.execute_reply": "2026-09-28T17:48:08.252083Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "TT rank of the target: [1, 3, 3, 2, 1]\n" ] } ], "source": [ "tn.manual_seed(0) # reproducible observations and initial guess\n", "\n", "N = 20\n", "Xs = tntt.meshgrid([tn.linspace(0, 1, N, dtype=tn.float64)]*4)\n", "target = Xs[0]+1+Xs[1]+Xs[2]+Xs[3]+Xs[0]*Xs[1]+Xs[1]*Xs[2]+tntt.TT(tn.sin(Xs[0].full()))\n", "target = target.round(1e-10)\n", "print('TT rank of the target:', target.R)" ] }, { "cell_type": "markdown", "id": "112504fb", "metadata": {}, "source": [ "## Observations\n", "\n", "We observe $M = 10000$ randomly chosen entries (about 6% of the tensor), perturbed by Gaussian noise with standard deviation $10^{-3}$.\n", "The method `apply_mask()` evaluates a TT tensor at a list of multi-indices." ] }, { "cell_type": "code", "execution_count": 3, "id": "a4cd958c", "metadata": { "execution": { "iopub.execute_input": "2026-09-28T17:48:08.253447Z", "iopub.status.busy": "2026-09-28T17:48:08.253359Z", "iopub.status.idle": "2026-09-28T17:48:08.256384Z", "shell.execute_reply": "2026-09-28T17:48:08.255972Z" } }, "outputs": [], "source": [ "M = 10000 # number of observations\n", "indices = tn.randint(0, N, (M, 4))\n", "\n", "# the observations are noisy\n", "sigma_noise = 0.001\n", "obs = tn.normal(target.apply_mask(indices), sigma_noise)\n", "\n", "# squared misfit on the observed entries\n", "loss = lambda x: (x.apply_mask(indices)-obs).norm()**2" ] }, { "cell_type": "markdown", "id": "ff069973", "metadata": {}, "source": [ "## Riemannian gradient descent\n", "\n", "We start from a random TT tensor of rank $(1,3,3,3,1)$.\n", "In every iteration, `torchtt.manifold.riemannian_gradient()` computes the Riemannian gradient $\\xi$ of the loss using automatic differentiation.\n", "Since the loss is quadratic, the step size along $-\\xi$ that minimizes it can be computed exactly:\n", "\n", "$$ \\alpha = \\frac{\\langle P_\\Omega \\xi,\\, P_\\Omega \\mathsf{x} - y \\rangle}{\\| P_\\Omega \\xi \\|^2}, $$\n", "\n", "where $P_\\Omega$ keeps only the observed entries.\n", "Rounding the updated tensor to the rank of the iterate retracts it back onto the manifold." ] }, { "cell_type": "code", "execution_count": 4, "id": "dc566380", "metadata": { "execution": { "iopub.execute_input": "2026-09-28T17:48:08.257171Z", "iopub.status.busy": "2026-09-28T17:48:08.257087Z", "iopub.status.idle": "2026-09-28T17:48:17.344459Z", "shell.execute_reply": "2026-09-28T17:48:17.343987Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Iteration 100 loss 2.482796e+01 relative error 2.846982e-02\n" ] }, { "name": "stdout", "output_type": "stream", "text": [ "Iteration 200 loss 2.224802e+01 relative error 2.524484e-02\n" ] }, { "name": "stdout", "output_type": "stream", "text": [ "Iteration 300 loss 1.293911e+00 relative error 4.510943e-03\n" ] }, { "name": "stdout", "output_type": "stream", "text": [ "Iteration 400 loss 9.445935e-03 relative error 5.464841e-05\n" ] }, { "name": "stdout", "output_type": "stream", "text": [ "Iteration 500 loss 9.445857e-03 relative error 5.460669e-05\n" ] }, { "name": "stdout", "output_type": "stream", "text": [ "Iteration 600 loss 9.445186e-03 relative error 5.454384e-05\n" ] }, { "name": "stdout", "output_type": "stream", "text": [ "Iteration 700 loss 9.442962e-03 relative error 5.471117e-05\n" ] }, { "name": "stdout", "output_type": "stream", "text": [ "Iteration 800 loss 9.442961e-03 relative error 5.471383e-05\n" ] }, { "name": "stdout", "output_type": "stream", "text": [ "Iteration 900 loss 9.442961e-03 relative error 5.471385e-05\n" ] }, { "name": "stdout", "output_type": "stream", "text": [ "Iteration 1000 loss 9.442961e-03 relative error 5.471385e-05\n", "Time elapsed 0:00:09.084384\n" ] } ], "source": [ "x = tntt.randn([N]*4, [1, 3, 3, 3, 1]) # initial guess\n", "\n", "tme = datetime.datetime.now()\n", "for i in range(1000):\n", " # Riemannian gradient of the loss\n", " grad = tntt.manifold.riemannian_gradient(x, loss)\n", "\n", " # exact line search along -grad (the loss is quadratic)\n", " residual = x.apply_mask(indices) - obs\n", " grad_obs = grad.apply_mask(indices)\n", " step_size = (grad_obs @ residual) / (grad_obs @ grad_obs)\n", "\n", " # step and retraction onto the manifold of tensors with rank x.R\n", " x = (x - step_size * grad).round(0, x.R)\n", "\n", " if (i+1) % 100 == 0:\n", " print('Iteration %4d loss %e relative error %e' % (i+1, loss(x), (x-target).norm()/target.norm()))\n", "tme = datetime.datetime.now() - tme\n", "print('Time elapsed', tme)" ] }, { "cell_type": "markdown", "id": "9bd64c2c", "metadata": {}, "source": [ "## Results\n", "\n", "The loss levels off at about $M \\sigma^2 = 10^{-2}$, the contribution of the noise, and the completed tensor matches the whole target, including the 94% of entries that were never observed.\n", "The number of unknowns (the entries of the TT cores) is much smaller than the number of observations." ] }, { "cell_type": "code", "execution_count": 5, "id": "135bcd15", "metadata": { "execution": { "iopub.execute_input": "2026-09-28T17:48:17.345760Z", "iopub.status.busy": "2026-09-28T17:48:17.345654Z", "iopub.status.idle": "2026-09-28T17:48:17.348235Z", "shell.execute_reply": "2026-09-28T17:48:17.347873Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Number of observations 10000, tensor shape [20, 20, 20, 20], percentage of entries observed 6.25%\n", "Number of unknowns 480, number of observations 10000, unknowns/observations 0.048\n", "Relative error of the completed tensor 5.471385e-05\n" ] } ], "source": [ "print('Number of observations %d, tensor shape %s, percentage of entries observed %.2f%%' % (M, str(x.N), 100*M/np.prod(x.N)))\n", "print('Number of unknowns %d, number of observations %d, unknowns/observations %.3f' % (tntt.numel(x), M, tntt.numel(x)/M))\n", "print('Relative error of the completed tensor %e' % ((x-target).norm()/target.norm()))" ] } ], "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.12.3" } }, "nbformat": 4, "nbformat_minor": 5 }