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?


$\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


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.