# Norm of matrix with randomly deleted entries

Let $A$ be an $n \times n$ matrix with real entries and let $B$ be the random matrix whose $(i,j)$ entry is $$B_{i,j}=v_{i,j}A_{i,j}$$ where the $v_{i,j}$ are i.i.d Bernoulli random variables with $P(v_{i,j} = 1 ) =\rho$ and $P(v_{i,j} = 0) = 1-\rho$.

That is, $B$ is formed by setting each entry of $A$ to 0 with probability $1-\rho$.

Is there any result about how the norm of $B$ compares with the norm of $A$ in expectation? I'm particularly interested in the maximum row sum norm $\|B\|_{\infty} = \max_{i}\{\sum_{j}|B_{i,j}|\}$

It seems obvious that $\mathbb{E}(\|B\|_{\infty}) < \|A\|_{\infty}$ as long as $\rho > 0$, and I'm looking for some references which attempt quantify this.

• I don't think you can say a whole lot for general $A$. For example, if there's a single column with $1$'s only and all other entries are zero, then $\|B\|=\|A\|$ with prob $1-(1-\rho)^n$, so the expectation doesn't go down by much. Commented Mar 12, 2015 at 4:50
• Thanks for this example. It seems that you can use the same argument for the identity matrix, and then you can conclude that $P(\|A\| = \|B\|)$ is going to be high for other matrix norms which specialize to the the largest absolute element on diagonal matrices.
– ttb
Commented Mar 14, 2015 at 7:45