I am multiplying a matrix $A$ with vector $p$. However, the matrix $A$ isn't accurate.
Some (a very small fraction) of the element's value is changed from $a_{i,j}$ to {0,$-a_{i,j}$, $2a_{i,j}$}. However, which values are changed is not known. In fact the distribution of changed elements are uniform over elements of the matrix.We do have bound over number of elements changes $\beta\ll n^{2}$.
Let's call the perturbation in the matrix $\Delta A$. So the matrix vector product calculated is $(A+\Delta A)p$. What I am intersted is finding bounds for following quantity
$\eta =\frac{||\Delta Ap||}{||Ap||} $
I would like this bound based on all known quantities like norms of $A$ and $p$ and conditions numbers, $\beta$ etc. It can be assumed that most of the parameters about $A$ and $p$ are known.
Edit - So far I've done is
$\frac{\left\Vert \Delta Ap\right\Vert _{2}}{\left\Vert Ap\right\Vert }\leq\frac{\left\Vert \Delta A\right\Vert _{2}\,\left\Vert p\right\Vert _{2}}{\lambda _{n}\left\Vert p\right\Vert _{2}}\leq\frac{\left\Vert \Delta A\right\Vert _{F}}{\lambda _{n}}$
, Here I have used 2-norm is always less then frobinius norm and $||Ap||\geq\lambda_{n}||p||$ . Here A is SPD matrix and $\lambda_{n}$ is smallest eigenvalue. Now
$||\Delta A||_{F}^{2}=\sum _{(i,j)\in E}a _{i,j}^{2}\leq\beta(\max _{i,j}(a _{i,j}))^{2}$
Hence
$||\Delta A|| _{F}\leq(\max _{i,j}(a _{i,j})\sqrt{\beta})\leq\lambda _{1} \sqrt{\beta}$
. Here again E is the set of entries in the matrix where element has been changed. and $\lambda_{1}$ is largest eigenvalue of the matrix. and $\max_{i,j}(a_{i,j})\leq\lambda_{1}$ . Hence over all I get is
$\frac{||\Delta Ap||_{2}}{||Ap|| _{2}}\leq\kappa(A)\sqrt{\beta}$
However, this is very loose bound since both the terms on right hand side are greater than one
