2
$\begingroup$

When $x$ is a vector of size Nx1, and $K$ is a very large symmetric sparse matrix of size NxN (say N=100K), is it possible to decompose $x^T K x$ as $y^T y$?

As if I could get $y = K^{1/2} x$.

Edit for more information:

K is a correlation matrix, where only local correlation is assumed. So it is more a band matrix, as the correlation between variables too far away are assumed to be 0, hence the sparse matrix.

Then, I have a model for which $x$ is the solution I get. And I would like to get the contribution of each variable, meaning I would basically like to get the $y_i^2$'s.

Improve this question
$\endgroup$
7
  • $\begingroup$ Does K happen to be positive semidefinite? $\endgroup$
    – eric_kernfeld
    Commented May 27, 2020 at 20:58
  • $\begingroup$ $x^T K x > 0$, but I actually don't know if it would be true for all possible $x$. $\endgroup$
    – F. Privé
    Commented May 27, 2020 at 21:09
  • $\begingroup$ A little extra information could be really helpful to come up with a useful solution. Where does $K$ come from? Why are you doing this? $\endgroup$
    – eric_kernfeld
    Commented May 27, 2020 at 21:44
  • $\begingroup$ @eric_kernfeld Please see my edit. $\endgroup$
    – F. Privé
    Commented May 28, 2020 at 17:03
  • 1
    $\begingroup$ That's interesting and useful. What does your model say? I am wondering about the interpretation of $y$, because it seems like the solution will not be unique. You could potentially get very different conclusions depending on a detail that seems unimportant based on the information provided so far. For instance, Cholesky decomposition as suggested below can be done in many different ways depending on the permutation selected. Another option, eigendecomposition, would give still a different $y$. This really might be unworkable statistically even once you do manage to compute it efficiently. $\endgroup$
    – eric_kernfeld
    Commented May 28, 2020 at 19:18

1 Answer 1

Reset to default
3
$\begingroup$

Cholesky decomposition should work. It will factor $K=LL^T$, similar conceptually to a square root of a matrix. So that $y^T=L^Tx$

There is software that takes advantage of sparsity to compute Cholesky decompositions more economically. For instance, the function Cholesky in the R package Matrix:

http://web.mit.edu/~r/current/arch/i386_linux26/lib/R/library/Matrix/html/Cholesky.html

Improve this answer
$\endgroup$
15
  • 1
    $\begingroup$ Ok, but can I really get a Cholesky decomposition of a matrix that is that large? $\endgroup$
    – F. Privé
    Commented May 27, 2020 at 21:29
  • $\begingroup$ how sparse is your matrix @F.Privé? $\endgroup$
    – Aksakal
    Commented May 27, 2020 at 21:33
  • 1
    $\begingroup$ (+1; $LDL^T$ is the obvious way to go.) @eric_kernfeld: All eigenvalues of a real symmetric matrix are real, by definition $K$ is symmetric so that is covered. Strictly speaking Cholesky does not work for PSD but only for PD. That's why the $LDL^T$. :D $\endgroup$
    – usεr11852
    Commented May 28, 2020 at 0:21
  • 1
    $\begingroup$ @JakeWestfall: Maybe I misunderstand something: 1. $D$ is diagonal... Taking the square root of it is trivial. (And of course, the transpose of the diagonal matrix $D$ is the matrix $D$). 2. A symmetric matrix, $K=K^T$, has only real eigenvalues. Sure, it can be PSD and not only PD but that's why the $LDL^T$. (And of course $L$ does not have to be sparse any more.) Again apologies if I misinterpreter something here; I really value your posts. $\endgroup$
    – usεr11852
    Commented May 28, 2020 at 8:22
  • 1
    $\begingroup$ @eric_kernfeld: If $K$ positive semi-definite, then the pivots are non-negative. $\endgroup$
    – usεr11852
    Commented May 28, 2020 at 13:17

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.