Numerically unstable matrix decompositions (to simple perturbations e.g. $A+ \varepsilon A$) So basically the title says it all. I would like to find a decomposition, or something similar, e.g. any transformation that would "notice" a slight perturbation in a given matrix; as in $f(A) - f(A+ \varepsilon * A)$ is relatively big. It would be desirable if it were reversible. Let's say the matrix has nonnegative values and they are bounded from above.
An example could be LSB type algorithms.
All of the normally used decompositions are stable. E.g. singular value decomposition: $U, S,V$ won't change much if I make slight changes to the original matrix.
 A: Eigenvalue and Jordan decompositions are pretty unstable in general. Pretty much the worst case scenario is this example. Consider
$$
J(\epsilon) = \begin{pmatrix}
0 & 1 & & \\
& \ddots & \ddots & \\
& & \ddots & 1 \\
\epsilon & & &0
\end{pmatrix}\in \mathbb{C}^{n\times n}.
$$
When $\epsilon=0$, we have only a single eigenvalue $0$. However, one can show that for $\epsilon>0$, $J(\epsilon)$ has $n$ distinct eigenvalues given by $\lambda_j = \omega^j\epsilon^{1/n}$, where $\omega = e^{-2\pi i/n}$. Thus, the change in the eigenvalues of a matrix perturbed by $\epsilon$ can be $\epsilon^{1/n}$. Therefore, the eigenvalues can have basically unbounded relative error as $n$ increases.
One can also consider a similar construction of matrices like
$$
A(\epsilon) = \begin{pmatrix}
1 & 1 \\ 0 & 1+\epsilon
\end{pmatrix}
$$
The eigenvalues are $1$ and $1+\epsilon$, which are fine as $\epsilon\to0$, but the problem comes in when you consider the eigendecomposition $A = P\Lambda P^{-1}$. One can compute $P$ and we find that
$$
P^{-1} = \begin{pmatrix}
1 & -\epsilon^{-1} \\
0 & 1
\end{pmatrix},
$$
where is not even defined when $\epsilon=0$.
These examples may be more pathological than you are looking for though
A: Let $\lambda_i$ be the eigenvalues of $A$. Then consider $\prod_i(A_\epsilon-\lambda_i)^{-1}$. Each factor will have a large norm by definition of the eigenvalues. Along the same lines would be $c_A(A_\epsilon)^{-1}$, where $c_A$ is the characteristic polynomial of $A$.
If you prefer a numerical value, consider $\prod_i\|A_\epsilon-\lambda_i)^{-1}\|$ where the norm could be Frobenius norm for easy calculation.
