Saturday, September 22, 2012

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

and several attendant papers:

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

Thanks Laurent for bringing this to my attention.

No comments: