Learning matrices B s and B t takes O(m 2 × n s ) and O(m 2 × n t ) operations per iteration.
in real applications, we have k m. the overall complexity of the algorithm, dominated by computation of matrices B s and B t , is O(m 2 × n) where n = max(n s , n t ).