关于论文引理11中矩阵等式与不等式推导的疑问

Hey Chloe, great questions—this kind of matrix manipulation gets really nitpicky, so it’s totally normal to get stuck on these steps! Let’s work through each of your confusions one by one.

问题1：对角化操作的等式困惑 #

First, let’s unpack the mix-up with the ddiag operator. Your expansion of S was spot-on:
$$S = \text{ddiag}(Azz^T) - A = nI_n - zz^T + \sigma\left(\text{ddiag}(\Delta zz^T) - \Delta\right)$$

Your confusion comes from the paper writing this as $nI_n - zz^T + \sigma\left(\text{ddiag}(\Delta zz^T - \Delta)\right)$—which seems wrong if we’re talking about matrix equality, since:

• The off-diagonal entries of $\text{ddiag}(\Delta zz^T) - \Delta$ are $-\Delta_{ij}$ (non-zero, since $\Delta$ isn’t diagonal)
• The off-diagonal entries of $\text{ddiag}(\Delta zz^T - \Delta)$ are $0$

Here’s the key: the paper isn’t claiming the matrices are identical—they’re using a common shorthand for quadratic form equality. When working with $u^T M u$, only the combination of matrix entries and $u_i u_j$ matters, not the matrix itself.

Wait a second—does Lemma 11 impose any special conditions on $u$? For example, if $u$ is orthogonal to the off-diagonal subspaces of $\Delta$, or if $u$ has some symmetry (like being an eigenvector of $\Delta$)? Even if not, maybe the paper is only concerned with the diagonal contributions for the bound they’re trying to prove, so they’re dropping the off-diagonal terms by rewriting the expression to focus on the diagonal part (since off-diagonal terms might cancel out or be negligible in the final bound).

Your initial breakdown was correct—this is likely a notational shorthand in the paper to simplify the quadratic form expression, not a strict matrix equality.

问题2：两个二次不等式的推导 #

Let’s break down each inequality with concrete bounds.

(2a) $u^T\text{ddiag}(\Delta zz^T)u\geq -|u|2^2|\Delta z|\infty$ #

First, expand the left-hand side: $\text{ddiag}(\Delta zz^T)$ is a diagonal matrix where each entry is $(\Delta zz^T)_{ii} = z_i \cdot (\Delta z)_i$ (since $(\Delta z)i = \sum_k \Delta{ik} z_k$, so multiplying by $z_i$ gives the diagonal entry of $\Delta zz^T$).

So the quadratic form becomes:
$$u^T\text{ddiag}(\Delta zz^T)u = \sum_i z_i (\Delta z)_i u_i^2$$

To get a lower bound, we use the fact that any real number $a \geq -|a|$. Applying this to each term:
$$\sum_i z_i (\Delta z)_i u_i^2 \geq -\sum_i |z_i (\Delta z)_i| u_i^2$$

Now, $|(\Delta z)i| \leq |\Delta z|\infty$ (by definition of the infinity norm—it’s the largest absolute value in the vector $\Delta z$). From your earlier observation that $\text{ddiag}((zz^T)(zzT)) = nI_n$, we can infer $z_i^2 = 1$ for all $i$, so $|z_i|=1$. This means $|z_i (\Delta z)i| \leq |\Delta z|\infty$.

Substituting this in:
$$-\sum_i |z_i (\Delta z)i| u_i^2 \geq -|\Delta z|\infty \sum_i u_i^2 = -|\Delta z|_\infty |u|_2^2$$

Putting it all together gives the inequality (2a).

(2b) $-\sigma u^T\Delta u\geq -|u|_2^2|\Delta|$ #

This relies on a standard quadratic form bound: for any matrix $\Delta$ and vector $u$,
$$|u^T\Delta u| \leq |\Delta| |u|_2^2$$
where $|\Delta|$ is the operator (spectral) norm of $\Delta$. This comes from Cauchy-Schwarz: $u^T\Delta u \leq |u|_2 |\Delta u|_2 \leq |u|_2 \cdot |\Delta| |u|_2 = |\Delta| |u|_2^2$.

Rearranging for the lower bound of $-u^T\Delta u$:
$$-u^T\Delta u \geq -|\Delta| |u|_2^2$$

Multiply both sides by $\sigma$ (assuming $\sigma > 0$, which is standard for regularization-like parameters):
$$-\sigma u^T\Delta u \geq -\sigma |\Delta| |u|_2^2$$

If the paper omits the $\sigma$ on the right-hand side, it’s either a typo, or $\sigma \leq 1$, or they’ve absorbed $\sigma$ into the definition of $|\Delta|$. Either way, the core idea is using the operator norm to bound the quadratic form.

备注：内容来源于stack exchange，提问作者chloe