7
$\begingroup$

I am wondering whether it is possible to compute portions of the eigenvectors of a given (possibly very big) matrix. More formally, consider the eigenvalue problem $\mathbf{Ax} = \lambda \mathbf{x}$, where $\mathbf{A}$ is $n \times n$ Hermitian. For a fixed eigenvector $\mathbf{x}$, I am only interested in the values $\mathbf{x}_k$ for some choices of $k \in \{1,\dots,n\}$.

Is it possible to restrict the computation as above? If not, is it possible to obtain an approximate solution, and under which conditions?

$\endgroup$
  • 3
    $\begingroup$ What is your goal here? What are you trying to achieve that doesn't work with the usual large-scale eigenvalue algorithms? $\endgroup$ – Federico Poloni Sep 28 '14 at 14:01
  • 1
    $\begingroup$ You may benefit from "random sampling" of $A$... $\endgroup$ – Suvrit Sep 28 '14 at 16:01
  • $\begingroup$ Thanks a lot for your comments. What I'm trying to achieve here is the computation of the heat kernel for a given point of a 2d compact manifold $M$, restricted to the time domain. In particular, given the eigen-decomposition $\Delta_M \phi = \lambda \phi$ of the Laplace-Beltrami operator $\Delta_M$ on $M$, I'm interested in computing the quantity $\sum_{i=1}^m e^{-\lambda_i t} \phi_i(x)^2$ for a given $x\in M$, $t \in \mathbb{R}$ and $m \in \mathbb{N}$. I need to do it very efficiently, that's why I'd like to compute $\phi_i(x)$ instead of the whole $\phi_i$. $\endgroup$ – gboukensha Sep 29 '14 at 15:56
  • 1
    $\begingroup$ I deleted my prev answer (it didn't answer your question), but I've actually encountered this exact problem before. One can show that the condition you need on $A$ is that it must be well-approximated by a rank-$O(k)$ reduction. I can write out a full answer when I get time. $\endgroup$ – Richard Zhang Oct 28 '14 at 13:54
  • $\begingroup$ Hi Richard. That's very interesting, I'm eager to read your answer! $\endgroup$ – gboukensha Oct 29 '14 at 14:24
4
$\begingroup$

Here is some information that you might find useful. The context is that of PageRank computation, for the purpose of updating only some of ranks (essentially entries of the eigenvector).

  1. Y. Y. Chen, 2004. Local methods for estimating PageRank values
  2. Fast incremental and personalized page rank

In general, chasing references for "incremental" pagerank or just "top few ranks" should help you find more related work and ideas.

Alternatively, you could try to solve the problem approximately by using randomization to subsample the matrix $A$, and then using perturbation analysis to estimate the error of approximation --- some ideas for this can be found by following work related to the so-called "CUR" decomposition.

$\endgroup$
  • $\begingroup$ "Following work" missing. $\endgroup$ – Federico Poloni Sep 28 '14 at 19:28
  • $\begingroup$ :-) --- I mean: "by following the work related to" $\endgroup$ – Suvrit Sep 28 '14 at 22:18
  • $\begingroup$ Thanks a lot for the pointers! I'm going to look into them more in detail and see what I can get out of it. $\endgroup$ – gboukensha Sep 29 '14 at 16:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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