Norm of matrix with randomly deleted entries

Question

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.

Answer 1

There is a recent paper related to your question: Bandeira, Afonso S., and Ramon van Handel. "Sharp nonasymptotic bounds on the norm of random matrices with independent entries." arXiv preprint arXiv:1408.6185 (2014). In your question, the random matrix has independent entries, where each entry is a two-point distribution with different means. The special case that each entry has the same distribution (i.e. i.i.d. case) is rather well-understood; but as argued in the paper above, when the entries are independent but not identical, all previous bounds are loose. They derive an (almost) tight bound. That paper only deals with the spectral norm, not the maximum row sum norm. Nevertheless, some ideas might be applicable to other norms.