debugMinor
Rigorous error bounds for eigenvalue solvers
Viewed 0 times
errorsolverseigenvalueforboundsrigorous
Problem
I computed the first four eigenvalues of a quite large ($2^{24}\times 2^{24}$) but very sparse matrix. I used pythons in-build function sparse.linalg.eigsh to compute them.
I need a validation that the results are correct up to an error of at most $10^{-3}$.
Very specifically I want to ask if there is a rigorous error-analysis involving rounding errors up to machine precision in each step.
More generally: Are there other practical algorithms for eigenvalues with such a rigorous error analysis.
I need a validation that the results are correct up to an error of at most $10^{-3}$.
Very specifically I want to ask if there is a rigorous error-analysis involving rounding errors up to machine precision in each step.
More generally: Are there other practical algorithms for eigenvalues with such a rigorous error analysis.
Solution
It might suffice to ask the solver to give you both the eigenvalue $\lambda$ and the corresponding eigenvector $v$. Then you can verify for yourself how much error there is. Note that if $\lambda$ is the eigenvalue corresponding to eigenvector $v$, for matrix $M$, then we have $Mv=\lambda v$. So if you know $M$ and $v$ exactly, and you have a claim that $\hat{\lambda}$ is within $\epsilon$ of the true eigenvalue $\lambda$, it suffices to check that
$$(\hat{\lambda}-\epsilon)v \le Mv \le (\hat{\lambda}+\epsilon)v$$
where $\le$ is to be interpreted separately for each index, i.e., you should check that $(\hat{\lambda}-\epsilon)v_i \le (Mv)_i \le (\hat{\lambda}+\epsilon)v_i$ holds for each index.
If there is some error in the eigenvector $\hat{v}$ returned by the solver, then there is the possibility that the above check might fail, even if $\hat{\lambda}$ is indeed a true eigenvalue of the matrix. I don't know whether there's a nice way to adapt the above calculation to address this issue. If the operator norm $\|M\|_1$ is small, then it might work to check that
$$(\hat{\lambda}-\epsilon)\hat{v}_i -c \le M\hat{v} \le (\hat{\lambda}+\epsilon)\hat{v} + c$$
where $c = \|M - \hat{\lambda} \text{Id}\|_1 \times c'$ and $c'$ is an upper bound on the amount of error in $v$ (measured in $L_1$ distance) that you're willing to tolerate. I'm not sure if this is exactly right; there might be issues in this last criterion, so check it yourself before believing in it.
$$(\hat{\lambda}-\epsilon)v \le Mv \le (\hat{\lambda}+\epsilon)v$$
where $\le$ is to be interpreted separately for each index, i.e., you should check that $(\hat{\lambda}-\epsilon)v_i \le (Mv)_i \le (\hat{\lambda}+\epsilon)v_i$ holds for each index.
If there is some error in the eigenvector $\hat{v}$ returned by the solver, then there is the possibility that the above check might fail, even if $\hat{\lambda}$ is indeed a true eigenvalue of the matrix. I don't know whether there's a nice way to adapt the above calculation to address this issue. If the operator norm $\|M\|_1$ is small, then it might work to check that
$$(\hat{\lambda}-\epsilon)\hat{v}_i -c \le M\hat{v} \le (\hat{\lambda}+\epsilon)\hat{v} + c$$
where $c = \|M - \hat{\lambda} \text{Id}\|_1 \times c'$ and $c'$ is an upper bound on the amount of error in $v$ (measured in $L_1$ distance) that you're willing to tolerate. I'm not sure if this is exactly right; there might be issues in this last criterion, so check it yourself before believing in it.
Context
StackExchange Computer Science Q#104844, answer score: 2
Revisions (0)
No revisions yet.