Let \(n := \max _k n_k\)  and \(r := \max _k r_k\) . Calculating the Riemannian gradient (REF ) can be split into three steps. We first compute the term \(\left(\mathbf {I}_{n_k}\otimes {{\cal X}_t^{\le k-1}}^\mathsf {T}\right)\left({\cal P}_{\Omega }\left(\phi \left(\bar{{\cal X}}_t\right)\right)-{\cal P}_{\Omega }\left({\cal T}\right)\right)^{<k>}{\cal X}_t^{\ge k+1}\)  which can be done efficiently by exploiting the sparsity of \({\cal P}_{\Omega }\left(\phi \left(\bar{{\cal X}}_t\right)\right)-{\cal P}_{\Omega }\left({\cal T}\right)\) . As shown in [1]}, the computation of this term requires \(O\left(d\vert \Omega \vert r^2\right)\)  floating point operations (flops). Then we form the matrices \(\mathbf {L}_t^k\)  and \(\mathbf {R}_t^k\)  recursively via the equation (REF ) which costs \(O\left(dnr^3 \right)\)  flops, see Algorithm REF . Finally, computing the inverse of \(\mathbf {L}_t^k, \mathbf {R}^k_t\)  and the matrix product requires \(O\left(dnr^3+dr^3 \right)\)  flops. Hence the total cost of computing the Riemannian gradient is \(O\left(d\vert \Omega \vert r^2+dnr^3 \right)\) .
The main computational complexity of calculating the backtracking line search procedure lies in computing the horizontal projection in the RBB step size which requires \(O\left(dnr^6\right)\)  flops to form the coefficient matrix in (REF ) and \(O\left(d^3r^4\right)\)  flops to solve the linear system [2]}. In conclusion, if \(d^2\ll nr^2\) , the total cost of one iteration of RGD (Q) is \(O\left(d\vert \Omega \vert r^2+dnr^6 \right)\) .
[ht!]

Computation of the interface matrix products
 \(\bar{{\cal X}} = \left\lbrace {\cal X}^1,\cdots ,{\cal X}^d\right\rbrace \)  
\(\mathbf {L}^0 = \mathbf {R}^{d+1} = 1\) , \(\mathbf {L}^1 = L\left({\cal X}^1\right)^\mathsf {T}L\left({\cal X}^1\right)\) , \(\mathbf {R}^d = R\left({\cal X}^d\right)R\left({\cal X}^d\right)^\mathsf {T}\) ;
