8
$\begingroup$

I have some vector $V$ which can be decomposed into the eigenspace of the hermitian sparse operator $M$:

$V = \sum_i v_i \hat{m}_i$

Is there a way to find the $\hat{m}_i$ (the eigenvector itself) that correspond to the largest $v_i$ (in magnitude)?

I essentially want the largest few terms of the sum, including the eigenvectors of $M$, which I don't know ahead of time.

Specifically, I want to simultaneously find the eigenvectors of $M$ that correspond to the largest $|v_i|$, along with finding the largest $v_i$. Preferably without finding the entire spectra of $M$ first.

Some possibilities that I have been thinking about:

We can "inflate" the matrix using the opposite of "Wieldant's Deflation":

$M_1 = M + \sigma \left[ \Sigma_i v_i \hat{m}_i \right] V^H = M + \sigma V V^H$

The eigenvalues for different $\hat{m}_i$ are shifted $\lambda_i + \sigma |v_i|^2$. I believe we can then extract $\sigma$ and $v_i$ because the eigenvectors don't change. The problem is that the outer product of $V$ is dense.

another possibility:

The power method (keep multiplying $M$ by our vector $V$ until the convergence) finds the component of $V$ with the largest eigenvalue. The downside of this method is that we don't control for the magnitude of $v_i$, so we would end up finding ALL the components, and then finding the largest.

Is there some way to control this so that we only converge on the largest component?

$\endgroup$
  • $\begingroup$ I'm thinking real-world so I'm thinking it requires stochastic simulation. You have a vector and you want to find its place in a subspace. The subspace is spanned by the eigenvectors. The trick is, you don't have all the eigenvectors, only some of them. You can use the dot product to see which ones of the eigenvectors you have contribute to the vector or vectors that you have. If you are lucky then you could span your vector with a subset of the eigenvectors. If not then you can decompose your vector in terms of the eigen-vectors that you do have, and find vector/s that you do not. $\endgroup$ – EngrStudent - Reinstate Monica Mar 10 '15 at 10:43
  • $\begingroup$ Please see scicomp.stackexchange.com/questions/28111/… for a solution! I have added some details of the solution to the question. $\endgroup$ – as2457 Jan 31 at 8:03
1
$\begingroup$

Since the matrix is hermitian, you could use it as a hamiltonian to propagate it in imaginary time. That is, solve the following system of differential equations:

$$ i\frac{d \vec{V}}{dt}=M\vec{V}$$

The general solution to this is:

$$ V(t)=V_0e^{iMt}$$

Then you take your $\vec{V(t)} \cdot \vec{V(0)}$, fourier transform it, and the height and placement of the peaks will tell you the components along various eigenvectors and their associated eigenvalues. This is sometimes called "the spectral method" in ultrafast atomic physics.

Once you have the eigenvalues, find the eigenvectors with whatever specific-eigenvalue solver you prefer.

$\endgroup$
  • $\begingroup$ Can you recommend a textbook, lecture notes or any source which contains an introduction into this "spectral method"? Google search did not really provide satisfactory results for me. $\endgroup$ – Marco Breitig Apr 15 '15 at 12:24
  • $\begingroup$ @Marco Breitig: I've never been able to find one either. It's just part of the oral tradition of atomic physics, I suppose. $\endgroup$ – Dan Apr 15 '15 at 21:16
0
$\begingroup$

Sure. Let $\hat{M}$ be a matrix such that each column is a distinct eigenvector of the Hermitian operator $M$; it follows from the Hermiticity of $M$ that $\hat{M}$ is invertible. To obtain the $v_{i}$, solve the linear system $\hat{M}v = V$. Then, select the index $i$ such that $\max_{j}|v_{j}| = |v_{i}|$; the $i$th column of $\hat{M}$ will the eigenvector corresponding to the largest $v_{i}$ in magnitude.

$\endgroup$
  • 1
    $\begingroup$ Sorry, I wasn't clear. I know I can just calculate every eigenvector and get the answer that way, but I JUST want the eigenvectors corresponding to the largest components of $V$. If possible, I would like to avoid calculating all the eigenvectors and then figure out which components are the largest. $\endgroup$ – Andrew Spott Dec 12 '14 at 4:00
  • 2
    $\begingroup$ @AndrewSpott: Add that requirement to your question. Finding eigenvectors given eigenvalues (or finding one for a maximal magnitude eigenvalue) is straightforward. Finding a best low-rank approximant in terms of a given basis is also straightforward. However, here, you have to solve for an eigenbasis and simultaneously find a best low-rank approximant. It might be doable, but no algorithm immediately comes to mind. $\endgroup$ – Geoff Oxberry Dec 12 '14 at 7:13
  • $\begingroup$ is it more clear now? $\endgroup$ – Andrew Spott Dec 12 '14 at 20:01

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.