# Dense least-squares with millions of variables

Suppose $$X$$ is a dense $$m\times n$$ data matrix and we seek to find $$w$$ by approximately iterating least-squares filter equation:

$$w = w - \mu (X'X)^{-1}X'(Xw-b)$$

What are known approaches for $$10^9 and $$n\approx 10^6$$?

This setting comes up in Machine Learning and people tend to invent their own techniques for approximate pseudo-inverse of $$X$$, which in practice has low stable-rank, without referencing scientific computing literature.

For instance KFAC method addresses large $$n$$ by writing $$x\approx a\otimes b$$ and using this factorization to approximate $$(X'X)^{-1}\approx (A'A)^{-1}\otimes (B'B)^{-1}$$. Making this update numerically stable requires considerable tweaking.

Any literature pointers appreciated!

• How do you store the matrix X? It has at least 10^15 elements (m=10^9, n=10^5), so even at half-precision (2 bytes per entry), this would take 2*10^15 bytes or 2000 terabytes (or 4000 terabytes at single precision or 8000 terabytes at double precision.) Your problem is ridiculously over-determined- it would probably make sense to work with a much smaller sample of data. Jun 21 at 19:59
• $X$ is too large to fit into memory, so update is typically performed by using a random subset of $k$ rows during each step Jun 21 at 20:02
• As a concrete example for size, JFT-300m dataset has 300 million example. Taking youtube frames as examples nets trillions of images. Compression and delivery of these datasets involve a lot of engineering Jun 21 at 20:21
• Maybe you can try to factor it (like using a SVD), sometimes only a few factors are needed to provide a good description of the matrix content. But definitely, factoring the matrix $X$ into something simpler is likely needed.
– PC1
Jun 22 at 20:56
• Large $m$ is easy to deal with, just take subset of data and reuse same algs as before. But large $n$ is a problem. I can't SVD the whole thing, so how do I break it into smaller problems? Doing SVD on blocks? Hierarchically? I'm guessing someone has invented algorithms for this scale already, I just need to find their names Jun 23 at 3:52