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).

  • $\begingroup$ The problem this set isn't Convex so I'm not sure there is one answer. $\endgroup$ – Royi Jun 1 '18 at 8:01
  • $\begingroup$ 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. $\endgroup$ – 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:

  1. Semidefinite Projections, Regularization Algorithms and Polynomial Optimization.
  2. Sublinear Time Low Rank Approximation of PSD Matrices.
  3. Low Rank PSD Approximation in Input Sparsity Time.
  4. Positive Semidefinite Rank and Nested Spectrahedra
  5. Positive Semidefinite Rank.
  6. Rank Restricted Semidefinite Matrices and Image Closedness.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.