# Nonunique low rank matrix completion from a few entries

Suppose we want to have a good approximation for the following NP-hard problem

$\text{min rank}({\bf X})$ s.t. $\mathcal{A}({\bf X})={\bf b}$ and ${\bf X}$ is PSD

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 Candes and Tao.

So my question is, if 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.

-