5
$\begingroup$

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!

Edit Jul 19 crossposted on mathoverflow

Improve this question
$\endgroup$
7
  • 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$
    – Brian Borchers
    Jun 21, 2022 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$
    – Yaroslav Bulatov
    Jun 21, 2022 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$
    – Yaroslav Bulatov
    Jun 21, 2022 at 20:21
  • 1
    $\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, 2022 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$
    – Yaroslav Bulatov
    Jun 23, 2022 at 3:52

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.