Why is $\inf \{ \| X \|_2 \mid X \in S^n \} = \inf\{ t \mid -t I \preceq X \preceq t I, X \in S^n\}$?

Question

Question 1: how convert following problem: $$\min \quad \| X \|_2$$ to a Semi-definite Programming(SDP)： $$\min \quad t$$ $$s.t. \quad -tI \preceq X \preceq tI,t \ge 0$$ where X is a symmetric matrix of $n \times n$.

Question 2: in fact, I'm even not sure whether it is a SDP. I tried to construct a optimization variable:

$Y={\begin{bmatrix}S_1 \\ & S_2 \\ & & t\end{bmatrix}}_{(2n+1)\times(2n+1)}$ . Where $S_1=tI-X,S_2=X+tI$.

Notice that $S_1,S_2 \succeq 0$ from above constraints. Now I get $Y \succeq 0$ and write it as: $$\min \quad tr(CY)$$ $$s.t. \quad Y \succeq 0$$

Matrix $C$ can be easily constructed. Now I wonder whether is the way I construct optimization variable valid? If not, what are the formal methods?

Problem comes from an example in Boyd & Vandenberghe Convex Optimization at page 174

Answer 1

The Idea

The $ \left\| \cdot \right\|_{2} $ matrix norm is given by:

$$ \left\| X \right\|_{2} = \sqrt{ \lambda_{max} \left( {X}^{T} X \right) } $$

Where $ \lambda_{max} $ is the maximum eigen value of $ {X}^{T} X $.
Hence the above looks at the extreme conditions where the matrix $ X + t I $ or $ X - t I $ are PSD / NSD matrices.

Proof of $ {L}_{2} $ Matrix Norm

$$ \begin{align*} \left\| A \right\|_{2} & = \max_{x \neq 0} \frac{ \left\| A x \right\|_{2} }{ \left\| x \right\|_{2} } = \max_{x \neq 0} \frac{ \sqrt{ {x}^{T} {A}^{T} A x } }{ \left\| x \right\|_{2} } & \text{} \\ & = \max_{x \neq 0} \frac{ \sqrt{ {x}^{T} Q \Lambda {Q}^{T} x } }{ \left\| x \right\|_{2} } & \text{Where $ {A}^{T} A = Q \Lambda {Q}^{T} $ by Spectral Decomposition} \\ & = \max_{x \neq 0} \frac{ \sqrt{ \left( {Q}^{T} x \right)^{T} \Lambda \left( {Q}^{T} x \right) } }{ \left\| {Q}^{T} x \right\|_{2} } & \text{Since $ Q $ is Unitary matrix} \\ & = \max_{y \neq 0} \frac{ \sqrt{ {y}^{T} \Lambda y } }{ \left\| y \right\|_{2} } & \text{Where $ y = {Q}^{T} x $} \\ & = \max_{y \neq 0} \sqrt{ \frac{ \sum {\lambda}_{i} {y}_{i}^{2} }{ \sum {y}_{i}^{2} } } \leq \sqrt{ \frac{ \lambda_{max} \sum {y}_{i}^{2} }{ \sum {y}_{i}^{2} } } = \sqrt{{\lambda}_{max}} \end{align*} $$

The above is achievable by choosing $ {y}_{j} = 1 $ for $ {\lambda}_{j} = {\lambda}_{max} $ and $ {y}_{j} = 0 $ otherwise.

Pay attention that $ \lambda_{max} $ is always non negative (As all other eigen values of $ {A}^{T} A $ as being PSD Matrix). Basically it is the maximum of the absolute values of the eigen values of $ A $.

The Meaning of the Operations

All needed to show is that the operation of adding scaled unit matrix is changing the values of the Singular Values of the matrix.

Since $ X $ is a symmetric matrix, by Spectral Decomposition one could write:

$$ X \pm t I = Q \Lambda {Q}^{T} \pm t I = Q \left( \Lambda \pm t I \right) {Q}^{T} $$

As can be seen above, adding the term $ t I $ shifts the eigenvalues of $ X $.

Shifting Set of Numbers

Given a set of numbers $ \left\{ {\lambda}_{1}, {\lambda}_{2}, \ldots, {\lambda}_{n} \right\} $ how could one find their maximum?

Assuming Non Negative Numbers

Assuming all numbers are non negative one could ask what's the minimum number $ t $ such that $ {\lambda}_{j} - t \leq 0, \, \forall t $. This will yield $ t = {\lambda}_{max} $. As uses above, $ t $ is non negative number.

Assuming Non Positive Numbers

Assuming all numbers are non positive one could ask what's the minimum number $ t $ such that $ {\lambda}_{j} + t \geq 0, \, \forall t $. This will yield $ t = {\lambda}_{max} $. As uses above, $ t $ is non negative number.

Summary

Hence, for any set of numbers if one looks for the non negative $ t $ which holds both of the above then $ t $ will be equal to the maximum absolute value of the set.

Answer 2

To my understanding: $$\|X\|_2=\max_{u \neq 0} \frac {\|Xu\|_2} {\|u\|_2}$$ $$\qquad \qquad =\max_{u \neq 0}(\frac {u^TX^TXu} {u^Tu})^{1/2}$$ $$\qquad \qquad =\max_{u \neq 0}(\frac {u^T X^2 u} {u^Tu})^{1/2}$$ $$\qquad \qquad \qquad \quad=\max_{u \neq 0}(\frac {(Q^Tu)^T \Lambda^2 Q^Tu} {(Q^Tu)^T Q^Tu})^{1/2}$$ $$\qquad \qquad \qquad \quad=|\lambda|_{max}=\max\{|\lambda_1|,|\lambda_n|\}$$

Where $|\lambda|_{max}$ represents the maximum of absolute value of eigenvalues of $X$(e.g. although $\lambda$ is the most negative, $|\lambda|$ is the most positive) and $$X=Q \Lambda Q^T=Q \begin{bmatrix} \lambda_1 \\ &\lambda_2 \\& & \ddots \\ & & & \lambda_n\end{bmatrix} Q^T$$ $\lambda_1,\lambda_n$ are the maximum and the minimum of eigenvalues respectively(i.e. $\lambda_1 \ge\lambda_2 \ge\lambda_3 \ge... \ge\lambda_n$).

From Royi's thread, $X \pm tI=Q(\Lambda \pm tI)Q^T$ means what we actually do is shifting eigenvalues with magnitude $t$(suppose $t \ge 0$).

Given $|\lambda|_{max}=|\lambda_n|$, the minimum magnitude we have to shift is t=$|\lambda_n|$ so that $X+tI \succeq 0$(which means $\lambda_n$ is negative, $|\lambda|_n \ge |\lambda|_1$ and naturally $X-tI \preceq 0$).

Given $|\lambda|_{max}=|\lambda_1|$, the minimum magnitude we have to shift is t=$|\lambda_1|$ so that $X-tI \preceq 0$(which means $\lambda_1$ is positive, $|\lambda|_1 \ge |\lambda|_n$ and naturally $X+tI \succeq 0$).

Anyhow, we can achieve: $$\inf\{t|X+tI \succeq 0,X-tI \preceq 0,|\lambda|_{max}=|\lambda_n|\}=|\lambda_n|$$ $$\inf\{t|X-tI \preceq 0,X+tI \succeq 0,|\lambda|_{max}=|\lambda_1|\}=|\lambda_1|$$ To sum up: $$\inf\{t|X+tI \succeq 0,X-tI \preceq 0\}=|\lambda|_{max}=\|X\|_2$$