1
$\begingroup$

(cross-posted on crossvalidated)

For random variable $(x,y)$ in $\mathbb{R}^{d}\times \mathbb{R}^{d}$ and vector $v \in \mathbb{R}^d$, I need to perform the following matrix vector multiplication.

$$T(v)=E[xy']v$$

The issue is that the expected matrix $E[xy']$ is too large to represent in memory ($d\approx $1 million), so I can only afford to store $O(d)$ worth of statistics and perform $O(d^{1.5})$ worth of operations. Three such statistics are $E[x]$, $E[y]$ and $E[x\odot y]$, where $\odot$ refers to element-wise multiplication.

If I only had the first two, one could argue that the following modification of $T$ is appropriate, representing an unbiased guess subject to these constraints

$$T(v)\approx E[x]E[y']v$$

What's an appropriate way to incorporate $E[x\odot y]$?

$\endgroup$
  • $\begingroup$ In your first line, I think it would be easier to read if you wrote $(x,y)\in{\mathbb R}^d\times {\mathbb R}^d$. $\endgroup$ – Wolfgang Bangerth Sep 24 '20 at 16:26
  • 1
    $\begingroup$ Sometimes the idea is that you would not store the matrix in memory, but perform the product "online" as data are received. I would suggest to specify better the problem, to understand if this is feasible: how many samples do you have? do they arrive sequentially on your computer? When is $v$ known? How many such vectors $v$ do you have? $\endgroup$ – Federico Poloni Sep 24 '20 at 17:11
  • $\begingroup$ It's stochastic power iteration -- a single $v$ being multiplied by estimates of $E[x],E[y]$, etc coming from a distributed system. I think the question comes down to -- should knowledge of $E[x\odot y]$ affect an existing estimate of off-diagonal elements? It feels like it shouldn't. But if $E[x\odot x]$, were thrown into the mix, then maybe it would affect it. So wondering about the generic way to handle such partial constraints $\endgroup$ – Yaroslav Bulatov Sep 24 '20 at 17:24

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.