Solving the 2-norm k-hyperplane clustering problem via multi-norm formulations
Authors: Stefano Coniglio
Venue: ICLR 2026 Poster (2026)
Keywords: optimization; spatial branch-and-bound; clustering
Primary area: optimization

Abstract: We propose a method to solve $k$-HC$_2$—the $k$-Hyperplane Clustering problem that asks to find $k$ hyperplanes that minimize the sum of squared $2$-norm (Euclidean) distances between each point and its closest hyperplane—to global optimality via spatial branch-and-bound (SBB) techniques. Our method strengthens a mixed-integer quadratically constrained quadratic programming formulation for $k$-HC$_2$ with constraints that arise when formulating the problem in $p$-norms with $p \ge 2$.

In particular, we show that, for every (suitably scaled) $p \in \mathbb{N} \cup \{\infty\}$, one obtains a variant of $k$-HC$_2$ whose optimal solutions yield lower bounds within a multiplicative approximation factor. We focus on the case of polyhedral norms where $p = 1, \infty$ (which are disjunctive-programming representable), and prove that strengthening the original formulation by including, on top of its $2$-norm constraints, the constraints of one of the polyhedral norms leads to an SBB method where nonzero lower bounds are obtained in a number of nodes that is linear in $n$ and $k$ (rather than exponential).

Experimentally, our method leads to very large speedups, reducing median solve times by up to $41\times$ while increasing the total number of solved instances by up to $63\%$, drastically improving the problem's solvability to global optimality.

SOLVING THE 2-NORM K-HYPERPLANE CLUSTERING PROBLEM VIA MULTI-NORM FORMULATIONS
Stefano Coniglio Department of Economics
University of Bergamo
Bergamo, Italy stefano. www.gnoooiiiiiiiiooo......n
ABSTRACT
We propose method to solve k-HC2 the k-Hyperplane Clustering problem that asks find i hyperplanes that minimize the sum of squared 2-norm (Euclidean) distances between each point and its closest hyperplane- global optimality via spatial branch-and-bound (SBB) techniques. Our method strengthens a mixed integer quadratically constrriied quadratic programming formulation for k-HC₂ with constraints that arise when formulating the problem in p-norms with p # In particular, we show that, for every (suitably scaled) p N U {oo}, one ob- tains a variant k-HC2 whose optimal solutions yield lower bounds within a multiplicative approximation factor. We focus on the case of polyhedral norms where = 1, oo (which are that strengthening the original formulation by including, on top of its 2-norm con- straints, the constraints of one of the polyhedral norms leads to an SBB method where nonzero lower bounds are obtained in a number of nodes that is linear n and & (rather than exponential). Experimentally, our method leads to very large speedups, reducing median solve times by up to 41x while increasing the total number of solved instances by up to 63%, drastically improving the problem's solvability to global optimality.
representable), and prove
INTRODUCTION
Given m points {ai...., 3m in IR"", the k-Hyperplane Clustering problem, k-HC2, asks for identifying i hyperplanes which minimize the sum of the squares of the distances between each point and the hyperplane closest it in Euclidean (2-norm) distance. k-HC₂ arises when relationships of co-linearity (in IR²) or co-(hyperiplunariis (in R are sought. One of the problem's most natural applications is line/surface detection in ssaitlely-sampled images and in 3d environments Amaldi & Mattavelli (2002). More applications are found in diverse areas such medical prognosis Bradely & Mangasarian (2000), linear facility location Megiddo & Tamir (1982). discrete-time piecewise affine hybrid system identification contifiicationFeerrr...
et al. (2003), piecewise-affine model fitting Amaldi et al. (016)). prineipal/sparse component analysis Washizawa & Cichocki (2006): He Cichocki (2007): : (2cho))
Tsakiris & Vidal (2017). nonlinear regression He & Qin (2010), dictionary learning Zhang et al.
2013). LiDAR data classification Kong al. (013)) and sparse matrix representation Georgiev
et al. (2007).
k-HC₂ was first introduced by Bradely & Mangasarian (2000), where is shown that, with 1, the problem is solved by computing an cigenvalue-eigenveer
pair of a suitably defined matrix built as a function of the data points. k-HC2 is -ard in any norm since fitting m points in In with l hyperplanes with 0 error is -VP-complete even for = 2 (Megiddo & Tamir, 1982). To tackle k-HC₂ when & 2 2 without optimality guarantees, Bradely Mangasarian (2000) pro- posed an adaptation of the popular k-means heuristic by MacQueen 1967). An exact Mixed Integer Quadratically Constrained Quadratic Programming (MI-QCQP) formulation is proposed by Amaldi & Coniglio 2013), together with heuristic for larger-scale instances. Works addressing variants of k-HC, asking for the smallest number of hyperplanes with distance no larger than a given found in Dhyani & Liberti 2008); Amaldi et al. (2013).

---

Contributions. We propose a method to solve k-HC2 to global optimality via spatial branch- and-bound (SBB) technique. We strengthen a classical mixed-integer quadratically-consttiin quadratic programming (MI-QCQP) formulation for k-HC₂ by including constraints (and variables) that arise when formulating the problem in another p-norm (p * 2). We show that, under mild assumptions, the inclusion of constraints stemming from version of k-HC2 formulated in of the two polyhedral norms (where p 1, oc) leads to an SBB method where nonzero global lower bound obtained in a linear number of SBB nodes, as opposed the exponential number that is necessary when the classical formulation is used. Our experiments reveal that our method leads to very large speedups, reducing median solve times by up 41x while increasing the total num- ber of solved instances by up to 63%, substantially improving the problem's solvability to global optimality.
PRELIMINARIES
Given a point a E R", its p-norm with p E N U {oo} is ||a|lp == lim, (Eh= lap 19x19)//4 1/9 In
particular, for = 1,2, and oo we have ||a]] = Σm= lanl. |all2 == (En=1 las (2) 1/22 and |||]|oe = maxke[a] {|ax|} I The p-norm point-to-hyperplane distance da(a, H) between a point IR" and hyperplane H == {x E TR" :x as the p-norm distance between a and the point E that is closest to Namely, da H
_xJw w = 7 of parameters (w, 7) E R=+1 is defindd
minye ||a zllp- Different arguments, including Lagrangian duality- see Mangasarian 1999
Tmolle"' can be used to show that da H) |w a-21, where and p' satisfy ; + = For p 2,
(a, H) is called Fuclidean point-to-hyperplane (or orthogonal) distance. many applications, such distance is preferred it leads to solutions that are invariant rotations of the data points.
In spite of being defined on top of a p-norm, the distance function dp is intrinsically nonconvex w.r.t w regardless of the choice of p (the proof in the appendix):
Proposition 1. Given hyperplane H = {x R" : x w r and point E R", the function da H)
1 T a->1 where + p' = 1, is a nonconvex function of (w, (o.7)) for every E N (o0). [wo] o'
This makes k-HC2 substantially harder than classical machine learning problems where a norm is minimized, and motivates the adoption of SBB techniques for solving it to global optimality.
APPROXIMATING H-HHC2 USING DIFFERENT NORMS
Given m points (ar ........ am } in IR,, the most compact nonlinear programming (NLP) formulation for k-HC2 reads
m Σ min SE(K]
(a. w 72) }}
(k-HC2)
min (w)))
|00 11
where (wij 7i) R j E [k], are the hyperplane parameters. (k-HC2) has a non-smooth ob- jective function due to Proposition [ and, since ||w,|| w/ Wy. it features ratios of quadratics. While the inner min operator can be casily dropped by introducing binary assignment variables (see below), this formulation is unsuitable for most nonlinear programming solvers as the denominator vanishes when Wi- = 0.
In the remainder of the paper, will study k-HC(n.e) generalized version of k-HC₂ which employs a p norm not necessarily equal to and which is parametric in a constant c 2 0. Its NLP formulation, where 1 + 1, reads:
p
(k-HC(p.c))
min (w,))
Σ
jE(M] { (aT wj 73) ||w5l13 2 e,j [8]
min
'Throughout the paper, we adopt the notation [5] := 1...., E for every Ç E N.
"wwo norms where 1 + 1 are called dual. The 2-norm is self dual and the and no-norms are dual. We report mathematical programming formulations in brackets and optimization problems without them.
2

---

Letting, for problem P, (P)(P) be its optimal solution value, the validity of (k- (c-HC(m.)) and the role that c plays in it are shown by the following lemma (the proof is in the appendix):
Lemma 1. The solutions (l-)C and (k- (k=HC2) coincide. Also, (p.e)) is quadratically homogeneous w.E.t G, i.e., (PT()-HC((.o) = 22 (p.C)))))).)))
The property shown by the lemma will be useful to guide our choice of which p should use to introduce additional norm constraints to the formulation of k-HC₂ (which, we recall, is the version of the problem that we aim to solve in this paper) in order to strengthen it.
Investigating (-Ho(p.e) with (p. c) + (2, 1) is of interest for two reasons. First, as shown in this section, doing so allows us to show that, for suitable choice of p and c, the optimal solutions to k-HC(p.e) are approximate solutions (to within an approximation factor) of those to k-HC ().))- Second, as shown in the next sections, the study of k-HC(p.e) allows us prove that, again for suitable choice of and the formulations (A--CC (p.c)) and (k-HC(2.11) can be intersected obtain a strengthened formulation which is valid for k-HC2 and which is also much easier to solve both in theory and practice.
Rationale.
Novelty. While changes of norm are frequent in the ML literature, the dual norm in the denom- inator of the point-to-hyperplanne distance requires, for our results, switching between primal and dual norms and applying suitable scaling factors to the problem's 's constraints in a way that, to our knowledge, is new. The idea of intersecting formulations derived for different norms, which leads to a provably tighter approximation factor, is also, to our knowledge, uncommon in the literature. We also manage to establish lower bounds on the number of branching operations needed to compute a nonzero lower bound (after which pruning becomes possible), type of result which is extremely rare integer programming (let alone nonlinear integer programming).
3.1 THE GENERAL CASE
We show that, whichever version of k-HC( one aims to solve (be it the 2-norm one with 1 or another one), the optimal-solution value of (-HC(q.ee) for any choice of q and suitable c' is within an approximation factor of the optimal-solution value of k-
Theorem 1.
Let p. q E IN U foo} and с >> The three positive scalars a(p, 4), 8(p 0(p
which, for all x IR", satisfy the congruence inequality alp, 4) |=/lp S ((p, 4/ S 8(p, 4) (=] for [o(x)) also satisfy the optimal-value inequality a(p.g) OPT()-HC(p))
d(p.q)"
OPT k-HC
dip.a)) (a.e 8(p-0)
S (PC
Theorem shows that the optimal solution value of k- k-HC with c' B(p.2) is lower bound
8(p.4)
8(p-4)" This is crucial, as shows which value pick for c' for any norm we may choose to obtain a relaxation of k--HC (p.c) and, in particular, one of 12 (which is, ultimately, the problem we aim to solve).
on the optimal solution value of k-HC(p.c) to within approximation factor of a(p-g)²
We remark that Theorem can be extended produce an approximation of k-HC from above to within an approximation factor we omit the details since, here, we solely are interested in ap- proximations from below to build tighter relaxations suitable for an SBB method.
Theorem has nice geometrical interpretation in terms of the feasible regions of (b.e))))e) and (k-HC )l Indeed, with e' = A(pp.) (g.catmra))
((p.)) the feasible region of the q-norm constraints featured
in k-HC( is a relaxation of the region that is feasible for the p-norm constraints of k-HC An illustration is reported in Figure for p 2, and adopting q 1 (left) and q = oo (right), for which we have, respectively, c' 1 and ç' = Vn
3.2 THE CASE OF POLYHEDRAL NORMS WITH q == 1,00
We now focus on polyhedral norms (g 1, 00). These are of computational interest due to their tractability: while the constraints [|w]| 2 c', j E [b)), with q = 1, oo, are nonconvex, they can be stated as disjunctions polyhedra, thus being mined--tgger-innaagggggamiii representable.
3

---

W2
W2
W1
Figure I: Complements of the feasible regions of {w E IR? 1|wl|1 1} and {w IR? 1/ 1
In light of this, we consider the following two relaxations of k-HC (see again Figure for an illustration of the projection of the feasible regions of these two problems the space for k 1):
(oo.))
min (ar)))
min {a,, wy -5) ||wy|1 2 1.j [k]
jE[Kj
(k-HC )
min (ar,7)
min {(a wy 35) | 2 1 vn [k] jE(K]
Notice that, due to norm duality, (o-,HC features I-norm constraints while (I-HH (1, } fea-
co-norm ones. For these two problems, Theorem leads to the following result (the proof is in the appendix):
Corollary 1. k (o,,)) and k-HC + satisfy:
OPT(k-HC(2.1) OPT(L-HC (no, (P.())
(P < OPT(L-HC
(P.
With the first chain of inequalities, the corollary shows that solving k- (oo, 1)+ i.e., formulating k- HC with the constraint ||иy][ı 2 for all E [k)] leads to relaxation to within approximation factor. With the second one, the corollary shows that solving k-HC ) i.e., solving the version
of k-HC with the constraint ||,, 1l,0 2 Jn for all j [k], leads another relaxation also to within the same approximation factor 1.
3.3 MULTI-NORM RELAXATION
[k], are relaxations of ||w,]|2 2 1. E [k]. a strengthened relaxation of k-HC(2,11) can be obtained by simultancously imposing both. Such multi-norm relaxation, which we refer as (-HH((muli.))) reads
Since both ||w,||| 2 1. E [k), and ||w J -
| 2 1, j k k
(m-Hi()
min (w
Σ min (a, wy -3) jE(K]
20 2 Va
j
E
Letting ||ull == min [[w/|,, w [w/l)))))))) one can see that simultaneously imposing ||w, |1 2
and | 2 + j E [k], coincides with imposing ||wy] Imatti
1.j E [k]. A depiction of the
corresponding feasible region reported in Figure
So far, our analysis has hinged on the possibility of translating a p'-norm constraint into the cor- responding dp distance, which we applied Theorem [ Deriving an approximation factor for k-HC is not straightforward, though. This is because, while vector norms are convex and convex functions have convex sublevel sets, the sub-level sets the function ||utt are not con- vex and, thus, there is no p-norm, p E N {oo}, whose adoption directly leads to k- (mml))u
4

---

102
W1
Figure 2: Complement of the feasible region of {w E R ||00| Imoti 2 1}.
In spite of this, in the following we show that we can still derive an approximation factor by con- structing the norm that is implicitly minimized when min(|]w|]1, v / 2 1 is imposed.
We start with the following lemma (the proof is in the appendix), which shows what combination of point-to-hyper -heee-ll- distances is minimized in k-HC when imposing min[//wlla val|wlloo 2 1:
Lemma 2. Solving k-HC subject to min vnl // 2 1 coincides with solving an uncon- strained version of k-HC where the point-lo-hyperplane distance between as and Hj is defined as max (doc (ax, H3); Jm dd (ax, H,))-
We now prove two new lemmas (the proofs are in the appendix) that show that the function 1 max[]|=>|| vn ||0||1] a norm and construct a congruence inequality for it:
Lemma The function max (doo (a,, H2), Ja di (a,, H2)} is distance induced by the norm max[[]=]]ee] [
Lemma 4. The norm max ( Jal [a]ll satisfies the congruence inequality
n | I max ||0||oo Ja 11l12l11 $ ||x||2
Crucially, the following holds:
Corollary Combining Lemma with Theorem 7 the multi-norn relaxation k-HC satisfies
1 (PT()-HQ22)) S OPT(K-HC (mull))) S (2..
SOLVING THE STRENGTHENED FORMULATIONS OF l: (--HC(2,1) VIA SBB
We now focus solving (-HC global optimality via SBB. We analyze the number of SBB nodes needed to compute nonzero global lower bound when solving a basic formulation of the problem, and then prove that intersecting the basic formulation for k-HC with one of our re- laxations involving polyhedral norms allows for computing a nonzero global lower bound much earlier.
4.1 SPATIAL BRANCH-AND-BOUND
The basic idea of the spatial branch-and-bound (SBB) method is build a dual bound by optimizing over convex (typically polyhedral) envelope conv(F) of the feasible region F of the problem. F then split into two sub-regions Fi and F22 with tighter bounds on least one variable. This allows for constructing tighter convex envelopes of F1 and F2 in such way that the optimal solution over conv (F') is cut off because does not belong to conv U conv(F2). Fi and F2 are then recursively optimized in classical divide-et-impera manch-and-bounde fashion within binary- tree search scheme.
Let consider the case of k-HC We assume (as done by most of the state-of-the-arr solvers such as Gurobi Gurobi Optimization, LLC (2026)) that polyhedral envelopes are employed. Under such assumption, when considering the nonlinear constraints ||wr 1 En= w3n 2 1, E [M),
5

---

classical SBB method first introduces the auxiliary variable 2yh for each nonlinear term w2, and corresponding defining constraint 2yh wihh It then substitutes the original nonlinear constraint with Σx=1 2jh 1. Each defining constraint is then relaxed into a polyhedral envelope. The point-wise minimal outer envelope of bilinear product corresponds to the well-known McCormick envelope McCormick (1766).
4.2 BASELINE MATHEMATICAL PROGRAMMING FORMULATION FOR (2,1)
We start by considering as baseline the following classical Mixed Integer Quadratically Con- strained Quadratic Programming (MI-QCQP) formulation for (2.1( Coniglio (001 & Coniglio (2013):
Amaldi
Σjn Ti==1 =1 1will2
Vi E [m]]
Vj E [k]
(k-HC(221))
min (w.r),,dd
df
d, z wj 0; -
d Fig)
Vi E [m].j] E [A]
d, 2, wy + d (1 miy)
Vi E [m]:j E [A]
In it, Faj (0, takes value if and only if a; is assigned to the hyperplane of index j [k]]
d, is the distance between a, and the hyperplane of index j E [A]] d is an upper bound the largest distance between any point a; and hyperplane of index E [k.. The only nonconvexity of the formulation is due to the 2-norm constraints. W.l.o.g., assume a, for all i [m]] (as this can be easily obtained in a preprocessing step by translating the dataset). The following bounds on the variables can be included. We let d := ||b ell2. where is the all-one vector and 6 the length of the edge of the smallest hypercube that contains {a1..... Jm J. Since |/wll2 = holds in any optimal solution and max max[[|u) || || 1l 1} = we impose ||w,||so j E [k). These bounds imply nbb d² S5 S nb d j [R:].
via -e S Wy S e,
Since the point-to-hypen t-ype-lllaeee distance is symmetric, given any solution to H- an equivalent one can be obtained by changing the sign of wi for some j E [k]. To remove such a symmetry (symmetries are known be a hindrance when solving mathematical programming problems to optimality via methods based on (spatial)
saanchandd-bund) we impose wy to belong to an arbitrary half-space of R for each j E [k]] by imposing wy1 2 0.J E [k.. where Wyn is the first component of wy In this way, any solution that is obtainable by changing the sign of component of one of the vectors w becomes infeasible (due to being obtained from the previous one by reflection of w over the hyperplane defining the halfspace that we selected), thus breaking the symmetry. In all our formulations, we partially remove the symmetry on Tajs á E [m],j E [k), that is induced by the assignment constraints by imposing Tij 0 for all i,j E [m] x [k] with < j. This reduces the number 0-1 variables by (k-1)
4.3 SOLVING THE FORMULATION (k-HC(2,1) VIA SBB
Let analyze the behavior of standard SBB method employed for solving the classical formulation (k-HC Since the projection onto the w space of the feasible region of k-HC nonconvex and its complement symmetric about the origin, any SBB method based on convex envelopes will necessarily convexify the infeasible region, thus making the trivial solution w = 0,j [k), feasible. This leads to bound weak as possible due the fact that the objective function is the sum of squares Σ 1= df 2 0 and, with (w), 75) = 0, j E [k], we obtain Σ d
The following assumption holds in most SBB codes see, e.g., Belotti et al. (009)
Assumption 1. Assume that, when spatially branching variables with symmetric domain, branching takes place on the midpoint of the domain.
Notice that, with the bounds we included, the domain Wyn- j E [k], E [m], is symmetric.
Crucially, under Assumption I the geometry of the feasible region of H--H makes it so that the number of branching operations that are needed to make the solution infeasible (and, thus, compute nonzero global lower bound) is exponentially large (the proof is in the appendix):

---

Proposition 2. Under Assumption 7 when solving (2,1) nonzero lower bound is obtained only after generating least 2 1) branching nodes.
This is particularly bad since, until the first nonzero lower bound has been calculated, no pruning happen the tree due to the fact that a lower bound of O trivially holds at any node since the objective function a sum of squares.
4.4 STRENGTHENED FORMULATIONS
We now construct valid formulations for k-HC2 which are strengthened by featuring not only the 2-norm constraints but also a collection of polyhedral-noma constraints. Building on the relaxations we constructed before, we introduce the following three strengthened formulations (in each of them, the norm constraints imposed for all j E [A]):
(2.HC
min (w,)7
min [[a]] Wy - 7})
2 [0
sE[R]
2
|m
1 2 1
(k-HC (1.
min (10,7)
min {(a} T Wy - 73))
|wj
jE(k]
lwy 12 1
(2.
min (w8,7)
Σ min {a, Wy 71) jE(k]
Before analyzing the number of branching operations needed to achieve a nonzero lower bound with these formulations, report the Mixed Integer Linear Programming (MILP) formulations by which we formulate the polyhedral-norm constraints.
1-norm. We formulate the constraints ||wy]|ı 2 1, E [k)) via the following absolute-value refor- mulation:
w jh W jh with
j E [k), [n]
(1a)
wi S 8jh
j jE [k], h E [n]
(1b)
" jn S (1 sjh))
j [k], [n]
(1c)
(wth +Wih) 2
j [k]
(Id)
5 w th Wihh S1
i [k),, h E [n]
(Ie)
89h E [0.1)
j E [k), E [m]
(1f)
The binary variable syh denotes the sign of the h-th component of wy- Consider component wys of index h of wy. Due to Constraints Ia--le 0) and syh 1. Otherwise, if wy O, then w > 0 (with w = and Wynh - Wyh) and syh = 0. Since w and w are component- wise complementary thanks to Constraints (b) Ich. we deduce that w + w -|wy| holds. Thus, Constraint [d] guarantees ||wy]l 2 1. When these constraints are imposed, we break symmetry mentioned before by imposing wy1 2 0, E [k]. This leads to 851 = 1 and Wii = 0, thanks to which Constraint (1d) becomes Wy1 + 2 (w)) tw 2 1.
Ic if wyn > then w > 0 (with w Wigh and Wia
oo-norm. We formulate the constraints ||w > Ja.J j [k), i.e., maxnetn| [w 2 -
j [k], as the disjunction Vã (w3h < - V wyn 2 ) .j. [K]. Differently from the pre- vious cases, in this case break symmetry by (w.l.o.g.) always selecting Wihh 2 v from each elementary disjunction Wish v 1
v Wih 2 1 This translates into considering the restricted
disjunction Vi Winh 2 ) E [k). For each j E [k], we restate the resulting disjunctive set
7

---

via the following MILP formulation:
wsh +1+
1
ush
j E [Rt], h E [n]
(2a)
vn
Uih
j e [k]
(2b)
h=1
Ujh E {0,
j [6]. E [n].
(2c)
Due to Constraint (2ah. if Uih = 1 holds for some h E [n]] then wish 2 + holds (the constraint is
inactive if Uih 0. and reads wynh 2 -1). Constraint 2b imposes that exactly one component of
U = (U)1.... Uyn) is equal to I.
When imposing multiple norm constraints once, only have to pay attention the way sym- metry is prevented, as the symmetry-breaking constraint W'1 2 0 we introduced for the constraints ||w 2 j [k]] and ||wy]li 2 1, E [K], is not compatible with the one-sided disjunction considered for |/ || sc v J [k.]. and imposing both would lead to over-restriction. When- ever the || 2 v
1 constraints are imposed, we resolve the issue by dropping the symmetry-
breaking constraints Wy1 2 0. j E [R:.
4.5 SOLVING THE STRENGTHENED FORMULATIONS VIA SBB
We extend the analysis in Proposition 2 to the strengthened formulations with the following two propositions (the proofs of both are contained in the appendix):
Proposition 3. Assume that the constraint ||wyl| 2 1, E [k), is imposed and that branching takes place on the 83h variables first. Then, nonzero global lower bound is obtained after generating at least ( 1) nodes. If (oe.) is being solved, no further branching on w takes place.
Proposition 4. Assume that ||w Z - j E [k)], is imposed and that branching takes place on the Uih variables first. Then, k(n-1) nodes suffice to obtain nonzero lower bound. If k--H (1, )
is being solved, no further branching on w takes place.
Propositions 3 and show the crucial advantages strengthening formulation (k-HC(g,,) as we proposed via the two (scaled) polyhedral-norm constraints considered. Proposition [ indicates that, the ||,||| 2 1, E [k:]. constraints are imposed and branching takes place on the 0-1 variables of such norm constraints, in a complete SBB tree of depth ((2k(=1)) the polyhedral- norm constraint satisfied in every leaf node. This in stark contrast to the 2-norm case, where the same number of branching operations only suffices to obtain the first nonzero global lower bound, and the number of branchings needed to completely describe the feasible region of the problem in the space depends on the solver's feasibility tolerance (since, for each E [k). the complement of the feasible region is sphere).
Va E [k). constraints are imposed and branching takes place on their 0-1 variables, the size of the SBB tree is extremely small-oni] polynomial in k and n. The difference between the two results is due to the geometry of the 1- and co-norm balls with > 2, since the former has 2 facets while the latter only 2n.
Crucially, Proposition 4 shows that, when the ||w 2
When included in formulation for k-HC2 on top of the constraints ||wy|la ll2 2 1,J E [k]. the polyhedral-none constraints substantially accelerate the computation of a nonzero global lower bound, leading to more pruning and, overall, to faster SBB method. This is better shown in the next section.
5 COMPUTATIONAL. RESULTS
We assess the effectiveness of our strengthened formulations with Gurobi 10's SBB using 12 threads on a 2.6GHz Intel Core i7-9750H equipped with 32 GB RAM, with a total time limit across the 12 cores of 168,000 seconds (46 hours).
8

---

We consider two testbeds: Low-dim and High-dim. Low-dim contains 43 instances with m = 10......................... .30 n = 2,3, and = 2.3. These instances are a superset of the 24 instances tackled with SBB techniques in Amaldii & Coniglo (013). High-dim contains 43 instances with m = 10,.... 17, n = 2, 3, 4, 5, and k = 2.3, 4,5. Both datasets are generated by randomly choos- ing (g) J E [k), with uniform distribution in [-1,1] and distributing uniformly random the m points such that each of them belongs (with 0 distance) to a hyperplane. Then, an orthog- onal deviation from the corresponding hyperplane is added to each point by sampling a Gaussian distribution with O mean and variance that is selected, for each hyperplane, uniformly at random in [0.7- 0.003, 0.003]. Details on how to access and run our code as well as on how to access the dataset we used in the experiment are reported in the appendix.
(k-HC(2.1)), (L-HC (c....). and ((-ub...)) Tables 1 and 2 report, for each formulation, the median computing time on the subset of instances solved by all four, the median speed-up relative to (k-HC and the Holm- corrected (with a family-wise error rate a = 0.05) p-value of a two-sided Wilcoxon signed-rank test against (2,
We consider four formulations:
Table I: LowDim: comparison to (k-HC on the 20 instances solved by all four formula- tions.
Table 2: HighDim: comparison to (k-HC the 30 instances solved by all four formula- tions.
Algorithm
Median (s)
Speed-up
p-value
Algorithm
Median (s)
Speed-up
p-value
(k-HG (k-HC) (aat, (hr
169.9
1x
(A-HC
208.6
1x
4.15
40.9%
10
(I-HC (aasves (e))
18.30
11.5%
5.6 10 -9
(l-HC 1 (ouH))
6,10
27.9x
10
(I-HC (a,,C
20.65
10.1x
7.5
10-9
5.00
34.0%
1.1 x 10-4
(A-HC
37.35
5.6%
8.7 x 10-
Detailed results are reported in Tables 3 and 4 three strengthened formulations (H-HC (I-HC and (I-HC 21 instances that are not solved in over 46 hours with the classical formulation (k-HC(2.1)) are solved in under 2 hours. With the strengthened formulations, the 20 instances that are also solved with the classical formulation are solved, respectively, 41, 28, and 34 times faster. Incidentally, our results on the imw testbed prove that all the heuristic solutions found in Amaldi & Coniglio (2013) on the 24 instances considered in that work (those with m 10, 14, 18, 22, 26, 30) are optimal.
Let us focus first on the Low- dim testbed. With the
Let us turn now to the High--ins testbed. On it, with the best-performing strengthened formulation we manage to solve 10 more instances than with the classical formulation. With the strengthened formulations, the 30 instances that are also solved with the classical formulation are solved, respec- tively, 12, 10, and 6 times faster.
Notice that the speedup obtained with (2- is smaller than those obtained with (o. and (f-HC Such behavior is well explained by the results of Propo- sitions and 4 As n and l: increase, the difference between the exponential lower bound on the number of nodes required to obtain a nonzero global lower bound in the first proposition and the polynomial one in the second one becomes larger and larger. Thus, any branching operations taking place on the constraints
||wح|| 2 1 have a much smaller impact on the bound than those taking
place on the ||wylloo 2 Vn E [k), which explains the superior performance of (k:-HC (2.1),
6 CONCLUDING REMARKS
We have focused on solving the 2-norm k-Hyperplane Clustering problem with spatial branch-and- bound (SBB) techniques by strengthening the classical formulation with constraints that arise from (scaled) p-norm formulations of the problem, with p + 2. Focusing on the and co-norms, we have theoretically shown that including the constraints stemming from the 1-norm version of the problem (featuring scaled oc-norm constraints) leads to computing nonzero lower bounds in a linear (rather than exponential) number of SBB nodes. Our experimental results show very large speedups, reducing median solve times by up to 41x while increasing the total number of solved instances by up to 63%, substantially improving the problem's solvability global optimality.

---

Table 3: Results on the LowD im dataset
Table 4: Results on the HighDim dataset
(I-HC (2.C(a.. D.0 t
(A-BC (A. (oe...))
(oni(o 13)
(A-HC Comils 41)
(I-HC
(1-)C(2.1))
(I-HC (2.
(E-HC
time obj
time obj
time
obj
time
obj
&
time obj
time obj
time ebj
time abj
0.3
0.0
0.7 0.5
0.5
0.5
1,0
6.1
0.0
3.9 0.0
1.6 8.5
0.6
8.5
8.5
11
21.9
5.9
0.]
17.7
0.1
14
31.9 0.8
4.4
0.8
3,4
0.8
5.4
0.8
11
1264.3 0.0
392.8
0.0
300.2
0.0
2689.7
0.0
18
13.9
3.4
0.4
3.4
0.4
3,4
0.7
3,4
11
5,4 0.0
166
0.0
1.5 00
2.1 0.0
18
488.9
0.7
3.9
0.7
4,4
0.7
4.6
0.7
12
79.4 0.1
17.0
0.1
8.1
0.1
30.5
0.1
22
179.2 9.7
1.7
9.7
1,4
9.7
0.9
9.7
12
425.6 0.0
160.4
0.0
56.8
0.0
282.8
0.0
22
2213.3
2.4
11.2
2.4
11.2
24
98
24
12
17.3 0.1
1.2
0.1
7.7 0.1
10.1
0.1
25
28.9
8.2
0.6
8.2
0.4
8.2
1.4
8.2
12
2
29.3 0.0
14.4
0.0
16.4
0.0
26. 0.0
25
2
168000000
2.7
936.6
2.7
96.1
2.7
221.0
2.7
13
4
238.2 D.I
1944
0.1
14.6
0.1
18.4 0.1
26
2
1680010.0
6.2
5.8
10.4
5.8
2.2
5.8
13
935.1
D.0
127.1
0.0
55.8
0.0
170.7
0.0
26
2
0680000.0
39.2
3.4
$6.6
344
28.3
34
13
4143.7 D.
7562.6
0.0
1680000
168000.0)
27
2
0680
0.7
5.1
2.6
5.1
088
5.1
13
13.0 0.1
6.5
0.1
2.1
0.1
9.3 0.1
27
2
168000.0
1678.4
3.3
2687.7
3.3
238.6
3.3
13
948,7 0.0
567.1
712.6
0.0
4625.7
0.0
28
2
168000.0
86
11.7
18
11.7
47.0
11.1
0.1
28
2
168000.0
293.1
3.6
471.3
153.5
14
683.1
22.4
0.2
55.8 0.2
2
168000.0
7.1
6526.6
586.0
0.0
168000.0
7694.9
7.1
6029.0
1476.4
1680000
2752.6
2784.8
7540.2
0.0
168000.0
58.5
9.6 0.5
2
168000.0
1447.5
6906.7
1.1 0.9
0.0
32.6
0.0
31.9
41,9
13806
0.3
0.7
0.8
0.7
58542
320.5
0.0
206.4
0.1
29.7
0.1
25,5
0,1
49.7
T00
15
168010,0
276088
0/0
1772.1
0.0
168000.
18
160.6
0.7
1.7
0.7
7,8
0,7
0.7
15
37.5 06
5-8
0.6
8.4
0.6
9.2
0.6
18
2234.9
0.4
93.4
0.4
91.6
0,4
157,9
0.4
13
38030 DO
5156
0.0
439.4
0.0
2208.3
0.0
22
025.0
4.3
18.6
4.3
11.3
4.3
108
4.1
15
9 TU
18-5
40.7
0.1
35.0
0.1
22
135.629
1.3
1089.5
1.3
638.2
1.3
1243.7
1.3
16
5 0.
1196
f1.2
28.9
0.2
67.3
0.2
23
3
6459.4
0.9
8.1
0.9
45.5
0,9
10.1
0.9
16
168000.0
S826
0.0
346.6
0.0
781.9
0.0
24
3
18049.6
6.9
66.3
6.9
474.7
6.9
34,5
6.9
16
1680000
4586.5
0.0
2407.2
0.0
168000.0
24
3
160010.0
1.7
2470.6
1.5
2716.7
1.5
3817.0
1.5
16
165000.0
168000.0
169000.0
168000.0
25
3
278669
5.7
70.7
5.7
28.1
5.7
14.2
5.7
16
179, 111
12.9
1.1
15.0 1.1
12.
1.1
25
3
660000.
1.3
1952.
1.3
5060.3
1.1
2885.1
1.3
16
5144.2 0.
554.5
0.0
601.1 0.0
2507.3
0.0
26
3
6.3
4.5
4.7
4.5
4.4
4.5
16
444.9 08
28.5
43.2 0.8
60.8
0.8
26
3
0
3937.9
1.3
4345.7
1.3
2300.2
1.3
17
168010.0
0.2
37.1
42.1 0.2
69.2
0.2
27
3
160000.0
215.1
3.4
1274.8
3.4
58.5
3.4
17
160010.0
0.1
1452.3
999,4 0.1
1517.1
0.1
27
3
168000.0
52548.9
2.9
65949.3
2.9
35206.1
2.9
17
1680000
4970.5
2553.9 0.0
168000.0
28
3
168000.0
31.1
3.6
1.7
10.2
17
1680100
168000.0
0.5 168000.0
168000.0
168000.0
4234.9
74560.6
4180.9
175.7
9.8 0.5
168000.0
143.5
$4.0
0.0
168000.0
168000.0
168000.0
168000.0
8218.2
8083.1
1680000
3014.8
1092.7
97.4
1010
168000.0
23488.8
168000.
6541.5
168000.0
8116.4
7910.9
# Sol
20
42
40
42
#
31
41
40
37
An interesting research direction for future work is exploring the connection between k-HC and sub- space clustering, in particular related to the recent literature coresets for projective clustering and subspace approximation Rademacher et al. y; /Shhler & Woodruff (2018); Eiben et al.) (2021). These techniques allow us to construct small, weighted subsets of data that preserve the clustering cost within a (1 +)) factor. Integrating such coreset constructions with our exact SBB-based solver could yield a hybrid approach (approximate in data, but exact in optimization), combining scalability with provable global optimality guarantees.
ACKNOWLEDGEMENT OF SUPPORT
The author's work was partially supported by the European Union under Next Generation EU the Italian National Recovery and Resilience Plan (PNRR), PRIN 2022 PNRR (project code P20227CTY3, CUP gorithms for Grid Operations at the National level".
project title "HEXAGON: Highly-specialized EXact Al-
10

---

REPRODUCIBILITY STATEMENT
The author provided all the necessary information to facilitate the reproducibility of the results. The code developed for this work is made available online (see Appendix) and freely distributed under the MIT license
ETHICS STATEMENT
All datasets employed in this work are publicly available for research and contain personally identifiable information or harmful content. 'he methods introduced in this paper have a societal impact comparable to that of any other clustering algorithm.
LLM USAGE STATEMENT
All technical content presented in this paper is entirely the work of the author, with LLMs serving only an editorial tool.
REFERENCES
Amaldi and Coniglio. distance-based point-reassignment heuristic for the k-hyperplane clustering problem. European Journal of Operational Research, 227(1):22-29, 2013.
E. Amaldi M. Mattavelli. The MIN PFS problem and piecewise linear model estimation. Discrete Applied Mathematics,
2002.
E. Amaldi, K. Dhyani, and Ceselli. Column generation for the minimum hyperplanes clustering problem. INFORMS Journal Computing, 25(3):446-460, 2013.
E. Amaldi, S. Coniglio, and L. Taccari. Discrete optimization methods to fit piecewise affine models to data points. Computers & Operations Research, 75:214-230 2016.
Belotti, Lee, L. Liberti, F. Margot, and A. Wächter. Branching and bound tightening techniques for non-convex MINLP. Optimization methods and software, 24:597-634, 2009.
Bradely and O.L. Mangasarian. k-plane clustering. Journal of Global Optimization, 16:23-32, 2000.
Coniglio. The impact of the norm on the k-hyperplane clustering problem: relaxations. restric- tions, approximation factors, and exact formulations. In Proceedings of the 10th CTW Graphs and Combinatorial Optimization, pp. 118-121, 2011.
K. Dhyani and L. Liberti. Mathematical programming formulations for the bottleneck hyperplane clustering problem. In Proceedings of Modelling, Computation and Optimization in Information Systems and Management Sciences, volume 14, pp. 87-96, 2008.
E. Eiben, F.V. Fomin, P.A. Golovach, W. Lochet, F. Panolan, and K. Simonov. Eptas for k-means clustering of affine subspaces. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2649-2659, SIAM, 2021.
G. Ferrari-Trecale M. Muselli, D. Liberati, and M. Morari. A clustering technique for the identifi- cation of piecewise affine systems. Automatica, 39:205-217, 2003.
Georgiev, P. Pardalos, and F. Theis. A bilinear algorithm for sparse representations. Computa- tionals Optimization and Applications, 38(2):49-225, 2007.
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2026. URL https::////r
gurobi com
https://chocseall wwwse..o.//.ceeeeeeeeeeee

---

H. He and Z. Qin. A k-hyperplane-bart based neural network for non- non-linear regression. In 9th IEEE International Conference on Cognitive Informatics (ICCI 10), pp. 783-787. IEEE, 2010.
Z. He and A. Cichocki. An efficient k-hyperplane clustering algorithm and its application to sparse component analysis. International Symposium on Neural Networks, pp. 1032-1041. Springer, 2007.
D. Kong, L. Xu, X. Li, and S. Li. K-plane-based classification of airborne lidar data for accurate building roof measurement. IEEE Transactions Instrumentation and Measurement, 63(5): 1200-1214, 2013.
J. MacQueen. Some methods for classification and analysis of multivariate observations. In Pro- ceedings of the fifth Berkeley symposium on mathematical statistics and probability, volume (14), pp. 281-297. Oakland, CA, USA, 1967.
O.L. Mangasarian. Arbitrary-nom separating plane. Operations Research Letters, 24(1-2):15-23, 1999.
G. McCormick. Computability of global solutions to factorable nonconvex programs: Part convex underestimating problems. Math. Progm., 10:146-175. 1976.
N. Megiddo and A. Tamir. On the complexity of locating linear facilities the plane. Operations research letters, 1(5):194-17,, 1982.
Rademacher, S. Vempala, and G. Wang. Matrix approximation and projective clustering via iterative sampling. 2005.
C. Sohler and D.P. Woodruff. Strong coresets for k- k-median and subspace approximation: Goodbye dimension. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 802-813. IEEE, 2018.
M.C. Tsakiris and R. Vidal. Hyperplane clustering via dual principal component pursuit. In Inter- national conference on machine learning, pp. 3472-3481. PMLR, 2017.
Y. Washizawa and A. Cichocki. On-line k-plane clustering learning algorithm for sparse component analysis. 2006 IEEE International Conference on Acoustics Speech and Signal Processing Proceedings, volume 5, pp. V-V. IEEE, 2006.
y. Zhang, h. Wang, W. Wang, and S. Sanei. K- K-plane clustering algorithm for analysis dictionary learning. In 2013 IEEE International Workshop on Machine Learning for Signal Processing (MLSP), pp. 1-4. IEEE, 2013.
A CODE REPOSITORY AND LICENSING
The code used for the experiments is freely available under the MIT license (https:/) choosea wwtp:/eee..ommiicceeeeeeeeee
and is available at https: com/
B FURTHER COMPUTATIONAL RESULTS
Table 5 reports the total node counts for the HighDim dataset. This provides clearer picture of relative tree sizes and convergence behavior across formulations. The results confirm the theoretical
analysis, with the (A-HC (H- (A-HC and (k-HC,mmuti,,))) formula-
tions generating, respectively, 7,987,723.07, 3,201,881.49 2.741.496.67, and 4.632,264.51 nodes on average.
12

---

Table 5: HighDim instances: total SBB node counts by formulation.
(k (R,1I)(),1)) (k-1IC
(2,13. vi
(I:IIC(2.1).ww.1)) (1)tt))))))
10
4
38 392
16.257
10.301
23 588
10
2
17033
4739
18 112
169937
11
168
29 502
868
565
890
11
404
3701
6989
8.844
12
287 736
45 100
22 786
755515
12
228 060
440626
063
687 073
743
820
19455
26
791
52 720
13
261 440
347 674
070
383 310
13
4
11 864 400
19678 500
23810 300
18 600 100
063
19 382
24 744
080
646
13
139 309
24034
346
48 397
355 780
667
34
166 633
14
19 826 01X)
2014470
515
5829970 970
14
21 01 800
5928 130
446 500
16 33000660
10637
15814
696
690
9144490
14396 900
367 215
34.000
4063
67 349
15
4
819 300
88 293
63 762
142.999
15
15 120 700
815961
240 698
005 150
20 797 200
68 821 170
290
17 132 800
14
15
399 350
068 560
949
4432 280
15
285 279
25 590
83 182
63 958
16
20072 700
387 933
122
177 715
18 348
839 480
977
550
16 743 900
16 840 700
925 600
14 859 600
16
622 968
29 784
34 762
25 049
16
12 307 300
297 660
759
4 850
41 490
66 069
490
740
17
18 531 600
5774570
1036 550
3 622 780
17
18 137 400
10911 800
361 730
165 600
17
16 997 500
15721 000
16018 000
87 100
599 093
22 341
2034 660
18 985
17
16 580
14203 900
13111
12 700
17
3 190 660
187 282
217 843
189 688
17
3
16.000 600
15.857 000
12:400 800
13 129-400
C
LIST OF OUR THEORETICAL RESULTS WITH THE CORRESPONDING PROOFS
ITT Proposition Given hyperplane H := {a ER" x w = 7 and a point a E IR", the function
H)
- [o
a- where 1 1 L, is a nonconvex functtionnn of (w, (w,y) for every p N NU (00).
T e-7l is convex function of (w,, 7) and only if the following holds for Proof. By definition, T|mlll every (W1, 71) and (w2, 72) E g=+1 and [0, 1]:
[ a - -71l + (1 A)
Ww a 721
2
| 1|
|| | 1
[Awu + (1 2)w2) TT (Ar + 2)722
[!w] + (1 A)wal11 Ilp'
Let p' E Let a 00 and consider two hyperplanes of parameters wi := -1,- ) =
and
W/2 = (- 1),72 72 = Let = 71 = 72. Letting X = 2. Inequality reads:
1
+ 2 1/1+ (2)
(4)
2 \/1 + (2)
((2) + (2)
or, equivalently:
(=)) p' + (G) N 1+ 5
Taking both sides to the p'tth power, we have 2 (2) hand side and multiplying both sides by 52", deduce 2. 2p'
2 + (
After moving to the left-
52', which implies 22'
13

---

2 2.2% - 5.' As (3)²² > 2 holds for every p' E NU {oo} (as one can see by setting p' to its smallest value, i.c. setting p' = 1), Inequality (DEN) (1)
is proven not to hold for any choice of p' E N
Let us consider the case p' oo now. With w1 (1,-5) and w2 - 1), we have | =
|| = and, with À = 1 5n we obtain |l (we + w2)ll = 1l (1 3l = Substituting these
values directly into equation leads to
サ 2 2
which does not hold, showing that convexity fails to hold also for p' 00 (p- 1).
Lemma 1. The solutions (k)HC and (k-HC2) coincide. Also, (k-HC(p.e) is quadratically homogeneous w.r.t e, i.e. (p) = e² OPT(K-HC((.)).
Proof. We start by showing that (2-HC and (k-HC2) are equivalent when c = 1 and p 2. Indeed, as n points in general position fix hyperplane in R", only of the + parameters be imposed w.l.o.g. for all as I|w]|2 2 1 is w.w.o.g.. as the latter is tight in any optimal solution- indeed, if not, strictly better solution can be found by scaling (wy, 75) by [wylllr E [A]]. Let ((wj:7s)]sep) be an optimal solution to (k-HC(p.c))- As argued, ||w, lle = e. holds. Let now (u), 1/) = (wwm)) E [k:]. Such a scaled solution satisfies ||wý 1 for all j E [R] and, thus, is feasible for (p.HH)..1))) ). Its objective function value is + times the one of (ww,,7))) yy)) Since such a multiplicative difference is a constant, the scaled solution is also optimal for (k-HC(p,1)) Thus, we have OPT(K-HC = d² OPT(A-HC(..)).
(wy. (3) E R=+1 are independent. Thus, ||w51
j E [k). Relaxing ||æll2
Theorem 1. Let p ENUUE (oo) and which, for all x E IR", satisfy the congruence inequality a(p, 4)||=||p, I 3(p, باح|اا/ S 8(p, @1l=lllfoopp e Nufoc} also satisfy the optimal-value inequality a(p.4) (PC S
The three positive scalars adp, 4), 3(, 0())
Ø(p.q)²
OPT
k-HC
Bip.a) (a.e 3(p.o)
OPP((k-HC(p.)).
Proof. The inequality
min f(x) S min f'(x) S min (x) #EX
(5)
xEX
xEX
clearly holds for any three functions f. X C R.. Since vector norms in IR" are congruent, for every p. E NU (00) there are three positive scalars a(p, 4), ((p,4), 00,5(pp.) q) which satisfy alp, ا)||ا(ي S B(p, ((p/1)][=/|g < ō(p, |>|| for p.q E Nu (oo). Since, by definition, da H) minyeH ||a vllp- equation leads to the following congruence relationship for point-to-hyper --hhperrlaae distances that holds for every hyperplane Hl in [ and point a E R.
R satisfying f(x) < fx)) S fz)) for all
a(p, 4) (a, H) S ((..9)d,(a, S 8(p, (a, H).
(6)
Squaring equation 6 and letting Hi...., Ha be arbitrary choice of hyperplanes, another appli- cation equation leads to
((p. q)² min (d (a,, H2)pp s 3(p. 9) min fd Hy)g) s () min (d H,)p jE(m]
(7)
jE(H]
This was already observed in Amaldi & Coniglio 2013). following.
The proof we provide here will be useful in the
14

---

Summing equation 7 over all data points with unit multipliers, obtain the following surrogate inequality:
m
ap,, q)²
min dd (ai, H2)p) z
jc
m
B(p, 2)
min {d (a;, Hj)a} S jE[l]
(a
8(p, q)²
Σ i=1
min d (a;, H2) jE(M]
Applying again equation 5 by letting the minimization consider the choice of optimal parameters for the hyperplanes Hj.j E [k], we deduce a(p, q)² OPT(A-HC(p.1) S g) (x) S
5(p, 2)² OPT(k-HC (p.1)) Multiplying through by e² and using Lemma
[ we obtain
(p. g)² (k-CH-CC.pp)
S 3(p,g) OPT(K-HC((.o) s 8(p, q)² (PT (p.))). By using the
quadratic homogeneity property of Lemma one more time, we deduce 3(p, q) OPT OPT(K-HC (GCC(H-)C (g.c((pa))))
which allows us to write:
alp. 9)² (P-( & ((C - 6(p, q)² (p.)))
Dividing all three terms by 5(p. q)2 and applying Lemmal one last time remove the coefficient B(p.a)z that would otherwise multiply the inner term, the claim follows.
Corollary 1. (oe,() and k-HC ) satisfy:
(PT((-HC((21) < (PC (P.(
OPT(K-HC(2.)) & OPT(K-HC )ه)) S OPT(K-HC(21))
Proof. We rely the following congruence relationships (see Proposition 5f for their derivation):
|=|| < || < |0ll2
||0l v ||>||| S ||01|2
Thanks to Theorem
|xl|| I ||0||oo S |al|a implies
OPT (C: (2.1)) S OP- (o..)) S (P.
Thanks to Theorem
| - + | - | implies
Vn
OPT(k- < OPT(K-HC OPT(L-HC
which, due Lemma
implies
OPT(K-HC (PC (2) OPT((-HC
n
Lemma 2. Solving k-HC subject to min ([[w]] Vollw]>>>> coincides with solving an uncon- strained version of k-HC where the point-to-hyper noint-to-hyperplane distance between as and H3 is defined as max(doo (a, H2), 1 di (a,, H,)). Jn
Proof. As a consequence of Lemma imposing min [/|w|h, vnl [w]lo)))))))))))))))))))) 2 in the context of k- HC implies imposing min [|/w|| / wil boo) in any optimal solution and, thus, accounting for
the distance between and H, la wy - >l min I [ We rewrite the latter as la wyy--y weTT,->l3 max || m
lo wy wy-2l
max (o] w.--,, -yl
(a] wy -y 1 |o w. -11 max(d (a, H,), Jn ddi di H,))-
||
15

---

Figure 3: Sets of points satisfying || = (inner circle) and max || 1 [ 1 (outer octagon).
1 Lemma The function maxfd (a;, Hj), va (1,, Hj)} is distance induced by the norm max [lxlle=loe, 1 [=
Proof. Let us show that max([]<]]ea J ||<]|]] } is norm in three steps.
Positive definiteness. First, it is clear that max (I] [1 0 if and only if 0.
and that
max(ll=llo + ||=/|11]
II. Absolute homogeneity. Second, it is also clear that |A] max Vn ||=||1) |a 2 for all X E IR.
III. Triangle inequality. Third, we must show that
maxf]læ + ylloo. || + v111 I max - ||0||1] + max 11vll
(8)
holds for any x, y E R", To see this, we first notice that
1
|| + ulloc |o|||
llvlls
and
|| vlla
|
Ilvlla
vn
vn
hold since these functions are norms. Taking the maximum of the left-hand and right-hand sides of these two inequalities, thanks to the monotonicity max we have:
max{| + vlloo - || +
vlli} max/||æ/|>> llvlloo
||ح||||
+
(9)
vn
To show that this implies that the triangle inequality is satisfied, show that, for any b, d 2 0, we have
maxfa + c, b d} S max(a, b} max(c, d}.
(10)
Trivially, we have a I max(a, b). max(a, b). e max(c. d}. and 5 maxfc, d). Adding the inequalities in pairs, we obtain a S max(a, b) max(c, cc d} and b+ < max(a, (,, b) maxf d). Taking the maximum of the left- and right-hand sides and applying again the monotonicity max, we deduce equation TO
Letting now := || :== llv|lso, b Jn ||a1|11, and == /nl Illll from equation 10 we have
1
1 || [|v|aa] s max([|=|]oe> vn
max(|] + Illlloo
|
+ max [lv|loo.
[|
(11)
Combining equation 11 with equation
equation g proven.
16

---

We have shown that max |||| -े ||=|| max (a,, Hj), de (a,, H2)} is a distance follows straightforwardy by following the
is norm.
Showing that
classical construction of point-to-hypepplane distances.
An illustration of the function max ||||| oo -े [ } is provided in Figure 3
Lemma 4. The norm max
||
loo
Vi | satisfies the congruence inequality
| I max || Jaa [allll } s ||0/|/2
n
Proof. We prove the congruence relationship in two steps.
1. Second part. From the second part of each of the two congruence relationships
/ | ||0|| |
Vnll ||01|2 v vn |||||| s ||0||2,
directly deduce max Ja |+]|||] s ||
II. First part. To prove the first part of the congruence, we establish what the largest value of ||0||2 when x is subject to max(]]=rloo, V/2 [|]|||]] S
Let S = {x E R" || < 1, va | S 1}, or, equivalently, S = fx R" | S 1, ||=|| S vnj. Let r be the fractional part of vī, i..., r == - lv E (0,1). We'll prove that every maximizer of |æl|| over S has most one fractional component in (0,1) and, in particular, that x² (1, (I...... 1, O,..., 0) is one such maximizer with objective function value
Iyn
max ||0||| VL +r².
Since S is symmetric under sign flips and coordinate permutations, we can w.l.o.g. restrict ourselves to vectors x R" with rı x22 2 2 In 2 0 and consider the equivalent problem
(P)
max
r [0,1)"
(i) First, we show that constraint Σ Th V is tight in any optimal solution. This is because, if not, we could increase each T; until either 1 or Em = -vn, thereby increasing the objective function Σ x7
(ii) Second, we show that any optimal solution features most one fractional component. Suppose that x is feasible with Σ = /n with 0 < < 1 and 0 < 2j < 1 for some i * [n]. W.l.o.g., assume F; 2 Tz. Pick some > with x; + E S and x, 2 O, and define ž as
T. = Zú + te, T. = Ij E, and 3t 2e for all & E [n] with l + i,j. Then,
12
Σ 7 - Σ x = (5) + +
27 -
2 x.) + + > 0.
20
This shows that any with two fractional entries is suboptimal.
(iii) Let x be an optimal solution with t ones, one fractional component r E [0, 1) (or none if = 0), /ni which (since is
and n 1 1 zeros. Since Σ 24 / is tight, we deduce ( 1) implies t = -Lvn| and vn LVnl. The objective value of (P) is therefore 1-1 2- leading to |0||| VLv + (Vī- - Lvā]2 Since -Āー
integer and - Ex
have (vn- [íー)レvカ) )² < /カ- /nl Therefore, [v //
[V Lvn] Vn. 1/4
Taking square roots gives |vn +
<
(iv) With steps (ii,, we have shown that, for every z E R with max J S 1, have ||æ|||2 < n//4 For arbitrary x * 0 (assuming this is w.Lo.g. since, for 0, the
17

---

congruence trying prove is trivially satisfied), let y max(]|=]|=<;, va 11) 11) Clearly,
max(llyllo>
+ 1. Thus, y S and, thus, |lvl2 S nt. Therefore
1 | I maxf1121loo vn | n².
| max vn
It follows that
n | I max
vn [kll)
which concludes the proof.
Corollary 2. Combining Lemma 4 with Theorem 7 the multi-norm relaxation k-HC (-H((mult.1)
(mutii.) satisfies
1
OPT(K-HC(2.)) s (PC (mulri.)) (P.( vn
Proof. direct consequence of applying Theorem to the congruence relationship derived in Lemma 4
Proposition Under Assumption when solving (2,1 a nonzero lower bound is obtained only after generating at least 2 branching nodes.
Proof. By assumption, each branching operation decides the sign component of wy for some j [k] by splitting (with half-space constraint) its feasible region with a hyperplane containing the origin. As long as the cone, call C. obtained by intersecting such half-spaces is not pointed, the convex hull of its intersection with the feasible region of the problem contains the origin. Thus, the solution with (wy, ?iy) = O and ziy = 1, E [m), which coincides with assigning every data point to the degenerate hyperplane of index (thus achieving d: 0, [m]), is optimal regardless of the convex envelope that is employed. Only after branching has been carried out on each component of wy whose sign is not already restricted by the commettr--beeaknng constraint (i.e., all coordinates ex- cept w ) for each j E [k]. the cone C' becomes pointed and, thus, the convex hull of its intersection with the feasible region of the problem renders the trivial solution (wy, 72) = 0. E [kt], infeasible, nonzero lower bound. This requires generating at least (* nodes by branching each hyperplane
allowing for the calculation
times (rather than n due to the symmetry breaking constraint being already imposed). Notice that, in the general case, more branching operations are needed due to the variables being binary.
Proposition 3. Assume that the constraint ||m 2 1, E [k], is imposed and that branching takes place on the 8ih. variables first. Then, nonzero global lower bound obtained after generating at least 1k(=-1) nodes. If (os.)( is being solved, no further branching on w takes place.
Proof. Let's consider a hyperplane index j E [k]. Let 85Λ = for all h E [n], which implies Wihh Σ 2 and Wijh S }- Letting wfh "ith = 2. we have with + Wigh 1. This feasible solution
1
trivially satisfies the 1-norm constraint equation with wit - Win Wihh 0. Thus, (wj, 75) 0.
j E [k)] is optimal. By branching on variable 8jh, we impose either wyh S (with 8yh = 0) or Wihh 2 0 (with 8ih- 1). In both cases, the solution where w w ja and With becomes infeasible due to either with With being forced to 0; the solution with Wish 0, though, for any other h' [n]] \ (h), remains feasible as long branching on it has not taken place. Thus, nonzero lower bound is obtained after 2k(n-1) branching nodes have been generated. If k-HC( is being solved, when such an exponentially-lang tree of depth k(n 1) is complete, though, ||w,l] 2 1, j E [k), holds in each leaf node and, thus, no further branching on w necessary.
Proposition 4. Assume that ||w 2 J. E [kk], imposed and that branching takes place the ush variables first. Then, k(n-1) nodes suffice to obtain a nonzero lower bound. If k-HC (1) is being solved, no further branching takes place.
18

---

Proof. After branching on üjh for any pair j. h, the (left, w.l.o.g.) child node with Uyh satisfies wyh 2 - This guarantees ||wy|le Tn and, thus, no further branching is needed on wy in the descendants of the left node. Further branching operations on w, are only necessary on the right child node where Uih = 0 has been imposed. By iteratively applying this reasoning - times (recall that no disjunction is imposed on Wi, due to symmetry breaking) for each j E [k]. we obtain tree with exactly two nodes per level (except for the root node) where each left node satisfies the ||wy]]e |ما 2 v constraint for least a j E [k.] Therefore, when the tree has depth k(n 1), ||wll J is satisfied for all j E [k). When such polynomially-sized tree of depth k(n 1) is complete, ||xcy bc J E [k:]. holds in each leaf node and, thus, if kheT wol 1. is being solved, no further branching on w is necessary.
Vn
D PROOF OF THE APPROXIMATION FACTORS AND OF THEIR TIGHTNESS
We will rely on the following Lemma:
Lemma 5. Given two functions f.g R Rh with g surjective we have:
max [xx max max
[(x)
:g(x)) =
(12)
#E
((x) WER
ZER"
If. for all x E IR"
= f((=) and g(x) = g(xx)), then:
fxx
f(x) g((z) = =m}}
max
max
max
(13)
HER g(x)
MER
ZERR
Proof. If g is surjective, then UveR E R" g(x) = =R. We can therefore partition R" into
infinitely many subsets of type {x E R² g(x) = v}. An optimal solution to max
f(x)
thus
g(a)
corresponds to the best solution over such subsets. The special case in equation 13 follows by similar argument.
Proposition 5. The following relationships are satisfied for every a E R": ||ll| I || S /n||=112
vn ||ا|| S ||0:|100 S ||0||2
and the factors vn and 1 vn are tight.
Proof. We are looking for four positive coefficients 0n, B1, (roo, Pro that satisfy the following rela- tionships for all E R"
a1||=|12 I ||>|| I |111=1112
ax Go<|2|112 I || - 9o0 || 12-
Assuming x * 0 as, for x = 0, a||=||, - ||ا|| s B||æ||, holds for all a, 3 and for all p. q E
No {oo), the tightest values for 0n, B1, 0loon 9rx must satisfy the following relationships:
|
81
max
Boc max =ER"
=E3*
2
|
|
x |mc
01
min =ER"
|z||
0.o
min ZER
|
As it is not hard to see, max the following four problems:
|=>|| ||>|
min
|alls holds for all p,q NU [co}. Thus, we need to solve
|
31 max
3x0 max
20
x 2
| ||2
||||| ||c||2
01
x
|0||00
19

---

lizlaa
Let us consider the of a1, azos for which are solving max
for q 10,0, By virtue of ||
Lemma 5 we are thus solving:
f|lz112 || v1) P rER
a4
max VER+
max
As the maximum of a convex function (such as [|=l2)) over a closed, convex set is achieved on the border of the latter and, if w.l.o.g. relax |اح| = into ||>|| V.
optimizing
polytope, over its extreme vertices, can
For ai, the extreme points of {a R" ||>||| S o are of the form: ver for all [n]] with ee being the f-th canonical vector of TR.. For each them, we have ||eelll vv2 v. Thus,
| |ا|| 1.
Q1 max
For Ozac the extreme points of for R" || I 2 are of the form: (tv,... , Hv) for all possible choices of =. For each of them, we have [I tv) V22n vn. Thus, || 2 " nn. -
0x max
for q co. By |E|| Let us consider the case of 31 and 8xx. for which solving max |
virtue of Lemma
5 we are thus solving:
max {11=)l ||2l|2 v1}
Bg
max VER_
v ZER7
For 31, the problem reads:
B1 max v20
max
{e (e"x:xTx- v²}
(14)
v ZER
The KKT conditions for the relaxation of the inner problem of equation 14 obtained after dropping the nonnegativity on read:
Vz(e" Mx=x=~²)) 00
x² xxx= v2.
with À unrestricted in sign. From the first equation, we deduce _ec second equation, we obtain アスズ = 2² that is, X = // is nonnegative, it is an optimal solution to both the relaxation of the inner problem of equation 14 with æ RR" and unrelaxed version with x E Ry. We thus have ||a||| = # |lellz v = uyn.
2X- By substituting it in the 2v Thus, we have x -. Since the latter
en
We conclude that 31 Pyn
Vn.
For Boo, the problem reads:
x : n2 }}
3:0
max #20
max ZER
max [x)] [E(n)
v
The optimal solutions to the inner problem are of the form veg, where eg is canonical vector of R", for which we have ||vee||oc We conclude that 8xx v
[
20


Reviews:
[{"review_id": "isTqlFO6oH", "reviewer": "Reviewer_oow2", "summary": "This paper introduces a method to solve the k-Hyperplane Clustering problem in the 2-norm ($k-HC_2$) to global optimality using spatial branch-and-bound (SBB). The approach strengthens the classical mixed-integer quadratically constrained quadratic programming (MI-QCQP) formulation by incorporating constraints from polyhedral norm variants $(p = 1, \\infty)$. The authors show that including ∞-norm constraints allows the SBB method to obtain a nonzero lower bound in O(nk) nodes, compared to $\\Omega(2^{k(n−1)})$ nodes for the baseline. Experiments on synthetic datasets report speedups of 8–41 times, improving the number of instances solved to global optimality.", "questions": "1. How does the method scale with the number of data points m, given that the assignment problem may become the bottleneck?\n2. Can the authors provide wall-clock time profiles and total node counts (not just medians) to better characterize tree size and convergence?\n3. How robust are the speedups under solver-default branching rules and parameters?\n4. Why does the multi-norm formulation perform worse than the individual $\\infty$-norm formulation in some cases?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. Theoretical analysis proves that adding polyhedral norm constraints reduces the number of SBB nodes required to obtain a nonzero lower bound from exponential to polynomial.\n2. The method is evaluated on two synthetic testbeds (Low-dim and High-dim) with statistical tests (Wilcoxon signed-rank) confirming significant speedups.\n3. Clear MI-QCQP and MILP formulations are provided for the polyhedral norm constraints.\n4. The multi-norm relaxation framework is general and may be applied to other problems with nonconvex norm constraints.", "weaknesses": "1. Experiments are limited to small-scale instances (up to m = 30, n = 5, k = 5) and use synthetically generated data with a specific noise model.\n2. The theoretical advantage of $\\infty$-norm constraints assumes branching occurs first on the binary variables of the polyhedral norm formulation; performance under default branching strategies is not tested.\n3. The analysis focuses only on the number of nodes to the first nonzero bound, not the total tree size or gap closure.\n4. No comparison with specialized heuristics or state-of-the-art approximate methods is provided.\n5. Validation is limited to synthetic data; real-world applicability is not assessed.\n6. The method requires solving complex MI-QCQPs, which may not scale to very large instances.\n7. There is also no analysis of the trade-off between solution quality and computation time for practical use.\n8. The paper does not provide guidance on selecting which polyhedral norm constraints to include for best performance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MWdT55CukS", "reviewer": "Reviewer_mEub", "summary": "The authors give a spatial branch-and-bound (SBB) method to solve the k-hyperplane clustering problem (k-HC2), which minimizes the sum of squared Euclidean distances from points to their nearest hyperplane. By updating the MI-QCQP formulation with constraints from alternative p-norms (especially polyhedral norms like p = 1, $\\infty$), they show that these additions improve SBB efficiency, reducing the number of nodes needed for nonzero lower bounds from exponential to linear under mild assumptions. Empirical results confirm speedups on the two listed datasets.", "questions": "1. How does the proposed method compare to existing subspace clustering approaches [2-3] in terms of formulation and performance?\n\n2. What is the time complexity of the proposed algorithm, and how does it scale with data size?\n\n3. What are the practical applications of the k-HC² algorithm, and in which domains does it offer clear advantages?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The k-Hyperplane Clustering problem (k-HC2) is a fundamental problem in classical machine learning. Addressing the k-HC2 problem using the a MI-QCQP formulation with constraints would be of interest to the community, particularly in the context of subspace clustering.\n\n2. The main contribution of this work lies in using a multi-norm approach to estimate the lower bound for the objective value of k-HC_{2,1}, as compared to using a single polyhedral norm. In this way, the authors enable earlier pruning in the SBB procedure. Furthermore, under specific assumptions (as shown in Proposition 4), the authors provide theoretical guarantees for the use of two scaled polyhedral-norm constraints in the k-HC(2,1) formulation.\n\n3. The proposed algorithm shows empirical speedups on datasets.", "weaknesses": "1. The paper does not discuss prior research in subspace clustering, which also aims to identify k subspaces that minimize the sum of squared Euclidean distances between each data point and its closest subspace [1][2][3]. \n\n2. The idea of using polyhedral norms and the SBB methods for k-HC2 problem has already been explored in several prior works (e.g., Dhyani and Liberti (2008), Amaldi & Coniglio (2013)). While this paper introduces a modification by incorporating multiple norm constraints($\\ell_1$-norm and $\\ell_{\\infty}$-norm) for approximation purposes, the contribution may be viewed as incremental.\n\n3. The problem remains computationally challenging for large-scale instances, and the paper does not clearly specify the time complexity of the proposed algorithm.\n\nReference:\n\n[1]. Rademacher L, Vempala S, Wang G. Matrix approximation and projective clustering via iterative sampling[C]. Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, 2006, Pages 1117 - 1126.\n\n[2]. Sohler, Christian, and David P. Woodruff. Strong coresets for k-median and subspace approximation: Goodbye dimension. 2018 IEEE 59th Annual Symposium on Foundations of Computer Science. IEEE, 2018.\n \n[3]. Eiben, Eduard, et al. EPTAS for k-means clustering of affine subspaces. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4U0GNJQy6U", "reviewer": "Reviewer_RjaT", "summary": "This paper focuses on improving spatial branch-and-bound (SBB) algorithms for optimally solving the 2-norm k-hyperplane clustering $k$-$HC_2$ problem, which seeks to choose k hyperplanes in a way that minimize the squared norm distance between each point and its nearest hyperplane.\n\nThe paper first considers a generalized objective $k$-$HC_{(p,c)}$ that considers the $p$-norm and a scaling constant $c$ in the constraints, and proves that optimal solution for  $k$-$HC_{(q,c')}$ for a careful choice of $c$ provides an optimal solution for $k$-$HC_{(p,c)}$. These bounds can be used specifically for the purpose of finding problems that approximate $k$-$HC_{(2,2)}$ = $k$-$HC_{2}$. The paper then focuses especially on approximations that are obtained for $k$-$HC_{2}$ in terms of $k$-$HC_{(\\infty,1)}$ and $k$-$HC_{(1,1/\\sqrt{n})}$. They then show how this leads to a strengthened formulation for  $k$-$HC_{2}$, which has a faster solution using SBB techniques. In particular, Section 4 proves that only a linear number of nodes in the branch-and-bound is needed to get a non-zero global lower bound for the new formulation, whereas an exponential number of nodes are needed to get a non-zero global lower bound for a basic formulation.\n\nThe paper shows in numerical experiments that the new approach leads to faster solve times in practice.", "questions": "Can you clarify the meaning of Lemma 2 and it's purpose?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The topic of the paper is interesting and well-motivated from previous research.\n\nThe mathematical contributions of the paper is non-trivial; the technical contribution of the paper is quite high. \n\nEven though the paper is proving a large number of non-trivial technical results, the presentation is very good and explains the main ideas and components (and how they fit together) very well. The approach makes sense at a high level, and the paper does a good job presenting enough technical detail in the main text while knowing what to push to the appendix.\n\nThe technical approach leads to concrete improvements in numerical experiments.", "weaknesses": "There were a couple places where the technical details were a little unclear and could have been explained a bit better:\n\nLemma 2 seems written somewhat informally and I do not follow what it is saying. In particular, it states that imposing a certain inequality \"coincides with accounting for each point to hyperplane distance as ...\". I don't understand precise meaning of the wording \"coincides with accounting for\", and hence I do not follow the meaning or significance of this lemma.\n\nIt's also not that clear how Lemma 2 is used in the main results. It's clear how Lemma 3 and Theorem 2 together produce the useful bound in corollary 2, but what role does Lemma 2 play in all this? \n\nFigures 1 and 2 could use a bit more explanation, e.g., in the caption. At first something seemed backwards, because the text explained how the feasible region of a (q,c) problem with $q = 1, \\infty$ and $c = 1, 1/\\sqrt{n}$ contains the feasible region for $p = 2, c = 1$, but this appeared opposite to the pictures where a circle contained a red diamond and green square. It did not take me long to realize that this is because the feasible region is everything that lies *outside* these colored shapes, but it would have made things a lot clearer a lot quicker to note this explicitly, rather than just stating these are illustrations of certain feasible regions. Also, in the captions, shouldn't you write 2 instead of n in $\\mathbb{R}^n$?\n\nThis is minor, but there are also some typos to fix:\n\n* lemma 1: coincide Also ---> add missing period\n* line 072: \"d_p intrinsically\" --> missing the word \"is\"?\n* line 055: \"nonzero global lower bounds is\" --> bound is or bounds are", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)