That's not actually true. The matrix they're talking about inverting here is actually just a square matrix of 8x8 or 128x128 (in their graphed example) to solve

That's not actually true. The matrix they're talking about inverting here is actually just a square matrix of 8x8 or 128x128 (in their graphed example) to solve the alternating least squares problem, in the paper you linked. What you do is for each user, sum up the vectors of items they 'used', and the outer product of each item vector with itself, and solve a straightforward linear algebra equation. Then you flip it around and sum up the new user vectors and their outer products for each item. And alternate. And so yeah, you don't need to invert the matrix, you use a Cholesky decomposition or something similar as it's guaranteed to be positive definite.