# Condition for guaranteed minimum-rank solution

Consider the following rank minimization problem of a positive semidefinite matrix $X$:

\begin{equation*} \begin{aligned} & \underset{X}{\text{minimize }} & & \mbox{rank} (X) \\ &\text{subject to}& & \| X - \hat{X} \| \leq \epsilon\\ &&& X \succeq 0 \\ \end{aligned} \end{equation*}

1. If I understand correctly, the general rank minimization problem is NP-hard but a special case exists where the extra constraint that the affine transformation of $X$ is also positive semidefinite, such as $A - X \succeq 0$, makes this problem efficiently solveable. Is this correct? What is the condition under which an exact solution can be computed?

2. Is there an algorithm for computing the exact minimum rank of $X$ subject to the above constraints?