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 following optimization 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).
 A: 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:


*

*Project the Matrix into the Set of Symmetric Matrices.

*Calculate the Matrix Eigen Values by the Eigen Decomposition of a Matrix.

*Threshold the Eigen Values such that any non positive value is zeroed.

*Keep the $ k $ largest eigen values.

*Recompose the matrix by the eigen values and eigen vectors.


Regarding deeper analysis I found:


*

*Semidefinite Projections, Regularization Algorithms and Polynomial Optimization.

*Sublinear Time Low Rank Approximation of PSD Matrices.

*Low Rank PSD Approximation in Input Sparsity Time.

*Positive Semidefinite Rank and Nested Spectrahedra

*Positive Semidefinite Rank.

*Rank Restricted Semidefinite Matrices and Image Closedness.

