2
$\begingroup$

I have dense $d\times d$ matrices $A$, $B$, $C$ with $d\approx 1000$ and want to find the top $10^5$ eigenvalues of the following positive definite matrix:

$$ \Sigma= \left(\begin{matrix} A\otimes A & C^T\otimes C\\ C\otimes C^T & B\otimes B \end{matrix}\right) $$

  • Cheap: assume $C=0$ and compute $\lambda(A)$, $\lambda(B)$, since $\lambda$ commutes with $\otimes$.

  • Expensive: power method. Storing $10^5$ eigenvectors is 40 GB.

Is there something in between the two?

Motivation

$\Sigma$ is a

  • covariance of $x\otimes x$, where $x$ is a partitioned Gaussian vector with mean 0 and $ E[xx']= \left(\begin{matrix} A&C^T\\ C&B \end{matrix}\right) $
  • Gauss-Newton block for neural network linear layer if we assume forward/backward values are jointly Gaussian
$\endgroup$

0

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.