# Matrix projection onto positive semidefinite cone with respect to the spectral norm

On page 399 of Boyd & Vandenberghe's Convex Optimization, it is stated that the projection of a symmetric $$n \times n$$ matrix $$X_0$$ onto the set of symmetric $$n \times n$$ positive semidefinite matrices $$S^n_+$$ is found in the following way:

• Find the spectral (eigenvalue) decomposition $$X_0 = \sum_{i=1}^n \lambda_i v_i v_i^T$$

• Define the projection $$X = \sum_{i=1}^n \max\{\lambda_i, 0\} v_i v_i^T$$

It is proven in the book that $$X$$ is the solution of the problem

$$\underset{X}{\text{minimize}} \quad \| X - X_0 \|_F^2 \quad \text{subject to} \quad X \succeq 0$$

where $$\|A\|_F^2 = \operatorname{tr} \left(A^T A\right)$$ is a square of the Frobenius norm. In other words, $$X$$ is the projection of $$X_0$$ onto symmetric positive semidefinite matrix cone with respect to the Frobenius norm.

I have also found a proof of this in this question.

Now the book also states (without a proof, or at least it is not obvious for me from the material) that $$X$$ is also a solution to the problem

$$\underset{X}{\text{minimize}} \quad \| X - X_0 \|_2 \quad \text{subject to} \quad X \succeq 0$$

where $$\|A\|_2$$ ($$A$$ being symmetric) is the spectral norm,

$$\|A\|_2 = \max_{i=1, \dots, n}|\lambda_i| = \max\{\lambda_1, -\lambda_n\}$$

where $$\lambda_i$$ are the eigenvalues of $$A$$, $$\lambda_1 \geq \lambda_2 \geq \dots \geq \lambda_n$$. How to prove this?

• Hint: you can make the problem easier by first showing that the result is true for diagonal matrices and then showing that the general problem can be reduced to one involving a diagonal matrix $X_{0}$. Commented May 12, 2018 at 13:45

Let $X_0 = \sum_{i=1}^n \lambda_i v_i v_i^T$ be the eigenvalue decomposition of matrix $X_0$ with $\lambda_1 \geq \lambda_2 \geq \dots \geq \lambda_n$. Assume $\lambda_n < 0$, as otherwise the projection of $X_0$ onto positive semidefinite cone would be itself. Then we have $$v_i^T X_0 v_i = \sum_{j=1}^n \lambda_i v_i^T v_j v_j^T v_i = \lambda_i$$ and $$||X_0||_2 = \max\{\lambda_1, -\lambda_n\} = \max\{v_1^T X_0 v_1, -v_n^T X_0 v_n\} = \max\{\sup_{||v||_2=1} v^T X_0 v, -\inf_{||v||_2=1} v^T X_0 v\}$$ Now let $X$ be any symmetric positive semidefinite matrix. We have $$||X - X_0||_2 \geq \sup_{||v||_2 = 1} v^T (X - X_0) v \geq v_n^T (X - X_0) v_n = v_n^T X v_n - v_n^TX_0v_n \geq -\lambda_n$$ Now if we define $X = \sum_{i=1}^n \max\{\lambda_i, 0\} v_i v_i^T$, we have $||X - X_0||_2 = -\lambda_n$. Therefore, the defined matrix is the projection of $X_0$ onto positive semidefinite cone.