The conjecture on SDP recovery for k-means at separation greater than 2+ϵ2+\epsilon

About 12 years old · traced to

Let the data and cluster model be under the same setting as in Theorem, and let Δ\Delta denote the cluster separation. Consider the SDP relaxation for the kk-means objective.

SDP recovery conjecture. The SDP relaxation recovers the clusters with high probability whenever

Δ>2+ϵ.\Delta > 2+\epsilon.

The preceding theorem establishes recovery under the stronger separation condition Δ>22(1+1/m)\Delta > 2\sqrt{2}(1+\sqrt{1/m}), while the paper notes that this bound is not tight and conjectures recovery at separation greater than 2+ϵ2+\epsilon.

References

Primary source

Pranjal Awasthi, Afonso S. Bandeira, Moses Charikar, Ravishankar Krishnaswamy, Soledad Villar and Rachel Ward, “Relax, no need to round: integrality of clustering formulations”, arXiv:1408.4045 (2015).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.