Each of the N data points is processed through several expensive linear algebra operations. O(N * k) just expresses that if you double N, the runtime also at most doubles. It doesn't mean it has to be fast in an absolute sense for any particular value of N and k.

Didn't read TFA, but it's hard to think of a linear algebra operation that is both that slow and takes time independent of n and k.