Convex Optimization Procedure for Clustering: Theoretical Revisit
In this paper, we present theoretical analysis of SON -a convex optimization procedure for clustering using a sum-of-norms (SON) regularization recently proposed in [8,10,11,17]. In particular, we show if the samples are drawn from two cubes, each being one cluster, then SON can provably identify the cluster membership provided that the distance between the two cubes is larger than a threshold which (linearly) depends on the size of the cube and the ratio of numbers of samples in each cluster. To the best of our knowledge, this paper is the first to provide a rigorous analysis to understand why and when SON works. We believe this may provide important insights to develop novel convex optimization based algorithms for clustering.
The paper revisits a convex optimization procedure for clustering andshows that when samples are drawn from two cubes that are sufficientlyseparated the method correctly recovers the cluster memberships fromthe data.  The paper contains a very interesting lifing technique thatis used in the proof.  The paper can be improved quite a bit -- bothin terms of the quality/clarity of the writing and the presentation of theproofs.  The originality is quite high, especially in the proof of the Theorem.  The technical details of the proof is quite frankly a bit tootedious, and I think can be considerably improved.  One possible suchimprovement is to note that the penalty term can be written \sum_i<j ||x_i-x_j|| = 1/2 \sum_i,j ||x_i-x_j||.  This should eliminate abunch of complicated sum manipulations.  I expect that the differenceoperator can now be replaced with the further lifted vector where allx_i-x_j are considered, so that D(E) can simply be described asD(E)=(E kron 1 - 1 kron E) and so forth.Also, note that the problem for p=1 is tractable and can very easily solved analytically for the two cluster case (without any lifting). Here are some other specific comments on the paper:Authors don't cite earliest occurence of method.  There is at least this earlier paper describing COP.Pelckmans K., De Brabanter J. Suykens J.A.K., De Moor B., Convex Clustering Shrinkage, in Workshop on Statistics and Optimization of Clustering Workshop (PASCAL), London, U.K., Jul. 2005. ftp://ftp.esat.kuleuven.ac.be/pub/SISTA/ida/reports/kp05-111.pdfIt's strange to call the NP-hardness of K-means an instability. Usually an instability would refer to small perturbations leading to big changes in the result?SON is previously used as an acronym for the method.  Why invent a new acronym (COP) in this paper?  That hardly seems to be properly respectful of the earlier work.a provable guarantee when COP succeeds in identifying cluster membership.  -- a provable guarantee that COP succeeds in identifying cluster membership under certain conditions?This sentence makes it sound like you can do more than your paper does.Isn't the operator D the same as D_1 up to a permutation?  Do you reallyneed D?The phrase "each cluster being a cube" is used repeatedly and isstrange.  I assume you just mean that the cluster corresponds to thepoints that were drawn from a uniform distribution over the cube.Rearrange the rows of A ...Note that such a rearrangement is not unique since the ordering of A^1and A^2 is not prescribed"for correctly determining" -- "to correctly determine"  or "forcorrect determination of" I have to give you compliements for proving Hocking's rotation conjecture.(3) seems overkill to state explicitly.  The space could be used in abetter way.The matrices on p.5 is presented with no intuition or clue as to whatthey are to be used for.  This is a case of putting the technicalmessy details in the paper and the intuition in the supplementalportion.  The appendix gives the intuition for the matrix \Omega, whereas the paper describes \Omega in gory detail with no sense of whyit's useful or where it comes from.  Can you switch the appendix andthe paper with respect to the \Omega description?What is V in equation (6).  This set has not been defined.Why are the Lemmas numbered starting with 2?line 403: "predict how the the performance" -- "predict how the preformance"Some additional comments for the Appendix/Supplement:It's strange for Lemma 1 to appear in the appendix.  Shouldn't this belemma 4 (or 3 if the others are numbered starting at 1)page 2 appendix.The statement after the sentence"Then, because A is column centered, we get"does not need the column centered property.This is only needed on line 084-086.line 164: column centerd -- column centeredThe statement on line 188 should be shown explicitlyBased on author feedback responding to my comments I have changed my review from "marginally above the acceptance threshold" to "Good paper, accept".