Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It only takes a minute to sign up.
Sign up to join this community
I was wondering whether there is some theorem that allows me to put an upper bound on the error introduced by omitting small matrix elements from a matrix before diagonalization.
Let's assume we have a large matrix, whose matrix elements range from $1$ to $10^{-15}$. If I were to set all matrix elements smaller than $10^{-10}$ to $0$ before diagonalizing the matrix, how large would the error be in the eigenvalues and eigenvectors?
Is this implementation dependent?
There is a field of study known as eigenvalue sensitivity analysis or eigenvalue perturbation analysis that allows you to estimate the effect of small matrix perturbations on the eigenvalues and eigenvectors. The basic technique used for this is differentiating the eigenvalue matrix equation, $$AX = X\Lambda.$$
For situations where the eigenvalues of the original matrix are all distinct, the following document has a very clear derivation and results:
Mike Giles. "An extended collection of matrix derivative results for forward and reverse mode algorithmic differentiation". https://people.maths.ox.ac.uk/gilesm/files/NA-08-01.pdf
When the eigenvalues are not distinct, some more care must be taken. See the following presentation and paper.
For the special case of symmetric matrices $A=U \Lambda U^T$ with distinct eigenvalues, subject to a small perturbation $A \rightarrow A + dA$, the results are simple enough that I reproduce them here. The derivative of the eigenvalue matrix is, $$d\Lambda = \text{diag} (U^T dA U),$$ and the derivative of the eigenvector matrix is, $$dU = UC(dA),$$ where the coefficient matrix $C$ is defined as, $$C = \begin{cases} \frac{u_i^T dA u_j}{\lambda_j - \lambda_i}, & i=j \\ 0, &i=j \end{cases}$$
The following paper by Overton and Womersley has a great sensitivity analysis for the symmetric case, including second derivatives.
Overton, Michael L., and Robert S. Womersley. "Second derivatives for optimizing eigenvalues of symmetric matrices." SIAM Journal on Matrix Analysis and Applications 16.3 (1995): 697-718. http://ftp.cs.nyu.edu/cs/faculty/overton/papers/pdffiles/eighess.pdf
It's not implementation-dependent in the sense that this is a mathematical operation performed on your matrix. However, it is very much matrix-dependent.
If your matrix is diagonalizable and $A=XDX^{-1}$, then zeroing out some element adds a small perturbation matrix $E$, so the new eigenvalues will be (assuming the matrix $X$ does not change much) $$ X^{-1}(A+E)X = D + X^{-1}EX. $$ The difference in $D$ has norm bounded by $$ \|E\| \kappa(X), $$ where $\|E\|$ depends on the magnitude of the elements you drop, and $\kappa(X)$ is the condition number of the matrix of eigenvectors.
If your matrix $A$ is normal (i.e., $AA^t=A^tA$), then $X$ is unitary and $\kappa(X)=1$, so this is fine.
If your matrix is not normal, you need the concept of its pseudospectrum, defined as the set $$ \Lambda_\epsilon(A) = \{z \mid z \text{ is an eigenvalue of $A+E$ with $\|E\| \leq \epsilon$} \}. $$ An equivalent definition, which is easier to compute with, is $$ \Lambda_\epsilon(A) = \{z \mid \|(zI-A)^{-1}\|\geq \epsilon^{-1} \}. $$ There is a good survey of pseudospectra and their properties in Pseudospectra of Matrices by Trefethen (it includes a nice gallery of matrices whose pseudospectra are much larger than their spectra: one might think that the pseudospectrum should be a collection of small $\epsilon$-sized disks around the eigenvalues, but that is really not right at all). In general, you cannot just assume that the pseudospectrum is well-behaved and that the perturbations are negligible. You can, however, compute $\kappa(X)$ and estimate the resulting error; you can also compute the pseudospectrum directly.
In some sense, dropping small matrix elements is fine: either they don't matter, and the new results are just as accurate as the original, or they do matter, and your original results are just as inaccurate as the new results.
