8
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ what if the matrix is within epsilon of a matrix that is not diagonalizable $\endgroup$ – k20 Dec 19 '14 at 23:18
6
$\begingroup$

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

$\endgroup$
10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ thanks a lot for your answer. the matrix in question would be normal, which is good :). Could you elaborate a little bit more on the statement "assuming the matrix X does not change much"? Is there some way to guarantee this for normal matrices? $\endgroup$ – ftiaronsem Dec 22 '14 at 20:40
  • $\begingroup$ @ftiaronsem I think you can follow links in Nick Alger's answer and determine the change in $X$ by computing the derivative $dX$ and estimating how big it can be. The point of my answer is really that if the matrix is not known to be normal (your question didn't say), then this is really not as straightforward as one might think. $\endgroup$ – Kirill Dec 22 '14 at 21: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.