Sunday Morning Insight: QTT format and the TT-Toolbox -implementation-

It must already be Sunday Morning somewhere. This one has been bugging me for a little while. What is the relationship between

• This question on LinkedIn: Is there a two-dimensional equivalent of compressed sensing?
• The use of Matlab's  reshape function to vectorize images in simple compressive sensing
• Putting in different columns the different frames of a video in order to perform Robust PCA
• Group Sparsity
• Low Rank SVD
• Graph wavelets as dictionaries
• Analysis operator leanring
• Recommender systems
• The need for decomposiing a measurement matrix into a series of matrices with specific features
• hyperspectral measurements
• Super Fast FFTs ?

Those were all issues that popped up on my radar screen this week and I think the beginning of a good answer is the quantized tensor train (QTT) format. Say what now ?

Two presentations might be of interest for a bird's eye view

• Tensor trains, TT and QTT formats by Ivan Oseledets
• Introduction to Tensor Numerical Methods in Scientific Computing by Boris N. Khoromskij

and several attendant papers:

• TT-GMRES: on solution to a linear system in the structured tensor format by Sergey V. Dolgov
• Solution of linear systems and matrix inversion in the TT-format by Sergey Dolgov, and Ivan Oseledets
• Constructive representation of functions in tensor formats by Ivan Oseledets
• Fast solution of multi-dimensional parabolic problems in the TT/QTT-format with initial application to 
  the Fokker-Planck equation by Sergey Dolgov, Boris N. Khoromskij and Ivan Oseledets
• Superfast Fourier Transform Using QTT Approximation by Sergey Dolgov,  Boris N. Khoromskij  and Dmitry Savostyanov.

Let us note that the Full-to-TT compression, the TTε recompression and the TT–rounding algorithms make heavy use of SVD and QR algorithms for matrices.which would seem to be a good candidate for insertion of robust PCA and randomized PCA work. There is also a toolbox to dwell into it:

TT-Toolbox 2.2.


TT-Toolbox (TT=Tensor Train) Ver­sion 2.2
TT(Tensor Train) for­mat is an effi­cient way for low-parametric rep­re­sen­ta­tion of high-dimensional ten­sors. The TT-Toolbox is a MATLAB imple­men­ta­tion of basic oper­a­tions with
ten­sors in TT-format. It includes:

• tt_tensor and tt_matrix classes for stor­ing vec­tors and oper­a­tors
• Basic lin­ear alge­bra sub­rou­tines (addi­tion, matrix-by-vector prod­uct, ele­men­t­wise mul­ti­pli­ca­tion and many oth­ers) using stan­dard MATLAB syn­tax, lin­ear com­plex­ity in the dimen­sion, reshape func­tion
• Fast round­ing pro­ce­dure with a pre­scribed accu­racy
• Advanced approx­i­ma­tion and solu­tion techniques:
• Approx­i­mate solu­tion of lin­ear sys­tems and eigen­value prob­lems
• Cross meth­ods to approx­i­mate “black-box” ten­sors
• Wavelet ten­sor train decomposition
• Con­struc­tion of basic oper­a­tors and func­tions (Laplace oper­a­tor, func­tion of a TT-tensor)
• Com­pu­ta­tion of max­i­mal and min­i­mal ele­ments of a ten­sor and sev­eral others

 New in Ver­sion 2.2

• Bet­ter doc­u­men­ta­tion
• Mixed QTT-Tucker for­mat (qtt_tucker class)
• reshape func­tion for a TT-tensor/TT-matrix
• dmrg_cross method for black-box ten­sor approx­i­ma­tion
• Con­vo­lu­tion in QTT-format

• You can get it here: TT-Toolbox 2.2.

Thanks Laurent for bringing this to my attention.

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.