MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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.