# Projection onto Positive Semidefinite (PSD) Matrices with Bounded Rank

Let $A$ be a symmetric matrix and $\Omega$ denote the set of positive semidefinite matrices with rank at most $k$. Consider the problem:

$$\arg \min_{X \in \Omega} \frac{1}{2} {\left\| X − A \right\|}_{F}^{2}$$

where ${\left\| \cdot \right\|}_{F}$ is the Frobenius Norm.

I know that the minimizer can be computed using the spectral decomposition of $A$. What I am not sure about is how to go about the proof. It would be great if someone could give a sketch of the proof (or suggest a reference).

• The problem this set isn't Convex so I'm not sure there is one answer. – Royi Jun 1 '18 at 8:01
• Not sure if it'll be the optimal solution, but I would take the Eigen decomposition of $A=U\Lambda U^T$, and would construct $\Lambda'$ by choosing the top $K$ (or less) positive Eigen values and set the rest to zero. Then would set $\tilde{X} = U\Lambda' U^T$. -- Btw, as Royi said, I think the problem is not convex due to the rank constraint. – Alt Oct 7 '20 at 21:18

I would use the Projected Sub Gradient Method for this problems.
Yet, the set of Semidefinite Matrices with Bounded Rank isn't Convex.
Hence the method can't be guaranteed to converge to the best solution.

So defining $\mathcal{ {\Omega} }_{k} = \left\{ X \in \mathbb{R}^{n \times n} \mid X \in \mathcal{S}_{+}^{n}, \, \operatorname{rank} \left( X \right) \geq k \right\}$ as the set of matrices with rank up to $k$ and Symmetric Positive Semi Definite.

One can do the following steps to project into the set:

1. Project the Matrix into the Set of Symmetric Matrices.
2. Calculate the Matrix Eigen Values by the Eigen Decomposition of a Matrix.
3. Threshold the Eigen Values such that any non positive value is zeroed.
4. Keep the $k$ largest eigen values.
5. Recompose the matrix by the eigen values and eigen vectors.

Regarding deeper analysis I found: