Condition for guaranteed minimum-rank solution

Question

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?

Answer 1

The general rank minimization is, as you said, NP-hard since for example, it reduces to cardinality minimization problem, which is intractable. For the positive semi-definite case, trace heuristic (nuclear norm minimization, in general) and log-det heuristic are two of the best known practices as well as SVP (partial SVD). You can find more details in Fazel's PhD thesis.