A TT-eigenvalue solver that finally works

Date 26/05/2016 Tags paper

In a recent preprint by Maxim Rakhuba and Ivan Oseledets we propose a new algorithm for calculation of vibrational spectra of molecules using tensor train decomposition. Under the assumption that eigenfunctions lie on a low-parametric manifold of low-rank tensors we introduce the concept of manifold preconditioning of well-known iterative methods …

Exponential machines and tensor trains

Date 12/05/2016 Tags paper

Modeling interactions between features improves the performance of machine learning solutions in many domains (e.g. recommender systems or sentiment analysis). In this paper, we introduce Exponential Machines (ExM), a predictor that models all interactions of every order. The key idea is to represent an exponentially large tensor of parameters …

Convergence analysis of a projected fixed-point iteration

Date 06/04/2016 Tags paper

In this paper by Denis Kolesnikov and Ivan Oseledets we analyse convergence of projected fixed-point iteration on a Riemannian manifold of matrices with fixed rank. As a retraction method we use `projector splitting scheme’. We prove that the projector splitting scheme converges at least with the same rate as standard …

Compress-and-eliminate solver for sparse matrices

Date 30/03/2016 Tags paper

We propose a new Compress-and-Eliminate Solver for sparse matrices. The approach is proposed by Daria Sushnikova and Ivan Oseledets. The solver has a very simple algebraic structure, and outperfoms state-of-the art CHOLMOD software.

New paper in SIMAX

Date 01/12/2015 Tags paper

Our paper on a new rational Krylov method for solving large-scale Lyapunov equations “From Low-Rank Approximation to a Rational Krylov Subspace Method for the Lyapunov Equation” by D. Kolesnikov and I. Oseledets is now published in SIAM Journal oon Matrix Analysis and Applications

New paper in J. Comp. Phys

Date 05/11/2015 Tags paper

Our paper on low-rank computation of huge-dimensional path integrals “A low-rank approach to the computation of path integrals” by M. S. Litsarev and I. Oseledets published in Journal of Computational Physics

New paper in J. Chem. Phys

Date 04/11/2015 Tags paper

Our paper on multidimensional potential energy surfaces approximation] using a combination of active subspace methods and tensor train decomposition “Fitting high-dimensional potential energy surface using active subspace and tensor train (AS+TT) method” by V. Baranov and I. Oseledets is now published in Journal of Chemical Physics

Anton Sukhinov leaves the group

Our research scientist Anton Sukhinov has finished working at Scientific Computing group. We thank Anton for his valuable contributions to the research agenda and for his work with the industrial partners (Huawei, Intel) and wish him good luck in his future career.

MMMA-2015

We have succesfully hosted at Skoltech 4-th international conference on Matrices in Mathematics and Applications, MMMA-2015. More than 100 talks from 6 countries and 10 universities. This is the first conference at our new building of such, and we had many interesting talks and discussions. The talks and videos …

Path integrals & low-rank for unbounded domains

Date 24/05/2015 Tags paper

Path integrals play a dominant role in description of a wide range of problems in physics and mathematics. They are a universal and powerful tool for condensed matter and high-energy physics, theory of stochastic processes and parabolic differential equations, financial modelling, quantum chemistry and many others.

The solution of the …

Cross-conv paper published!

Date 03/04/2015 Tags paper

Our cross-convolution paper “Fast Multidimensional Convolution in Low-Rank Tensor Formats via Cross Approximation” by M. Rakhuba, I. Oseledets is now published in SIAM Journal on Scientific Computing

Similarity for heterogeneous networks

Date 24/02/2015 Tags paper

We propose a generalization of SimRank similarity measure for heterogeneous information networks. Each node is associated with a set of objects and there are different possible relations. This is encoded into the adjacency tensor, and the TensorSimRank equation is given as

s_{\alpha \beta} = \sum_{\gamma} w_{\alpha \beta \gamma …

Time integration of tensor trains published!

Date 04/02/2015 Tags paper

Our paper on time integration of tensor trains “Time integration of tensor trains” by C. Lubich, I. Oseledets, B. Vandereycken is now published in SIAM Journal on Numerical Analysis

Maximum-volume principle for rectangular matrices

Date 03/02/2015 Tags paper

A definition of p-volume of rectangular matrices is given. We generalize the results for square maximum-volume submatrices to the case rectangular maximal-volume submatrices and provide estimates for the growth of the coefficients. Three promising applications of such submatrices are presented: recommender systems, finding maximal elements in low-rank matrices and preconditioning …

Alexander Mikhalev defends his PhD

Date 30/12/2014

Congratulations to Alexander Mikhalev for his successful PhD defense in INM RAS!

Convolutional neural networks and tensors

Date 19/12/2014 Tags paper

Deep learning is a huge topic today; speeding up the computation with convolutional neural network is crucial for fast classification. In this work we show how fine-tuned canonical polyadic (CP) decomposition can be used to speedup CNN by a factor of 8-10.

This is a new page

Date 02/12/2014

The website is finally online!

Alternating low-rank method for the Lyapunov equation

Date 13/10/2014 Tags paper

Time-stepping free method based on the rational Krylov subspaces play an important role in many applications. The adaptative selection of the shifts for the construction of the RKS is crucial. In this paper we propose a new algorithm for the selection of the shifts. It is based on the connection …

Time evolution and optimization with MPS

Date 21/08/2014 Tags paper

The projector-splitting scheme in the TT/MPS format is a natural way to computing dynamics of quantum spin systems Hamiltonians with long-range interaction. We have proposed a unified approach that leads to a cheap and efficient computational scheme that can be applied to any Hamiltonian, represented in the MPO/TT …

Time integration of tensor trains

Date 07/08/2014 Tags paper

Dynamical low-rank approximation is an efficient framework for solving continious and discrete-time problems in high-dimensions. Using the Dirac-Frenkel principle applied to the tensor-train format, we have propose a robust and efficient time integrator for the resulting system of nonlinear equations.

Algorithm scheme Approximate Laplace inversion

Multidimensional integrals in ion-atom collisions

Date 19/03/2014 Tags paper

Simulation in physics is full of multidimensional integrals. In the paper M. S. Litsarev and I. V. Oseledets. Low rank approximations for the DEPOSIT computer code. arXiv preprint 1403.4068, 2014 we consider the DEPOSIT code that is suited for the computation of ion-atomic collisons. The main computational bottleneck is …

Preconditioners for hierarchical matrices

Date 12/03/2014 Tags paper

We continue to develop our h2tools package with the new functionality. The solution of linear systems with hierarchical matrices plays a crucial role in many applications. We use the sparse extended form of the H2-matrices to reduce the initial linear system to a block-structured linear system and then use this …

Convolution via cross approximation

Date 25/02/2014 Tags paper

Multidimensional convolution plays a crucial role in many applications. We have proposed a new method for approximate computation of the convolution in low-rank tensor formats that is based on the cross approximation in the frequency domain. The method is applicable to any SVD-based tensor format (skeleton, Tucker, Tensor Train …

Theses topics

I have put short descriptions of the available student project online. Please check

Happy new year!

Date 09/01/2013 Tags paper

2013 is now in its full rights, so it is time to go on with research. With Christian Lubich we have finished a paper on a very efficient time-stepping scheme for the dynamical low-rank approximation —- so-called KLS-scheme, which is remarkably simple but efficient to compute the dynamics on low-rank …

One more paper

Date 22/12/2012 Tags paper

One more old paper on explicit representations of simple functions in tensor formats is published in the Constructive Approximation!

Solving parabolic systems (with application to Fokker-Planck)

Date 14/12/2012 Tags paper

Our paper on the new time-stepping scheme based on the QTT-format has been published in SISC!

News

Date 14/10/2012

Four papers are in progress : on the block eigenvalue solver in the TT-format, on the dynamical low-rank approximation, on the tensor structure of the wavelet tensor train matrix and on the fast solution of the Stokes problem in tensor format. Hope to finish them soon.

Also, I put some …

Publications of our group

Date 17/07/2012

We have recently put the publications of our research group at the Institute of Numerical Mathematics RAS on the web. The list is not yet full, but is close. Check it!

Fast adaptive interpolation of multidimensional arrays in TT-format

Date 15/06/2012

This paper with Dmitry Savostyanov published in the end of 2011 in the Proceedings of 7th International Workshop on Multidimensional Systems (nDS), doi: 10.1109/nDS.2011.6076873 is about fast adaptive methods for the approximation of high-dimensional arrays by cross-type methods (such methods are quite popular for matrices).

The …

Dynamical TT-approximation

Date 25/04/2012

Dynamical low-rank approximation is a rather new and important topic, which was studied by Lubich and Koch for low-rank matrices and low-rank (in the sense of Tucker format) tensor decomposition. Such kind of techniques were well known in physics in chemistry, going back to Dirac-Frenkel principle, and MCTDH method for …

TT-Toolbox 2.2.

Date 08/02/2012

TT-Toolbox (TT=Tensor Train) Version 2.2

TT(Tensor Train) format is an efficient way for low-parametric

representation of high-dimensional tensors. The TT-Toolbox

is a MATLAB implementation of basic operations with

tensors in TT-format. It includes:

* tt_tensor and tt_matrix classes for storing vectors and operators

* Basic linear …

Date 04/12/2011

Google mycitations service looks great. Here is mine

Date 26/11/2011

I decided to by on a twitter also (now posts only in Russian, but who knows :) )

oseledetsivan

Tensor-Train decomposition paper finally published!

Date 26/09/2011

Finally, after more than 2 years of reviewing process, the basic paper on the TT-format is published in SISC!

You can get the journal version here or directly at the SIAM website

The first text was based on the paper “Compact matrix form of the d-dimensional tensor decomposition”. However …

Solution of linear systems in the TT-format

Date 05/05/2011

The new paper, S.V. Dolgov, I.V. Oseledets, Solution of linear systems and matrix inversion in the TT-format describes a DMRG-type method for the solution of linear systems with both the matrix and the tensor in the TT-format. The method is able to solve certain structured …

TT-Toolbox 2.1

Date 04/05/2011

TT-Toolbox 2.1 is released. It contains several bug fixes. My great thanks to Sergey Dolgov for writing many important routines and to Vladimir Kazeev for providing his code for the construction of the QTT-representation of discrete Laplace operator (it can be done for extremely high dimensions in …

TT-Toolbox 2.0

Date 05/03/2011

New version of TT-Toolbox is released.

TT Toolbox version 2.0 introduces several major innovations compared to version 1.0.

• New classes tt_tensor and tt_matrix, which now represent TT-tensors and TT-matrices.

• Object-oriented approach allowed to overload many standard MATLAB functions, including addition, subtraction,

multiplication by number, scalar …

DMRG+QTT

Date 19/11/2010

DMRG (Density Matrix Renormalization Group) is a very efficient algorithm for computation of low-lying eigenstates of quantum spin systems. QTT (Quantics Tensor Train) consists in tensorization of one-dimensional objects (i.e. vectors of values of function on a grid with 2^d points) into a d-dimensional tensor, and application of …

Tensor Train in a nutshell

Date 02/11/2010

I have written a one-page article that describes vital operations in TT-format. Hope you will find it convincing, that TT-format is indeed a very elegant representation for tensors.

Relation of tensors, quantics TT and wavelet tensor trains

Date 03/10/2010

In our paper Algebraic wavelet transform via quantics tensor train decomposition we show, how quantics tensor train approach, which consists in tensorization of vectors and matrices, can be interpreted as algebraic wavelet transform. Advantages are especially clear for two dimensional functions. Besides new results, this approach, called WTT (wavelet tensor …

Preprint 2010-04: Explicit tensor-train representation of certain functions

Date 28/08/2010

The aim of Preprint 2010-04 is to construct explicit tensor-train representations for certain function-related tensors and vectors, which are constructed on the basis of introduced functional tensor train decomposition.These results are then used to construct explicit quantics tensor train decomposition for polynomial and sine functions.

Krylov methods for tensors

Date 12/04/2010

Using Wedderburn rank-reduction formulae (for reference what is that, please read a nice paper by Gene Golub and Moody Chu) , we managed to create several robust Krylov methods for the approximation of three-dimensional tensors. It is a preprint 2010-1 of Institute of Numerical Mathematics. A new general interpretation is given …

Tensor trees and tensor trains

Date 18/09/2009

In a new paper, we expose connections between tensor networks and recent recursive representations of high-dimensional tensors described by binary tensor trees and based on a sequence of skeleton (dyadic) decompositions for special unfolding matrices for a given tensor.Â Â Â Â  As the main result, we prove that …

Black box cross approximation for multidimensional arrays

Date 23/07/2009

In our new paper, TT cross approximation for multidimensional arrays” a new formula is presented for the recovery of a high-dimensional array from a part of its entries, provided that the array possesses some low-rank structure, namely it has small compression ranks (for example, a tensor of low canonical rank …

TT toolbox

Date 29/05/2009

A first version of TT toolbox for MATLAB is released. It seems to works also under Octave —- through not fully tested. Any comments, suggestions and bug reports are welcome at ivan.oseledets(dog)gmail.com

All basic algorithms are implemented as a set of short MATLAB functions. You can try …

Excluded sums and quasiseparable matrices.

Date 03/05/2009

The idea of Edelman et al. (published in 2005 in SIAM News) for fast evaluation of excluded sums and their relation with the non-recursive multipole method was largely unnoticed. The authors promised to give a new implementation of the multipole method based on their (quite elegant) approach however up to …

Tensors inside of matrices give logarithmic complexity

Date 03/05/2009

The recently intoduced TT-format finds a surprising application for the compression of ordinary “two” or “three” dimensional matrices, related to the discretization of operators on tensor grids. For some examples the complexity is shown to be logarithmic in the matrix order. The new format (named TTM format) can be …

New tensor decomposition

Date 15/03/2009

A new paper, A compact matrix form of the d-dimensional tensor decomposition is added. A new version of the TT (name is now not coming from “Tree Tucker”, but from “Three dimensional Tensors” which are the defining parameters of the format) format is presented, which is much simpler than the …

Breaking the curse of dimensionality

Date 30/01/2009

In our new publication, “Breaking the curse of dimensionality, or how to use SVD in many dimensions” we present a simple recursive decomposition for multidimensional functions, operators, vectors and matrices. We prove that in the case when the canonical decomposition exists our new Tree-Tucker decomposition also exists with the same …

How to find a good submatrix

Date 17/10/2008

Check out ourÂ  new paper, “How to find a good submatrix” . It contains the description of an algorithm to find the well-conditioned submatrix in a given matrix. This algorithm plays a crucial role in our low-rank approximation methods, both for matrices and tensors. [drain file 2 url Matlab code is …

Working with tensor-structured matrices and vectors

Date 01/07/2008

A new publication on tensor-structured matrices, with a tentative title “Linear algebra for tensor problems” is added. It is submitted to the special issue of Computing.

This paper is aboutÂ  structured iterations with matrices of low tensor rank in three dimensions. We show that in three dimensions we can use …

One more paper on polynomials

Date 18/06/2008

Added a paper “Improved n-term Karatsuba formulae in GF(2)” that contains improved (and without proof —- optimal!) formulae for multiplication of binary polynomials in GF(2). As noted in the end of this paper, the goal is not purely theoretic, but also practical —- these optimal formulae will be used for …

Some news

Date 26/05/2008

A new publication has been added. To my knowledge, it is the first paper where nontrivial class of low-tensor rank matrices with inverses also of a low tensor rank is found. This class is also not very small and many useful matrices can be reduced to it.

At present, I …

Contacts

Date 03/04/2008

You can always contact me by email:

ivan.oseledets DOG gmail.com.

Date 03/04/2008

Started the creation

Date 03/04/2008

That is my personal webpage, and I started its creation in April, 2008. Hope it will be interesting to somebody

News

 26/05/2016 A TT-eigenvalue solver that finally works Papers 12/05/2016 Exponential machines and tensor trains Papers 06/04/2016 Convergence analysis of a projected fixed-point iteration Papers 30/03/2016 Compress-and-eliminate solver for sparse matrices Papers 01/12/2015 New paper in SIMAX Papers

Contact

We are located at the 2-nd floor of the new "Technopark-3” building in Skolkovo (few kilometers outside Moscow Ring Road). The building is accessible from Skolkovo Road (Сколковское шоссе) and Minskoe Highway (Минское шоссе).

email: