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}$


$||\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

  • $\begingroup$ If $A$ has $\beta$ or fewer nonzero entries, it can happen that $\Delta A = A$, in which case $\|\Delta Ap\|/\|Ap\| = 1$. Thus, without knowing more about how $A$, $\Delta A$ and $p$ are lined up, you'll never find any bound whose right-hand side is less than one. $\endgroup$ – Vectornaut May 16 '13 at 3:08
  • $\begingroup$ we do know A has $\beta << nnz(A) < n^{2}$ non zero elements $\endgroup$ – zimbra314 May 16 '13 at 4:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.