If we use the retraction defined in (REF ), the main computational complexity of RGN (Q) lies in constructing and solving the problem (REF ). It requires \(O\left(dn^2r^2\right)\)  flops to calculate the matrices \(L\left({\cal X}^k\right)^{\perp }\)  via Householder transformation. To avoid computing \(\mathbf {Q}^{k+1}\) , we can rewrite \(\mathbf {Q}^{k+1}\)  as \({\cal X}^{\ge k+1}{\mathbf {S}^{k+1}}^{-\mathsf {T}}\) . By (REF ), the computation of \(\left\lbrace \mathbf {S}^k\right\rbrace _{k = 2}^d\)  can be implemented recursively which costs \(O\left(dnr^3 \right)\)  flops, see Algorithm REF . The sparsity of \({\cal B}_i\)  implies that calculating \(L\left({\cal X}^k\right)^{\perp }\left(\mathbf {I}_{n_k}\otimes {{\cal X}^{\le k-1}}^\mathsf {T}\right){\cal B}_i^{<k>}{\cal X}^{\ge k+1}\)  costs \(O\left(dr^2+n^2r^3\right)\)  flops. Thus, the total cost
needed for constructing (REF ) is \(O\left(d\vert \Omega \vert n^2r^3+d^2\vert \Omega \vert r^2\right)\)  flops. Since solving  (REF ) costs \(O\left(d^2\vert \Omega \vert n^4r^4\right)\)  flops, the main per iteration cost of RGN (Q) is \(O\left(d^2\vert \Omega \vert n^4r^4\right)\)  flops. For RGN (E), if the retraction in (REF ) is used, the TT-rounding procedure requires \(O(dnr^3)\)  flops [1]} to compute the TT-SVD. Thus,
the leading order per iteration cost of RGN (E) is still \(O\left(d^2\vert \Omega \vert n^4r^4\right)\)  flops.
[ht!]

Computation of \(\left\lbrace \mathbf {S}^k\right\rbrace _{k = 2}^d\)
 \(\bar{{\cal X}} = \left\lbrace {\cal X}^1,\cdots ,{\cal X}^d\right\rbrace \)  
Compute QR decomposition: \(\left[\mathbf {Q}^{d},\mathbf {S}^{d}\right]= \operatorname{QR}\left(R\left({\cal X}^d\right)^\mathsf {T}\right)\) ;
