Let $A=(a_{ij})_{ij}$ be an $m \times n$ random matrix with i.i.d entries. Let $E=(\epsilon_{ij})$ be a deterministic $m \times n$ matrix with $|\epsilon_{ij}|<\epsilon$ where $\epsilon$ is a fixed positive number.
I wonder if there are any good estimates for the norm of the matrix $A+E$ in terms of the norm $\|A\|$ (Frobenius or operator norm) and $\epsilon$ and $m,n$ (if necessary).
I didn't assume that $A$ is a mean zero random matrix. But if necessary, please feel free to assume that. I guess there will be a big difference to the norm, whether a matrix has mean zero or not.
Please let me know the reference if the result is highly non-trivial.
For the operator norm we have $$\|A+E\|=\sup \{\|(A+E)x\|: x\in\Bbb R^n,\, \|x\|=1 \}.$$
For any $x\in\Bbb R^n$ such that $\|x\|=1$ we have $\|(A+E)x\|\le \|Ax\|+\|Ex\|$. Next, we have $\|Ax\|\le \|A\|$ and for each $1\le i\le m$ the absolute value of $i$-th coordinate of the vector $Ex$ equals $$|(Ex)_i|=\left|\sum_{k=1}^n \epsilon_{ik}x_{k}\right|<\epsilon \sum_{k=1}^n |x_{k}|=\epsilon\|x\|_1.$$ If both spaces $\Bbb R^n$ and $\Bbb R^m$ are endowed with $\ell_p$ norm $\|y\|_p=\left(\sum |y_i|^p) \right)^{1/p}$ for $1\le p<\infty$ and each $y$ then
$$\|Ex\|^p_p=\sum_{i=1}^m |(Ex)_i|^p< m \sum_{i=1}^n (\epsilon\|x\|_1)^p=m(\epsilon\|x\|_1)^p\le m\epsilon^p\|x\|_p^pn^{p-1},$$ so $\|Ex\|_p\le \left(\frac mn\right)^{1/p} n\epsilon \|x\|_p$ and thus $\|E\|\le \left(\frac mn\right)^{1/p} n\epsilon$. Hence $\|A+E\|\le \|A\|+\left(\frac mn\right)^{1/p} n\epsilon$.
For the Frobenius norm we have
$$\|A+E\|_F^2=\sum_{i,j} (a_{i,j}+\epsilon_{i,j})^2=\sum_{i,j} a_{i,j}^2+2 a_{i,j}\epsilon_{i,j}+\epsilon^2_{i,j}<$$ $$ \|A\|_F^2+2\epsilon\sum_{i,j} |a_{i,j}|+mn\epsilon^2\le \|A\|_F^2+2\sqrt{mn}\epsilon\|A\|_F +mn\epsilon^2.$$
PS. In the calculations above we used an inequality $$\frac{\sum_{j=1}^N a_i}{N}\le \left (\frac{\sum_{j=1}^N a_i^p}{N}\right)^p,$$ valid for each non-negative numbers $a_1,\dots, a_N$ and each $p\ge 1$.