I'm analyzing a large problem with a large $N \times M$ data matrix $A$, where $N$ is the number of observations, $M$ is the number of explanatory variables, and $N \gg M$. I'd like to perform single-pass linear regression on this data set against a scalar response variable. But the challenge is that I'm only able to load $1 \times M$ columns of $A$ at a time (and loading row-by-row is not possible for this problem).

So the question is, is there some way to compute $A^T A$ for linear regression using less than $O(NM)$ memory by loading columns of $A$ at a time?

Edit: Thanks for your interest. I'm looking for an efficient algorithm that makes a single pass through the data. I'd like to compute $A^T A$ exactly if possible.

Each column contains 200 million rows and is stored in separate compressed files that disallow partial read. Production system needs the data in this format. There are 60 thousand columns. The data is on a storage server, and it takes 10 seconds to load one column on a compute server in the same data center and a week to make a single pass through the data. Each compute server has 1 TB of memory. I'm currently working in parallel batches of 2 M rows.

  • 1
    $\begingroup$ Of course: with a vector $x$ in RAM, accumulate the values of $y_i$ and $y_ix_i$ as you read in the vector $y.$ Repeat for all entries of $A^\prime A.$ Indeed, you only need $O(M^2)$ RAM if you're willing to read the columns an average of $(M+3)/2$ times each. $\endgroup$ – whuber Sep 6 '18 at 19:48
  • $\begingroup$ It's not clear to me what you mean by "I'm only able to load $1 \times M$ columns of $A$"? Evidently you don't mean "I can load all $M$ columns of $A$"... And why would loading row-by-row not be possible? $\endgroup$ – jbowman Sep 7 '18 at 2:37
  • $\begingroup$ Please register &/or merge your accounts (you can find information on how to do this in the My Account section of our help center), then you will be able to edit & comment on your own question. $\endgroup$ – gung Sep 7 '18 at 13:13

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.