Appendix In our proofs, we use c, c and kAk

For a set S, we use S to denote the complement of the set. Since we only analyze a single iteration, for simplicity we drop the superscript that indicates the iteration counter. Probability of erroneous cluster identity estimation We begin with the analysis of the probability of incorrect cluster identity estimation. Now we proceed to analyze the gradient descent step. Without loss of generality, we only analyze the first cluster.