I am studying Lemma 11 of the paper I am having difficulty understanding on the last step, in particular, I have two questions:
The first question (1) On the first equality of the last step on page 15, the authors use $$u^TSu=u^T(nI_n-zz^T+\sigma [\text{ddiag}(\Delta zz^T-\Delta)])u$$ where $S=\text{ddiag(Azz^T)-A}$. and $\text{ddiag}$ is an operator that sets all off-diagonal entries of a matrix to zero. But I don't understand why this is correct.
My confusion is:
I understand that
$$S=\text{ddiag(Azz^T)-A}=\text{ddiag}((zz^T+\sigma\Delta)zz^T)-zz^T-\sigma\Delta=\text{ddiag}((zz^T)(zz^T))+\sigma\text{ddiag}(\Delta zz^T)-\sigma\Delta-zz^T$$
As we can see that the first term $\text{ddiag}((zz^T)(zz^T))=nI_n$.
Thus I expect $\text{ddiag}(\Delta zz^T)-\Delta=\text{ddiag}(\Delta zz^T-\Delta)$.
But I don't see why this is true. According to the paper, the matrix $\Delta$ is not a diagonal-free matrix, thus the non-diagonal entries of the left-hand side $\text{ddiag}(\Delta zz^T)-\Delta$ should be $-\Delta_{ij}$, while the non-diagonal entries of the right-hand side should be zero.
Where am I wrong at?
The second question (2) On the second last step, I don't understand why
(2a) $$u^T\text{ddiag}(\Delta zz^T)u\geq -\|u\|_2^2\|\Delta z\|_\infty$$
(2b) $$-\sigma u^T\Delta u\geq -\|u\|_2^2\|\Delta\|$$
Any insights would be appreciated. Thank you!
In the paper you have $A=zz^T+\sigma\Delta$ and $z\in\{\pm1\}^n$. Therefore $z^Tz=n$ and the matrix $zz^T$ has a diagonal of ones. It follows that $$ \operatorname{ddiag}(zz^Tzz^T) =\operatorname{ddiag}\big(z(z^Tz)z^T\big) =\operatorname{ddiag}(nzz^T) =nI_n $$ and in turn, \begin{align*} S &=\operatorname{ddiag}(Azz^T)-A\\ &=\operatorname{ddiag}\big( (zz^T+\sigma\Delta) zz^T\big) - (zz^T+\sigma\Delta)\\ &=nI_n+\sigma\operatorname{ddiag}(\Delta zz^T) - zz^T - \sigma\Delta.\\ \end{align*} For your second question, note that $\operatorname{ddiag}(uv^T)=\operatorname{diag}(u\odot v)=\operatorname{diag}(v\odot u)$ in general, where $\odot$ denotes Hadamard (i.e., entrywise) product. Therefore $$ u^T\operatorname{ddiag}(\Delta zz^T)u \geq -\|u\|_2\|\operatorname{diag}(z\odot\Delta z)\|_2 = -\|u\|_2^2\|z\odot\Delta z\|_\infty. = -\|u\|_2^2\|\Delta z\|_\infty. $$ For your last question, the constant $\sigma$ is clearly missing. The expression $-\|u\|_2^2\|\Delta\|$ should read $-\sigma\|u\|_2^2\|\Delta\|$.