Solving the 2-norm k-hyperplane clustering problem via multi-norm formulations

1, Results regarding clustering accuracy are relatively weak. The SBB algorithm can only find a lower bound, which can make the clustering results hard to interpret. Bounds between strengthened formulations and the original formulation are missing, for instance, bound between $HC_{(2,1), (\infty, 1)}$ and $HC_{(2,1)}$ is not provided.

2, Corollary 2 might be wrong. The authors said that $1/(1+ \frac{(\sqrt{n} - 1)^2}{n-1})$ is strictly smaller than $1/n$ for all $n$. But $1/(1+ \frac{(\sqrt{n} - 1)^2}{n-1})$ converges to $1/2$, while $1/n$ converges to 0.

3, No applications using real datasets are provided.

4, Comparisons with existing methods are NOT included in the simulations. In addition, the following paper is highly relevant but is not discussed in sufficient detail: Hyperplane Clustering Via Dual Principal Component Pursuit by Manolis C. Tsakiris and Rene Vidal (ICML 2017). The following works are also related but are not mentioned in the paper: T. Zhang, A. Szlam, and G. Lerman, Median k-flats for hybrid linear modeling with many outliers, in Workshop on Subspace Methods, pages 234–241, 2009; G. Lerman, M. B. McCoy, J. A. Tropp, and T. Zhang, Robust computation of linear models by convex relaxation, Foundations of Computational Mathematics, 15(2):363–410, 2015. Please refer to the papers cited in "Hyperplane Clustering Via Dual Principal Component Pursuit" for more related work.

1. The approximation ratio can be as large as $\Omega(n)$, by corollary 2 of the paper.
2. The experiment on the high-dimensional data set does not show a significant improvement. This phenomenon has been discussed in the paper. Proposition 3 shows that the branching nodes of the $L_1$ relaxation grow exponentially by the dimension $n$. Thus the results may not be very helpful in solving high dimensional clustering tasks.

The paper has a few major weaknesses.

First, the presentation is suboptimal with redundancies and unclarity. For example:

• The theorems and propositions in Section 3 appear to be natural consequences of the norm equivalence. Technically it is incremental. And it is unclear how this serves the subsequent sections (see below).
• At the end of the day, the paper proposes adding L1 and L-infinity constraints to the formulation, which already has L2 constraints. This leads to two questions. First, why is Section 3 useful? Second, these constraints are redundant as the L2 constraint $|| w_j ||_2\geq 1$ implies the L1 and L-infinity constraints, as the paper plots in Figures 1 and 2. While the paper means that the L1 and L-infinity constraints are useful during the execution of the SBB algorithm, this leads to great confusion. And furthermore, since the SBB algorithm is disconnected from the actual implementation (see the point below), and since there is a lack of formal descriptions of the SBB algorithm, it is hard to assess whether the proposed redundant constraints are useful for SBB.
• The discussions on spatial branch-and-bound in Section 4 are disconnected from the actual implementations of the methods. It appears to me that the algorithms are implemented by writing down the formulation and invoking Gurobi. Note that Gurobi is a commercial, closed-source solver. Its implementation is unlikely to be pure spatial branch-and-bound; if that were the case, and as per Proposition 2, the classic MI-QCQP formulation would take exponential time at every iteration of bound calculation. Tables 1 and 2 show, instead, that the classic MI-QCQP formulation could be fast for some instances. This leads to concerns about the correctness of Proposition 2 or whether it is obtained by considering a worst case. Indeed, having a nonzero lower bound is easy: just add a constraint $d_i \geq \epsilon$ for a sufficiently small epsilon>0. I would guess that doing so can also speed up the algorithm.
• The introduction of MI-QCQP and the proposed formulation is not clear. Specifically:
  • At Line 302, why is it that The only nonconvexity of the formulation is due to the 2-norm constraints? Isn't that $x_{ij}$ being binary is also a non-convex constraint?
  • Typo in Eq. (3f), and Eq. (3f) is not justified: Why do we need a binary variable $s_{jh}$ to bound the entries of $w_j$? Isn't it that we could just take $w_{jh}^+$ to be the positive entries of $w_{jh}$? This uniquely determines $w_{jh}^+$ and $w_{jh}^-$.
  • Constraints in Eq. (3e) are not justified: Why do we want every entry of $w_j$ is bounded in $[-1,1]$?

The experimental results are somewhat unclear:

• The results appear to be based on simulations. Are there any findings from real-world datasets?

• The sample size is restricted under 100. What might be the reason for this limitation?

• Would it be possible to use plots for comparisons rather than tables?

Adding multiple norm constraints increases the complexity of the MI-QCQP formulation, which could make practical implementation more challenging. How would you address this issue?