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?

Improve this question
$\endgroup$
5
  • 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, 2014 at 14:01
  • 1
    $\begingroup$ You may benefit from "random sampling" of $A$... $\endgroup$
    – Suvrit
    Sep 28, 2014 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, 2014 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, 2014 at 13:54
  • $\begingroup$ Hi Richard. That's very interesting, I'm eager to read your answer! $\endgroup$
    – gboukensha
    Oct 29, 2014 at 14:24

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ "Following work" missing. $\endgroup$
    – Federico Poloni
    Sep 28, 2014 at 19:28
  • $\begingroup$ :-) --- I mean: "by following the work related to" $\endgroup$
    – Suvrit
    Sep 28, 2014 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, 2014 at 16:02

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.