Assume that $\mathbf{A}_{M\times N}$ is a sparse complex matrix. Then, what is the complexity of computation of its pseudo inverse, i.e., $$\mathbf{A}^{\mathrm{H}}(\mathbf{A}\mathbf{A}^{\mathrm{H}})^{-1}.$$ For a usual $\mathbf{A}$ (not sparse), the complexity of computation is $$\alpha_1 N M^{\nu-1}+\alpha_2 M^{\nu}+\alpha_3 M^2 N^{\nu-2},$$ where $2.37 \leq\nu\leq 3$.
Assume that $\mathbf{A}$ is sparse in a way that $\mathbf{A}\mathbf{A}^{\mathrm{H}}$ is also sparse. Is it better for the sparse case?
