If $A$ is a random matrix, $B$ is a matrix very close to the all-one matrix, then is $\|A\circ B\|$ close to $\|A\|$?

44 Views Asked by At

Suppose $A\in\mathbb{R}^{n\times n}$ is a symmetric random matrix with i.i.d. entries \begin{align} A_{ij} = A_{ji} = \begin{cases} -p & \text{with probability } 1-p, \\ 1-p & \text{with probability } p \end{cases} \end{align} for some $p\in (0,1)$. If we also know $B\in\mathbb{R}^{n\times n}$ is a symmetric matrix that is close to the all-one matrix $J$, i.e. there exists a small $\varepsilon$ such that \begin{align} 1-\varepsilon \leq B_{ij} \leq 1 \end{align} for any $i,j\in[n]$, where $\varepsilon\rightarrow 0$ as $n\rightarrow\infty$.

Since $A_{ij}$ are i.i.d. and bounded with $\mathbb{E}A_{ij} = 0$, it is not hard to get a high probability bound for $\|A\|$ (here $\|\cdot\|$ represents spectral norm) through Bernstein's inequality \begin{align} \mathbb{P}\left\{\|A\| \geq t\right\} & \leq 2n\exp\left(-\frac{t^2/2}{\mathrm{Var}(A) + t/3}\right) \\ & = 2n\exp\left(-\frac{t^2/2}{np(1-p) + t/3}\right). \end{align} In other words, we have $\|A\| \leq \sqrt{2p(1-p)n\log n}$ with high probability.

My question is whether we could give a similar high probability bound for $A\circ B$ such that the bound gives approximately the same guarantee as the one for $A$. Intuitively, the spectral norm $\|A\circ B\|$ should not deviate from $\|A\|$ too much because $A\circ B$ and $A$ are roughly the same when $n$ is large. So can we get such a high probability bound that looks tight and utilizes the information that every entry of $A\circ B$ can only deviate from its original value in $A$ by a small portion of $\varepsilon$?

Moreover, for the same random matrix $A$ if instead of $B$ there is an anti-symmetric $C\in\mathbb{R}^{n\times n}$ such that \begin{align} |C_{ij}| \leq \varepsilon \end{align} for any $i,j\in [n]$. Then do we have a way to utilize the fact that $C$ is anti-symmetric and obtain a better bound on $\|A\circ C\|$ than simply flipping the minus part of $A$ to get \begin{align} (A_C)_{ij} = (A_C)_{ji} = \begin{cases} \varepsilon p & \text{with probability } 1-p, \\ \varepsilon (1-p) & \text{with probability } p \end{cases} \end{align} and deriving a bound through $\|A\circ C\|\leq \|A_C\|$?