Suppose we want to have a good approximation for the following NP-hard problem
$$\min_{\bf X} \operatorname{rank}({\bf X}) \text{ s.t. } \mathcal{A}({\bf X}) = {\bf b}, {\bf X} \succeq 0$$
where ${\bf X}$ is $n\times n$, and $\mathcal{A}$ is a linear operator. For the case that the solution is unique, has rank $1$, and $\Omega(n\text{poly}\log(n))$ entries of ${\bf X}$ are "revealed", we can approximate $\text{rank}({\bf X})$ with $\text{trace}({\bf X})$. This relaxation is asymptotically tight with high probability, as shown by Candès and Tao.
Do there exist similar guarantee results for cases where the the minimum rank of ${\bf X}$ is still $1$, however the problem does not have a unique solution and only $\mathcal{O}(n)$ entries of the matrix are revealed?
