With some further derivations, we can show that the algorithm only requires O(nnz(A) + nk) time to update each column, 5 so the overall complexity is O(nnz(A)k + nk 2 ) time per epoch, which is only proportional to number of nonzero terms in A.
with the same time complexity as GloVe, we can utilize the information from all the zero entries in A instead of only sub-sampling a small set of zero entries.