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?
diagonalization of matrix - omitting small matrix elements
eigensystem;error estimation
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.pdfWhen 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