I am reading the following paper:
Big-Align: Fast Bipartite Graph Alignment. Danai Koutra, Hanghang Tong, David Lubensky. International Conference on Data Mining (ICDM 2013).
I'd like to understand one of the paper's claims about the running time of their algorithm. Their algorithm uses matrix multiplication as follows:
where $n \gg d$, $\bf A,B$ are a $n \times d$ matrices, $\bf U$ is a $n\times n$ matrix, and $\bf S$ is a $n\times n$ diagonal matrix with only the first $d$ diagonal elements being non-zero, with $\bf U,S$ derived from $\bf A$ via a SVD decomposition as indicated above. $\bf A$ has rank at most $d$, so there are at most $d$ non-zero singular values in $\bf S$. All matrices contain only non-negative values.
The multiplication of a $l\times m$ matrix and a $m\times n$ matrix take $O(lmn)$ time.
How can we compute $\bf P$ in $O(nd^2)$ time? I think it suffices to compute $\bf B \cdot \bf X$ in $O(nd^2)$ time. I tried different multiplication orders but cannot arrive at a $O(nd^2)$ time complexity. For example,
1) first compute $US^{-1}$, then result is a $n\times n$ matrix with only the first $d$ columns being "non-zero". Since $S$ is diagonal with $d$ non-zero diagonal elements, the time complexity is $O(nd)$.
2) then compute $A^T(US^{-1})$, the result is a $d\times n$ matrix with only the first $d$ columns being "non-zero". The time complexity is $O(nd^2)$.
3) then compute $B(A^TUS^{-1})$, the result is a $n\times n$ matrix with the first $d$ columns being "non-zero". The time complexity is $O(nd^2)$.
4) then compute $S^{-1}U^T$ similar to 1), the result is a $n\times n$ matrix with the first $d$ rows being "non-zero". The time complexity is $O(nd)$.
5) finally the do multiplication $(BA^TUS^{-1})(S^{-1}U^T)$, but this takes $O(n^2d)$ time.
I tried some other order without success to derive $O(nd^2)$ complexity. Am I missing something, or the paper is wrong about this?