For comparisons, the complexity of three state-of-the-art algorithms, namely, Bernoulli-Gaussian generalized approximate message passing (BG-GAMP) [1]}, orthogonal matching pursuit (OMP) [2]}, turbo compressive sensing (Turbo-CS) [3]} and sparse Bayesian learning (SBL) [4]}, are provided in Table REF . In BG-GAMP, each element of \(\mathbf {\zeta }\)  has its own \(\nu \)  instead of a shared \(\nu \)  for each row in Algorithm REF , then steps 11-12 are ignored. In OMP, for obtaining the possible non-zero indices the main complexity comes form calculating the product between each column of \(\mathbf {Z}\)  and each column of \(\mathbf {Y}\)  resulting in \(\mathcal {O}((N_\mathrm {r}N)^2M)\)  per iteration. The main computational costs in both Turbo-CS and SBL lie in the matrix inversions and matrix multiplications, which are \(\mathcal {O}((N_rN)^3)\)  and \(\mathcal {O}((N_\mathrm {r}N)^2UQM)\)  per iteration, respectively.
<TABLE>