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<m<\infty$ 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!

  • 3
    $\begingroup$ 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. $\endgroup$ Jun 21 at 19:59
  • 2
    $\begingroup$ $X$ is too large to fit into memory, so update is typically performed by using a random subset of $k$ rows during each step $\endgroup$ Jun 21 at 20:02
  • 2
    $\begingroup$ 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 $\endgroup$ Jun 21 at 20:21
  • $\begingroup$ 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. $\endgroup$
    – PC1
    Jun 22 at 20:56
  • 1
    $\begingroup$ 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 $\endgroup$ Jun 23 at 3:52


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.