We now analyze the time complexity of the above algorithm.
The computational complexity is mainly contributed by the updates of \(\mathbf {u, h, d}\) , and \(\mathbf {Z}\) .
Note that the update of \(\mathbf {u}\)  can be simplified by avoiding unnecessary matrix multiplications.
In (REF ), the calculation of \(\Psi ^{-1}\)  is independent of the input and thus can be cached before the iteration.
The adjoint operator \(T^*(\cdot )\)  is essentially an “extract and sum" operator, where each output element of \(T^*(\cdot )\)  is the sum of multiple specific elements of the input, whose indices can also be cached before the iteration.
Therefore, the time complexity of the update of \(\mathbf {u}\)  can be reduced to \(O(N_u)\)  (the multiplication of an \(N_u \times N_u\)  diagonal matrix \(\Psi ^{-1}\)  and an \(N_u\) -dimensional vector \(T^*(\cdot )\) ).
The update of \(\mathbf {h}\)  has time complexity of \(O(N^3)\)  due to the matrix inversion \((\mathbf {F}^\mathrm {H} \mathbf {F} + 2\rho \mathbf {I}_{N})^{-1}\) .
The update of \(\mathbf {d}\)  (the LASSO problem) also has time complexity of \(O(N^3)\)  introduced by \(N\) -dimensional matrix inversion [1]}.
The update of \(\mathbf {Z}\)  amounts to eigenvalue decomposition, whose time complexity is upper bounded by \(O(N^3)\) .
Combining the above results, the overall complexity of the proposed algorithm is \(O(N^3)\) .
