REVIEW 4 major objections 5 minor 38 references
TT-LSQR For Tensor Least Squares Problems and Application to Data Mining *
T0 review · 4 major / 5 minor · reviewed 2026-08-09 · deepseek-v4-flash
Pith's one-line read A tensor-train reformulation of LSQR solves multiterm tensor least-squares problems without forming Kronecker products, and the paper shows the resulting solver classifies documents and images competitively.
desk verdict A plausible TT-LSQR extension whose truncation step is never shown to track the original least squares problem; worth refereeing, but the reliability claims need support. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the tensor-train (TT) decomposition, which writes a $d$-dimensional tensor as a chain of small cores, $\mathcal{X}(i_1,\dots,i_d)=G_1(i_1)G_2(i_2)\cdots G_d(i_d)$ with $r_0=r_d=1$, so storage scales with the TT ranks instead of with the full multidimensional grid. The algorithm that carries the argument is the LSQR recurrence itself: vectors become tensors, the coefficient operator applies the sum of Kronecker products mode by mode without forming the products explicitly, and TT-SVD rounding after each sum keeps the ranks bounded. Two accelerants complete the machinery: a preconditioner built from the upper-triangular QR factors of selected coefficient matrices, and a randomized sketching operator that projects each mode's matrix onto a much smaller row space, approximately preserving Euclidean distances, before the iteration starts.
What would settle it
On a small instance of the multiterm tensor least-squares problem where the unrounded vectorized LSQR minimizer can be computed exactly, run TT-LSQR with no rounding and with a sequence of looser rounding tolerances; if the rounded solution errors do not tend to the unrounded solution as the tolerance tends to zero, or if the residual stops decreasing at a level inconsistent with the tolerance, the central claim fails.
Extended reading notes
Core claim
On its own terms, the central discovery is that the LSQR recurrence is format-agnostic: replacing the vectors by tensors and the operator by $\mathcal{L}(\mathcal{X})=\sum_i \mathcal{X} \times_1 A_1^{(i)} \cdots \times_d A_d^{(i)}$ yields exactly the same iterates as the vectorized method before any rounding is applied. Because sums of tensor-train tensors have ranks equal to the sum of the addend ranks, the paper applies TT-SVD rounding after each addition and application of $\mathcal{L}$, at the cost of a per-step error controlled by the rounding tolerance. It then shows that this truncated tensor LSQR, optionally preceded by QR-based right preconditioning and applied to a randomized sketch of each mode, solves the multiterm problem and produces classification decisions through two criteria: a direct residual criterion and a subspace-projection criterion built from the singular vectors of the TT-cores. The paper's claim is that this combination is a workable solver and a competitive tool for allocating new documents or images to existing clusters.
Load-bearing premise
The method rests on the assumption that repeatedly compressing the tensor-train representation after each update does not carry the iterates away from the true least-squares solution; the paper validates the per-step truncation error but does not analyze how these errors accumulate over hundreds of iterations.
Editorial extensions
If this is right
- Multiterm tensor least-squares problems with three or more modes become solvable without forming or storing the Kronecker-product coefficient matrix, whose size would be infeasible.
- Truncation gives a controllable trade-off: looser TT rounding tolerances or smaller rank caps make the iterates stagnate at predictable residual levels, matching the behavior known for truncated matrix Krylov methods.
- For fixed total training data, splitting it into more terms $\ell$ with fewer columns $m$ per term lowers CPU time dramatically while keeping classification accuracy roughly constant.
- Sketching the keyword or pixel space cuts CPU time by a large factor, and a short unsketched refinement using the sketched solution as a starting guess often recovers most of the lost accuracy.
- The tensor-based subspace-projection criterion (C2) generally matches or beats simple matrix least-squares query matching, which is unreliable on weakly correlated clusters.
Reading between the lines
- Inference: The format-level nature of the rounding suggests the same tensorized template should transfer to other Krylov iterations, such as CG on the normal equations or GMRES, for sums of Kronecker products; the paper only develops LSQR.
- Inference: The authors mention combining the two classification criteria as future work; a natural test is a voting rule that could stabilize classification on weakly correlated groups such as the Fashion-MNIST sandals class.
- Inference: The sketch is applied per mode with the same sketch size; one could test mode-dependent sketch sizes, since the reported correlation patterns differ markedly across groups and datasets.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes TT-LSQR, a tensor-train implementation of the classical LSQR algorithm for the multiterm tensor least squares problem (1.1), where the coefficient is a sum of Kronecker products of tall matrices. The algorithm applies LSQR recurrences to tensors in TT format and rounds the TT-ranks after each sum. The authors also introduce a sketching variant, discuss preconditioning, and apply the method to query-document classification using two criteria (C1) and (C2) on Reuters, Cranfield, Medline, and FashionMNIST data, comparing against a matrix least squares criterion (C3) and a truncated-SVD projection criterion (C4). The central claim is that TT-LSQR provides an effective, memory-saving solver for (1.1) and that the resulting classification framework is promising.
Significance. If the main claim were fully established, the paper would contribute a practical TT-based solver for a genuinely hard class of multiterm tensor least squares problems, with a plausible application to text and image classification. The algorithmic idea is natural, the use of the TT-Toolbox makes the implementation concrete, and the sanity checks in Section 5 usefully document the effect of rounding and rank truncation. The classification criteria are simple and do not involve fitted parameters beyond the least squares solution. However, the absence of any accumulated perturbation analysis for the repeated rounding in the LSQR recurrence leaves the central numerical claim unproven, and the classification evidence rests on very small test sets. The contribution is therefore best regarded as a promising heuristic numerical study rather than a fully supported solver.
major comments (4)
- [Section 3, Algorithm 3.1] The central load-bearing point is that TT-LSQR solves the original problem (1.1), but the paper only states in Section 3 that after each sum 'some truncation is necessary' and that the iterates coincide with the vectorized case only 'before truncation.' No result controls the cumulative effect of rounding U_{i+1}, V_{i+1}, and X_i at every iteration; Theorem 3.1 bounds only a single TT-SVD rounding step. Once rounding is applied, the scalars alpha_i, beta_i, rho_i, and theta_i no longer describe a fixed linear operator, so the classical LSQR convergence theory of [32] does not apply, and the method may converge to a tolerance- and rank-dependent problem rather than to the minimizer of (1.1). Please provide an accumulated perturbation bound, a low-rank representability condition on the true minimizer, or explicitly reframe the contribution as a heuristic rank-constrained solver with empirical validation only.
- [Section 5, Figure 5.1] The sanity check on the discretized PDE reports only relative residual norms and shows that stagnation is controlled by the truncation threshold. This does not establish that the computed iterates are close to the true solution of (5.1) or to the least squares minimizer of the original problem, since the residual may stagnate at a nonzero value for a different rounded problem. Please include an error measure against the exact solution or against an unconverged reference solution of the full problem, and report the TT-ranks achieved during the iterations.
- [Section 7.2, Tables 7.1-7.4] The classification experiments use 20 test documents per category (40 for FashionMNIST), and the authors themselves note that a 5% difference is a single document. Consequently, many of the reported differences between criteria (C1) and (C2) or between values of bar m are not statistically meaningful, and several claims such as 'a general preference of criterion (C2) over (C1)' are not supported at this granularity. Please provide confidence intervals, repeated train/test splits, or larger test sets, and restrict the qualitative conclusions to differences that survive this uncertainty.
- [Section 4.2, Eq. (4.1)] The sketching construction is not fully specified. If bA_j^{(i)} = S(A_j^{(i)}) with S: R^n -> R^s, then the sketched Kronecker factor has s^d rows, while S(f) as defined maps a single mode to length s; the notation in (4.1) is therefore ambiguous unless S is applied modewise to the whole tensor F. In addition, the chosen sketch dimension s = 2d bar m is far below the s ~ n log n / epsilon^2 required by the cited Johnson-Lindenstrauss bound, so that bound does not justify the reported accuracy. Please define the action of S on f explicitly, justify the sketch dimension, and report the relative residual of the original (unsketched) problem for the sketched solutions.
minor comments (5)
- [Section 8] The sentence 'the conclusions are drown' contains a typo; it should read 'drawn.'
- [Section 7.1, Criterion (C1)] The notation in Criterion (C1), in particular the expression '1 (x)_j f (x) 1' and the accompanying footnote, is unclear as printed; please define the positioning of f in the Kronecker product with a concrete formula.
- [Section 3.1, Theorem 3.1] The theorem is cited as [30], which is the TT-cross paper by Oseledets and Tyrtyshnikov, whereas the stated TT-SVD error estimate is usually attributed to [28]; please verify and correct the citation.
- [Table 7.5] For the case ell = 3 the table reports results on only 10 test documents while the other rows use 20 documents; this difference should be stated directly in the table caption or in the surrounding text, since it affects the interpretability of the CPU-time comparison.
- [Section 3, code availability] The text says the code 'will be made available' at a GitHub repository, but no repository link or release is provided; please include the link or state clearly that the code is available upon request.
Circularity Check
No significant circularity: TT-LSQR is an independent algorithmic adaptation, and the truncation gap is a correctness concern, not a definitional reduction.
full rationale
The paper's central claim is an algorithmic implementation (TT-LSQR) plus experimental classification criteria. The derivation chain is: vectorized LSQR, tensor-reshaped iteration, TT rounding after each sum, and classification criteria C1/C2. None of these steps reduces to its own input by construction. The statement that iterates before truncation coincide with vectorized LSQR is true by the mode-product/Kronecker correspondence, and the paper explicitly acknowledges that truncation changes the iterates ('some truncation is necessary'), so no prediction is disguised as a fit. Theorem 3.1 bounds a single TT-SVD rounding and is cited from Oseledets and Tyrtyshnikov; it is external and not a self-citation. The only same-author citation, [34] (matrix truncated LSQR), is used as a template and comparison method, but the tensor implementation and the classification experiments are self-contained and tested against external benchmarks; no load-bearing theorem is imported by self-citation. The lack of an accumulated perturbation bound for repeated rounding is a genuine mathematical gap in the paper's convergence theory, but a gap is not circularity: the algorithm's output is not defined to be the classification result, and criteria C1/C2 are evaluated rather than fitted. Accordingly, score 0.
Assumptions & free parameters
free parameters (6)
- TT rounding tolerance =
10^-4 in classification; 10^-9, 10^-7, 10^-5, 10^-3 in PDE tests
- Number of TT-LSQR iterations =
10 for classification; 200-600 for PDE tests
- Sketching dimension s =
s = 2*d*bar_m
- Max TT-rank used in rounding =
20, 30, 40, 50 in PDE experiments
- Number of terms ell and number of modes d =
ell = 6, d = 3
- Number of singular triplets in baseline C4 =
10
assumptions (4)
- standard math TT-SVD truncation error bound (Theorem 3.1)
- domain assumption Rounding at each TT-LSQR iteration preserves a meaningful approximation of the least squares solution
- ad hoc to paper The tensor model with F = f tensor f tensor f and partitioned term-document matrices is a valid representation for query classification
- domain assumption The mode-wise preconditioner chosen as the R factor with lowest condition number is effective for the whole multiterm problem
Cite this review
Pith. "Pith review of TT-LSQR For Tensor Least Squares Problems and Application to Data Mining *." pith.science (2026). https://pith.science/paper/7PIQVCC6
@misc{pith2026250201293,
author = {Pith},
title = {Pith review of: TT-LSQR For Tensor Least Squares Problems and Application to Data Mining *},
year = {2026},
howpublished = {\url{https://pith.science/paper/7PIQVCC6}},
note = {Machine review of arXiv:2502.01293}
}
abstract
We are interested in the numerical solution of the tensor least squares problem \[ \min_{\mathcal{X}} \| \mathcal{F} - \sum_{i =1}^{\ell} \mathcal{X} \times_1 A_1^{(i)} \times_2 A_2^{(i)} \cdots \times_d A_d^{(i)} \|_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.
Figures
Reference graph
Works this paper leans on
-
[32]
C. C. Paige and M. A. Saunders, LSQR: An algorithm for sparse linear equations and sparse 20 least squares, ACM Transactions on Mathematical Software (TOMS), 8 (1982), pp. 43–71
work page 1982
-
[1]
R. D. Algarte, Tensor-based foundations of ordinary least squares and neural network regres- sion models, 2025
work page 2025
-
[2]
A. H. Bentbib, A. Khouia, and H. Sadok, The LSQR method for solving tensor least-squares problems, Electronic Transactions on Numerical Analysis, 55 (2022), pp. 92–111. 19
work page 2022
-
[3]
M. Benzi and M. Tuma , A robust preconditioner with low memory requirements for large sparse least squares problems , SIAM J. on Scientific Computing, 25 (2003), pp. 499–512
work page 2003
-
[4]
M. W. Berry and M. Browne , Understanding Searching Engines , Software, Enviroments, and Tools, SIAM, Philadelphia, USA, 1999
work page 1999
-
[5]
M. Bouss´e, N. Vervliet, O. Debals, and L. De Lathauwer, Face recognition as a Kronecker product equation, in IEEE 7th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP), Dec. 2017, pp. 1–5
work page 2017
-
[6]
D. Brandoni and V. Simoncini , Tensor-train decomposition for image recognition , Calcolo, 57 (2020). article # 9
work page 2020
- [7]
Show all 38 references
-
[8]
Chang and H.-C
S.-Y. Chang and H.-C. Wu , Tensor-based least-squares solutions for multirelational signals and applications, IEEE Transactions on Cybernetics, 54 (2024), pp. 2852–2865
2024
-
[9]
Chen and D
M. Chen and D. Kressner , Recursive blocked algorithms for linear systems with Kronecker product structure, Numerical Algorithms, 84 (2020), pp. 1199–1216
2020
-
[10]
C. F. Dantas, J. E. Cohen, and R. Gribonval , Learning tensor-structured dictionaries with application to hyperspectral image denoising , in 27th European Signal Processing Confer- ence, EUSIPCO 2019, A Coru˜ na, Spain, September 2-6, 2019, IEEE, 2019, pp. 1–5
2019
-
[11]
C. F. Dantas, M. N. Da Costa, and R. da Rocha Lopes , Learning dictionaries as a sum of Kronecker products, IEEE Signal Processing Letters, 24 (2017), pp. 559–563
2017
-
[12]
De Lathauwer, B
L. De Lathauwer, B. De Moor, and J. V andewalle , A multilinear singular value decom- position, SIAM J. on Matrix Analysis and Applications, 21 (2000), pp. 1253–1278
2000
-
[13]
S. V. Dolgov and D. V. Savostyanov, Alternating minimal energy methods for linear systems in higher dimensions, SIAM Journal on Scientific Computing, 36 (2014), pp. A2248–A2271
2014
-
[14]
Eld ´en, Matrix methods in Data Mining and Pattern Recognition , Fundamentals of Algo- rithms, SIAM, Philadelphia, USA, 2019
L. Eld ´en, Matrix methods in Data Mining and Pattern Recognition , Fundamentals of Algo- rithms, SIAM, Philadelphia, USA, 2019. II ed
2019
-
[15]
Hackbusch, B
W. Hackbusch, B. N. Khoromskij, and E. E. Tyrtyshnikov, Hierarchical Kronecker tensor- product approximations, J. Numer. Math., 13 (2005), pp. 119–156
2005
-
[16]
N. Hao, M. E. Kilmer, K. Braman, and R. C. Hoover, Facial recognition using tensor-tensor decompositions, SIAM J. on Imaging Sciences, 6 (2013), pp. 437–463
2013
-
[17]
G. W. Howell and M. Baboulin, LU preconditioning for overdetermined sparse least squares problems, in Parallel Processing and Applied Mathematics, R. Wyrzykowski, E. Deelman, J. Dongarra, K. Karczewski, J. Kitowski, and K. Wiatr, eds., Cham, 2016, Springer Inter- national Publ...
2016
-
[18]
Jiang, F
B. Jiang, F. Yang, and S. Zhang , Tensor and its Tucker core: the invariance relationships , Numerical Linear Algebra with Applications, 24 (2017), p. e2086
2017
-
[19]
R. A. Johnson and D. W. Wichern, Applied multivariate statistical analysis, Pearson Prentice Hall, NJ, 2007
2007
-
[20]
Kernfeld, M
E. Kernfeld, M. Kilmer, and S. Aeron, Tensor-tensor products with invertible linear trans- forms, Linear Algebra Appl., 485 (2015), pp. 545–570
2015
-
[21]
B. N. Khoromskij , Tensors-structured numerical methods in scientific computing: survey on recent advances, Chemometrics and Intelligent Laboratory systems, 110 (2012), pp. 1–19
2012
-
[22]
, Tensor Numerical Methods in Scientific Computing , De Gruyter, Berlin, Boston, 2018
2018
-
[23]
T. G. Kolda and B. W. Bader , Tensor decompositions and applications , SIAM Review, 51 (2009), pp. 455–500
2009
-
[24]
Kressner and C
D. Kressner and C. Tobler, Krylov subspace methods for linear systems with tensor product structure, SIAM J. Matrix Anal. Appl., 31 (2010), pp. 1688–1714
2010
-
[25]
Kressner and C
D. Kressner and C. Tobler , Low-rank tensor Krylov subspace methods for parametrized linear systems, SIAM. J. Matrix Anal. & Appl., 32 (2011), pp. 1288–1316
2011
-
[26]
Martinsson and J
P.-G. Martinsson and J. A. Tropp , Randomized numerical linear algebra: Foundations and algorithms, Acta Numerica, 29 (2020), p. 403–572
2020
-
[27]
Meier, Y
M. Meier, Y. Nakatsukasa, A. Townsend, and M. Webb , Are sketch-and-precondition least squares solvers numerically stable? , SIAM J. on Matrix Analysis and Applications, 45 (2024), pp. 905–929
2024
-
[28]
Oseledets, Tensor-train decomposition, SIAM J
I. Oseledets, Tensor-train decomposition, SIAM J. Scientific Computing, 33 (2011), pp. 2295– 2317
2011
-
[29]
Oseledets, TT-Toolbox, 2025
I. Oseledets, TT-Toolbox, 2025. https://github.com/oseledets/TT-Toolbox
2025
-
[30]
Oseledets and E
I. Oseledets and E. Tyrtyshnikov , TT-cross approximation for multidimensional arrays , Linear Algebra and its Applications, 432 (2010), pp. 70–88
2010
-
[31]
I. V. Oseledets and S. V. Dolgov , Solution of linear systems and matrix inversion in the TT-format, SIAM Journal on Scientific Computing, 34 (2012), pp. A2718–A2739
2012
-
[33]
Palitta and V
D. Palitta and V. Simoncini, Matrix-equation-based strategies for convection–diffusion equa- tions, BIT Numerical Mathematics, 56 (2016), pp. 751–776
2016
-
[34]
Piccinini and V
L. Piccinini and V. Simoncini, Truncated LSQR for Matrix Least Squares Problems, To appear in Computational Optimization and Applications (COAP), (2025), pp. 1–22
2025
-
[35]
Rokhlin and M
V. Rokhlin and M. Tygert , A fast randomized algorithm for overdetermined linear least- squares regression, Proc. Natl. Acad. Sci. USA, 105 (2008), pp. 13212–13217
2008
-
[36]
N. A. Saputra, L. S. Riza, A. Setiawan, and I. Hamidah , A systematic review for classifi- cation and selection of deep learning methods , Decision Analytics Journal, 12 (2024)
2024
-
[37]
Simoncini, Numerical solution of a class of third order tensor linear equations , Bollettino UMI, 13 (2020), pp
V. Simoncini, Numerical solution of a class of third order tensor linear equations , Bollettino UMI, 13 (2020), pp. 429–439
2020
-
[38]
D. P. Woodruff , Sketching as a tool for numerical linear algebra , Found. Trends Theor. Comput. Sci., 10 (2014), pp. 1–157. 21
2014
Reviewed August 9, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.