Reviews: On Tensor Train Rank Minimization : Statistical Efficiency and Scalable Algorithm

The authors propose two algorithms for fitting low-rank tensor-train (TT) decompositions using the Schatten TT norm as the low-rank inducing regularizer. The first (TT-ADMM) uses ADMM with the optimization variable being the tensor itself--- this has exponential space and time complexities. The second (TT-RALS) reduces these complexities to polynomial by optimizing in an alternating fashion (using ADMM) over the factors in a TT factorization of the tensor, and using randomized dimensionality reduction to estimate the Schatten TT norm. Theoretical analysis is provided to argue that: under some regularity conditions (incoherence) the matrix estimate obtained by TT-ADMM is consistent, and if the initial guess is close enough to the optimal point, TT-RALS is also consistent. Quantitative rates of convergence are provided.