TT-LSQR For Tensor Least Squares Problems and Application to Data Mining *

We are interested in the numerical solution of the tensor least squares problem $$\underset{\mathcal{X}}{\min }\mathrm{\parallel }\mathcal{F}-\sum _{i=1}^{\mathrm{\ell }}\mathcal{X}{\times }_1{A}_1^{(i)}{\times }_2{A}_2^{(i)}\cdots {\times }_d{A}_d^{(i)}{\mathrm{\parallel }}_F,$$ where $\mathcal{X}\in {\mathbb{R}}^{m_1\times m_2\times \cdots \times m_d}$, $\mathcal{F}\in {\mathbb{R}}^{n_1\times n_2\times \cdots \times n_d}$ are tensors with $d$ dimensions, and the coefficients $A_j^{(i)}$ are tall matrices of conforming dimensions. We first describe a tensor implementation of the classical LSQR method by Paige and Saunders, using the tensor-train representation as key ingredient. We also show how to incorporate sketching to lower the computational cost of dealing with the tall matrices $A_j^{(i)}$. We then use this methodology to address a problem in information retrieval, the classification of a new query document among already categorized documents, according to given keywords.