# Compute only selected components of an eigenvector

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?

• What is your goal here? What are you trying to achieve that doesn't work with the usual large-scale eigenvalue algorithms? – Federico Poloni Sep 28 '14 at 14:01
• You may benefit from "random sampling" of $A$... – Suvrit Sep 28 '14 at 16:01
• 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$. – gboukensha Sep 29 '14 at 15:56
• 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. – Richard Zhang Oct 28 '14 at 13:54
• Hi Richard. That's very interesting, I'm eager to read your answer! – gboukensha Oct 29 '14 at 14:24

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.