6
$\begingroup$

Given a matrix $M$ and a vector $v$, is there an efficient method to find the normalized eigenvector of $M$ that is closest to $v$, in that it has maximal overlap. More explicitly, a vector $v$ can be decomposed like so \begin{equation} v = \sum_j \alpha_j u_j, \end{equation} where $u_j$ are the eigenvectors of $M$. I wish to find the subset for which $\alpha_j = v \cdot u_j$ are the largest, without solving the full eigenproblem.

In particular I'm interested in Hermitian matrices, often symmetric and often sparse. By efficient I mean that I should be able to find $R<N$ eigenvectors of an $N \times N$ matrix with the largest overlap with better scaling than diagonalising the full matrix then sorting.

I think this is an interesting question because all algorithms (at least that I know) work by utilising the properties of the dominant eigenvalue - that multiple applications of the matrix projects onto the eigenvector with that eigenvalue. By shifting/inverting it is possible to pick which should be the dominant eigenvalues. It therefore seems that these algorithms fundamentally can't pick out specific eigenvectors only eigenvalues. I am wondering if it is even possible to select a particular eigenvector.

Note that this question has been asked over three years ago on the maths stackexchange and over 2 years ago on this stackexchange, but with no answer:

https://math.stackexchange.com/questions/692468/find-the-eigenvector-with-maximum-overlap,

calculating eigenvector components of a given vector

Solution (added 31 Jan 2019) -------------------------------------------------------------

Thank you to demaregee for pointing me to the paper

https://journals.aps.org/prb/abstract/10.1103/PhysRevB.66.245104

which provides a nice solution to the problem using a variation of the Jacobi-Davidson alogirthm.

The basic idea is to consider instead the projected eigenproblem \begin{equation} V^\dagger M V c = \theta c, \end{equation} where $V$ is an $N\times K$ matrix where the columns are orthonormal vectors which span the "test space", and $u = Vc$ is the approximation of the vector. The problem is then how to choose and update the test space until u converges to the correct eigenvector.

Let $u$ be our current best solution and $V$ our test space. We then solve the correction equation \begin{equation} (M - \theta I) z = -r, \qquad r = (1 - VV^\dagger)(M - \theta I)u, \end{equation} for the correction vector $z$, where $\theta$ is our current approximation of the eigenvalue and $u$ the current approximation of the target vector. We then orthogonalize $z$ to $V$, normalize, and then extend the test space $V \rightarrow [Vz]$.

We then solve the projected eigenproblem and take the solution $u_j = Vc_j$ that has the largest overlap with $v$ as the next approximation to $u$ and update the corresponding eigenvalue $\theta$. We start with the test space being the single vector $V = v$, the vector we want to target and the whole process is repeated until $\|(M - \theta I)u \| < \epsilon$, where $\epsilon$ is our chosen accuracy.

The algorithm can be made more complicated by adding restarts that limit the number of vectors in the test space. We can also target multiple eigenvectors by projecting out all converged vectors from the problem.

$\endgroup$
  • $\begingroup$ Since eigenvectors are only determined up to a sign, when you say "largest $\alpha_j$", I suspect that you mean "largest in magnitude", right? $\endgroup$ – Wolfgang Bangerth Oct 22 '17 at 22:27
  • $\begingroup$ That's correct. $\endgroup$ – as2457 Oct 22 '17 at 22:28
7
$\begingroup$

The following paper suggests that the Jacobi-Davidson method can be used to target eigenvectors based on "any property that can be computed from the eigenvector", which would seem to include overlap with a given vector.

https://journals.aps.org/prb/abstract/10.1103/PhysRevB.66.245104

According to the paper, the key is just to reorder the QR decomposition by your desired property rather than by closeness to a target eigenvalue during each iteration of the Jacobi-Davidson algorithm. Thus, it seems like a minimal modification of existing Jacobi-Davidson codes.

I'm not aware of any codes that support this type of targeting built in, but would be quite interested in implementing/testing one.

$\endgroup$
  • $\begingroup$ I would welcome further answers, as I would like to know more about this target. $\endgroup$ – deemaregee Nov 12 '18 at 21:25
  • 1
    $\begingroup$ From a first glance this sounds perfect, thanks! I'll have a proper read through the paper before accepting your answer. I'll also add an explicit solution to my question if it is simple enough to express. $\endgroup$ – as2457 Nov 14 '18 at 9:21
  • $\begingroup$ Thank you very much! I wasn't able to implement the algorithm exactly as in the paper, but a simplified version works perfectly for my purposes. I'll add the basics of the algorithm to my question. $\endgroup$ – as2457 Jan 31 at 7:34

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.