Prove that

$$\bigg\| \begin{bmatrix} X \\ A\end{bmatrix} \bigg\|_2 \leq \sigma \iff X^* X + A^* A \preceq \sigma^2 I$$

Here, * denotes the conjugate transpose. This norm is the $2$-induced matrix norm. This equivalence is a part of other proof and I don't know how to start proving this equivalence.

obs: No need for a formal proof, the simply understanding of this inequality is enough for me.

The context from which I took this question is:

enter image description here

  • $\begingroup$ What does $[\cdot]^\prime$ mean? $\endgroup$ – parsiad Jul 3 '16 at 23:21
  • $\begingroup$ @par, I just editted the question $\endgroup$ – gustavoreche Jul 3 '16 at 23:39

Short Answer: \begin{align} \left\|\begin{bmatrix} X\\A \end{bmatrix} \right\|^2_2 := \lambda_{max}\left(\begin{bmatrix} X\\A \end{bmatrix}\begin{bmatrix} X^\mathrm{*}&A^\mathrm{*} \end{bmatrix} \right) = \lambda_{max}\left(\begin{bmatrix}X^\mathrm{*} & A^\mathrm{*} \end{bmatrix}\begin{bmatrix} X\\A \end{bmatrix} \right) = \lambda_{max}\left(X^{*}X + A^*A \right) \end{align} Now notice $\lambda_{max}\left(X^{*}X + A^*A \right) \leq \sigma^2 \Leftrightarrow \left(X^{*}X + A^*A \right)-\sigma^2 I \preceq 0 \Leftrightarrow X^{*}X + A^*A \preceq \sigma^2 I$

Longer Answer: \begin{align} \left\|\begin{bmatrix} X\\A \end{bmatrix} \right\|^2_2 := \lambda_{max}\left(\begin{bmatrix} X\\A \end{bmatrix}\begin{bmatrix} X^\mathrm{*}&A^\mathrm{*} \end{bmatrix} \right) = \lambda_{max}\left(\begin{bmatrix}X^\mathrm{*} & A^\mathrm{*} \end{bmatrix}\begin{bmatrix} X\\A \end{bmatrix} \right) = \lambda_{max}\left(X^{*}X + A^*A \right) \end{align} Where $\lambda_{max}\left(AA^* \right) = \lambda_{max}\left(A^*A \right)$ can be verified by looking at the SVD of $A=U\Sigma V^{*}$ and noting that $\lambda_i(AA^*) = \lambda_i(U\Sigma^2 U^*) = \lambda_i(V\Sigma^2 V^*) = \lambda_i(A^*A)$

Now notice: \begin{align} \lambda_{max}\left(X^{*}X + A^*A \right) \leq \sigma^2 &\Leftrightarrow \lambda_{max}\left(X^{*}X + A^*A \right)- \sigma^2 \leq 0 \\ &\Leftrightarrow \lambda_{max}\left(X^{*}X + A^*A -\sigma^2 I\right) \leq 0 \\ & \Leftrightarrow \left(X^{*}X + A^*A \right)-\sigma^2 I \preceq 0 \\ & \Leftrightarrow X^{*}X + A^*A \preceq \sigma^2 I \end{align}


Note that \begin{align*} \gamma & \geq\left\Vert \left[\begin{array}{c} X\\ A \end{array}\right]\right\Vert \\ & =\sup_{\left\Vert x\right\Vert =1}\left\Vert \left[\begin{array}{c} X\\ A \end{array}\right]x\right\Vert \\ & =\sup_{\left\Vert x\right\Vert =1}\sqrt{\left(\left[\begin{array}{c} X\\ A \end{array}\right]x\right)^{*}\left[\begin{array}{c} X\\ A \end{array}\right]x}\\ & =\sup_{\left\Vert x\right\Vert =1}\sqrt{x^{*}\left[\begin{array}{cc} X^{*} & A^{*}\end{array}\right]\left[\begin{array}{c} X\\ A \end{array}\right]x}\\ & =\sup_{\left\Vert x\right\Vert =1}\sqrt{x^{*}X^{*}Xx+x^{*}A^{*}Ax}.\\ & =\sup_{\left\Vert x\right\Vert =1}\sqrt{x^{*}\left(X^{*}X+A^{*}A\right)x}. \end{align*} Therefore, $$ \gamma\geq\sqrt{x^{*}\left(X^{*}X+A^{*}A\right)x}\text{ for all }\left\Vert x\right\Vert =1.\tag{*} $$ Squaring both sides, $$ \gamma^{2}\geq x^{*}\left(A^{*}A+X^{*}X\right)x\text{ for all }\left\Vert x\right\Vert =1. $$ Now, if $x$ is not a unit vector, we can normalize to get $$ \gamma^{2}x^{*}Ix=\left\Vert x\right\Vert ^{2}\gamma^{2}\geq x^{*}\left(A^{*}A+X^{*}X\right)x. $$ Thus, we have proven $\gamma^{2}I\geq A^{*}A+X^{*}X$. The reverse direction is essentially the same (start with inequality $(*)$ and take supremums of both sides).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.