Singular value of Hadamard product

Question

Let $A$ be an $n \times n$ random symmetric matrix with $E(A_{i j}) = 0$, $Var(A_{i j}) = 1/n$ for any $i,j$. $B$ is an $n \times n$ symmetric matrix with $B_{ii} = 0$.

I need to find a upper bound of $Tr(A^2 (A\circ B))$ as tight as possible. Notation $\circ$ is Hadamard product and $Tr(\cdot)$ is the trace of a matrix.

Currentely, my approach is as follows. According to von Neumann's trace inequality,

$Tr(A^2 (A\circ B)) \le \sum_i \sigma_i(A^2) \sigma_i (A \circ B) = \sum_i \big(\sigma_i (A)\big)^2 \sigma_i (A \circ B)$ ,

where $\sigma_i(\cdot)$ is the $i$th singular value of a matrix.

However, I do not know how to handle with $\sigma_i (A \circ B)$. Is there any way to deal with this or is there any better idea to find the upper bound?

Answer 1

Let $k \le n$ be the rank of $B$, and for $1 \le i \le k$, let $r_i(A)$ be the euclidean norm of the $i$th row of $A$ and let $c_i(A)$ be the Euclidean norm of the $i$th column of $A$. Taking things from where the OP left off, one can write $$ \begin{split} \left|\mbox{tr}(A^2 (A \circ B))\right| &\le \sum_i \sigma_i(A)^2 \sigma_i(A \circ B) \le \|A\|_{\mathrm{op}}^2\cdot\sum_i\sigma_i(A \circ B)\\ &\le \|A\|_{\mathrm{op}}^2\cdot \sum_i \min(r_i(A),c_i(A))\sigma_i(B)\\ &\le \|A\|_{\mathrm{op}}^2\|B\|_\star\cdot\max_{1 \le i \le k}\min(r_i(A),c_i(A)), \end{split} $$ where $\|B\|_\star := \sum_i \sigma_i(B)$ is the nuclear norm of $B$ and the second line is by Theorem 1 of "INEQUALITIES FOR THE SINGULAR VALUES OF HADAMARD PRODUCTS".

Now, by standard RMT, we know that $\|A\|_{\mathrm{op}} = \mathcal O(1)$ with probability $1-e^{-cn}$. Also, other certain conditions (see further below), each $r_i(A)^2$, and therefore each $c_i(A)^2$, verifies $|r_i(A)^2-1| \le t$ w.p $1-c/k^{1+\delta}$, for some universal $\delta > 0$. Putting things together, we deduce via a simple union bound that

$\left|\mbox{tr}(A^2(A \circ B))\right| \lesssim \|B\|_\star$ with arbitrarily high probability.

---

For the concentration of the $r_i(A)^2$, any of the following conditions is sufficient

• $k = o(n)$ (or roughly said, $k/n \to \infty$), OR
• $A_{ij}$ has sub-Gaussian concentration, OR
• ...

In case of the first condition, we would use the Chebyshev inequality.