Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.