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.
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