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{||\Delta Ap||_{2}}{||Ap||_{2}}\leq\frac{||\Delta A||_{2}\,||p||_{2}}{\lambda_{n}||p||_{2}}\leq\frac{||\Delta A||_{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} $

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.

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

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 =\left\Vert \frac{(\Delta A)p}{p^{T}(A+\Delta A)p}\right\Vert $

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.

When it is just the numerator I am able to come up with something; however when included denominator, I am left with no clues. Any help appreciated

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{||\Delta Ap||_{2}}{||Ap||_{2}}\leq\frac{||\Delta A||_{2}\,||p||_{2}}{\lambda_{n}||p||_{2}}\leq\frac{||\Delta A||_{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} $

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.