Skip to main content
4 of 7
added 297 characters in body
dohmatob
  • 6.9k
  • 1
  • 18
  • 76

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} \mbox{tr}(A^2 (A \circ B)) &\le \sum_i \sigma_i(A)^2 \sigma_i(A \circ B) \le \|A\|_{op}^2\cdot\sum_i\sigma_i(A \circ B)\\ &\le \|A\|_{op}^2\cdot \sum_i \min(r_i(A),r_i(A))\sigma_i(B)\\ &\le \|A\|_{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\|_{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 togethe, we deduce via a simple union bound that

$\mbox{tr}(A^2(A \circ B)) \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 concentratio, OR
  • ...

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

dohmatob
  • 6.9k
  • 1
  • 18
  • 76