Find the matrix projection of a symmetric matrix onto the set of symmetric positive semi definite (PSD) matrices

Question

Consider $\mathbb{S}^n$, the set of all $n\times n$ real symmetric matrices. Let $A\in \mathbb{S}^n$ and $A=U\Lambda U^{\top}$ be its spectral decomposition. I want to know how to prove that $\Pi_{\Bbb S_+^n}(A)=U\Lambda ^+U^{\top}$, where $\Lambda^+$ is the $n\times n$ diagonal matrix given by $\Lambda_{ii}^+=\max\{\Lambda_{ii}, 0\}$, for $i=1,...,n$；$\Pi_{S}(x)=\arg\min_{z\in S}\|x-z\|^2_2$.

This projection means that we can project any symmetric matrix on $\mathbb{S}_+^n$ and get the closest positive semi-definite matrix, but how can we prove that it is the closest one?

Answer 1

There is a subtle point missing in Rajat's answer, so I will repeat the proof:

Let $A = U\Lambda U^\top$ be the eigenvalue decomposition of $A$. Then we have $$ \min_{X\succeq 0} \|X-A\|_F^2 = \min_{X\succeq 0} \|X-U\Lambda U^\top\|_F^2=\min_{X\succeq 0} \|U^\top X U-\Lambda\|_F^2. $$

Now here is the subtle point: The matrix $B\equiv U^\top X U$ must be diagonal. Why?

First, whenever $\lambda_{ii}\geq 0$ we can set $b_{ii}=\lambda_{ii}$ to get zero error for those elements. Regarding the terms where $\lambda_{ii}< 0$, since $B$ is also psd it must have non-negative diagonal, so the best we can do is put $b_{ii}=0$. One might think that it's possible to put there a negative value which will decrease the error, and somehow take care of the psd constraint by carefully distributing the off-diagonal elements, but negative diagonal elements would violate the constraint. As for the off-diagonal elements - anything diffeent than $0$ would increase the error.

The solution is then given by $X = U \left(\max\left(\Lambda,0\right)\right) U^\top$.

Answer 2

$\Pi_{\mathbb{S}_+^n}(A)=\arg\min_{X \in \mathbb{S}_+^n}\|X-A\|^2_F=\arg\min_{X \in \mathbb{S}_+^n}\|\Lambda_X -V^{\top}A V\|^2_F$

$X = V \Lambda_X V^{\top}$ (as $X\in \mathbb{S}^n_+$, so it is diagolalizable), $B=V^{\top}A V$

$\|\Lambda_X -V^{\top}A V\|^2_F = \sum_{i \neq j}b_{ij}^2+\sum_i (\Lambda_{X_{ii}}-b_{ii})^2$

Minimum occurs when $b_{ij}=0$, and $\Lambda_{X_{ii}}=b_{ii}$. Note that $\Lambda_{X_{ii}} \geq 0$, so $\Lambda_{X_{ii}}=\max\{0,b_{ii}\}.$ $B$ is a diagonal matrix. So, $V=U$.