>Thank you for the detailed answers and clarifications. It will be beneficial to include many of the clarifications in revised versions of the manuscripts.
Thank you again for you review and questions. We will include all the points mentioned in our rebuttal in the revisions which will improve the clarity.
> However, let me followup the discussion on Chen et al. 2023. I see your point. However, note that Thm 4.4 in Chen et al. 2023 gives exact constants (no O() expression) and this is where the 3^q comes from. In contrast, your results is J=O(R^2/(\eps * \delta)) where the constant is unclear. For all I know, the O() hides a 3^q constant! So: if you flesh out the constant, do you really do not have any dependence on the tensor order?
There is no hidden dependency on the tensor order in the big O.
In Corollary 4.4, the number of samples required for each least square problem, J=O(R^2/(\eps * \delta)), is independent on the tensor order N (N is not hidden in the constant). Thus, for one sweep of the ALS algorithm, the complexity is linear in the tensor order, as stated in the second part of the corollary (i.e. the overall ALS complexity is O(#it εδ R^4 N \sum_{j=1^N} (log I_j + I_j), where N is the order of the tensor). We will clarify this point in the revision.
> even if we accept that there is a theoretical advantage in the form of a dependence of the order, this does not necessarily tell the whole story for a small q (where typically q=3 is the most common use-case). In fact, if q is fixed to 3, then 3^q is now a constant, and it really matters how it compares the constant of the your algorithm.
We agree that if q is treated as a constant, then the asymptotic complexity is the same. However, we believe that designing an algorithm with only a linear dependency on the order, instead of the exponential one given in Chen et al, constitute a non-trivial contribution and advancement compared to Chen et al. In addition, the TT decomposition is particularly suited and relevant for (very) high order tensors where the tensor order cannot be treated as constant (as demonstrated by its uses in quantum physics for simulating many-body systems where the order corresponds to the number of particles in the system).
> I still hold that Chen et al. 2023 is the most appropriate empirical baseline, and without it the empirical evaluation is lacking.
Unfortunately, the lack of a publicly available code for the method presented in (Chen et al, 2023) did not allow us to include it in the synthetic experiment. Moreover, to the best of our understanding, the method proposed by Chen et. al could not scale to the size of the tensors that we consider in the large sparse tensors experiments.