Classifiers in High Dimensional Hilbert Metrics

In the Euclidean metric, SVMs are typically solved by formulating them as convex optimization problems, specifically quadratic programming, which efficiently maximizes the margin between classes [3, 7]. This formulation frequently exploits Lagrangian duality, allowing the problem to be expressed purely in terms of inner products, which can then be elegantly generalized via the kernel trick [19]. However, generalizing this dual formulation to non-Euclidean spaces, such as hyperbolic or Hilbert geometries, is highly non-trivial. Substituting the Euclidean inner product or distance with a non-Euclidean metric generally destroys the positive semi-definiteness of the kernel or the convexity of the objective function. Consequently, the standard trick of solving the dual problem yields a nonconvex optimization problem when applied naively to these geometries.

Because of this inherent non-convexity, previous attempts to formulate SVMs and linear classifiers in hyperbolic spaces have faced significant computational hurdles. Cho et al. [9] were among the first to consider large-margin classification in hyperbolic space. While they demonstrated that their approach significantly outperforms Euclidean classifiers on hierarchical benchmarks by respecting the data’s intrinsic geometry, their method directly optimized a non-convex margin objective using Riemannian gradient descent. Without careful initialization, such approaches are highly susceptible to local minima and provide neither a guarantee of a global optimum nor a worst-case polynomial running time. Other continuous optimization techniques for representation learning in hyperbolic spaces similarly rely on iterative local methods lacking rigorous theoretical convergence guarantees [15, 35]. Furthermore, as highlighted by Mishne et al. [30], training hyperbolic learning models via Riemannian optimization frequently suffers from severe numerical instability and convergence issues, leading to catastrophic floating-point failures. By formulating our Hilbert SVM as a series of exact LPs, our approach completely obviates these Riemannian convergence and numerical stability bottlenecks.

Another potential avenue for solving SVMs in the Hilbert metric is to exploit isometric embeddings. Extending results of de la Harpe [12], Vernicos [42] presented an elegant isometry mapping the polytopal Hilbert geometry into a finite-dimensional normed vector space. While one might be tempted to map the input points into this embedding space to solve a standard SVM, this approach is fundamentally flawed for linear classification. Because the mapping is highly non-linear, a simple linear classifier (a hyperplane) computed in the embedding space does not translate back to a linear hyperplane in the original input space. Furthermore, computing the complex intersection of the resulting decision boundary with the polytope’s feasible image is analytically and computationally impractical.

Recently, Acharya et al. [1] addressed the exact polytopal SVM problem in the Hilbert metric without relying on non-convex optimization or non-linear embeddings. They showed that the Hilbert SVM could be modeled precisely as an LP-type problem. While their algorithmic framework achieves a running time linear in the number of training points, its complexity grows polynomially with the total number of vertices of the polytope defining the metric balls. Unfortunately, the vertex complexity of a polytope defined by $m$ facets generally grows exponentially with the dimension $d$. As such, their method suffers from the curse of dimensionality and remains unsuitable for high-dimensional spaces, where the vast majority of machine learning applications lie.

In this paper, we explore an alternative algebraic viewpoint of Hilbert geometry to develop an efficient, globally approximate algorithm for the Hilbert SVM problem. The defining feature of our approach is that the running time scales only polynomially with the dimension of the space, successfully circumventing the exponential bottleneck that plagues prior vertex-based methods while avoiding the local-minima pitfalls of Riemannian optimization.

Rather than relying on non-convex gradient descent or explicit vertex enumeration, our algorithm leverages Birkhoff’s formulation of the Hilbert metric to reduce the maximum-margin problem to a sequence of linear programming (LP) feasibility tests. Because we rely on numerical LP solvers, we assume the input coordinates and bounding hyperplane coefficients are represented as bounded $B$-bit rational numbers, and we compute the maximum margin to within a user-supplied additive approximation error $\epsilon$.

The following theorem formalizes our main result:

This polynomial dependence on the ambient dimension $d$ is a crucial advancement for modern machine learning applications. Furthermore, our framework is highly extensible:

Asymmetric Metrics:

We generalize our LP-feasibility results to the closely related asymmetric Funk geometry, which is useful for directed spaces and specific optimal transport problems (Section 2.1).

Soft-Margin Classification:

To handle real-world datasets that contain noise or are not perfectly linearly separable, we provide a robust soft-margin formulation for the Hilbert SVM that scales penalties based on boundary proximity (Section 4.1).

Nearest-Neighbor Classifiers:

While isometric embeddings fail for hyperplane SVMs, we leverage Vernicos’s mapping to design an efficient approximate nearest-neighbor-based classifier for non-linear decision boundaries (Section 4.2).

In this section, we introduce the Funk and Hilbert distances. Given a convex body $\mathrm{\Omega }$ and any two points $p,q\in \mathrm{int}(\mathrm{\Omega })$, let $p^{\prime }$ and $q^{\prime }$ denote the endpoints of the chord $\overline{pq}$ ordered as $⟨p^{\prime },p,q,q^{\prime }⟩$ (see Figure 1). If $p=q$ all the distances are defined to be zero. Otherwise, the Funk and Hilbert distances are defined as:

Intuitively, $d_{\mathrm{\Omega }}^F(p,q)$ is a measure of how far $q$ is from $p$ relative to the boundary that lies beyond $q$, and $d_{\mathrm{\Omega }}^{rF}(p,q)$ is just the reverse of this. The Hilbert distance $d_{\mathrm{\Omega }}^H(p,q)$ symmetrizes these by taking their arithmetic mean.

These distance functions are all nonnegative and satisfy the triangle inequality [34]. The Hilbert distance defines a metric over $\mathrm{int}(\mathrm{\Omega })$. The Funk and reverse Funk are asymmetric and hence define weak metrics over $\mathrm{int}(\mathrm{\Omega })$. Observe that as either point approaches the boundary of $\mathrm{\Omega }$, the Hilbert distance approaches $\mathrm{\infty }$. The Hilbert distance is invariant under invertible projective transformations.

Birkhoff [4] provided an alternative, equivalent definition of these metrics that is better suited to our approach.

This follows from the fact that $\mathrm{\Omega }$ is convex, and observing that if $\overrightarrow{pq}$ intersects $\partial \mathrm{\Omega }$ in $q^{\prime }$, on the bounding hyperplane $L_k$, then by similar triangles

Intuitively, this provides a way to define the metrics without explicitly calculating where the line $\overleftrightarrow{pq}$ intersects $\partial \mathrm{\Omega }$. One consequence of the proposition is that the metrics can be reduced to a sup norm over ${ℝ}^t$ for some finite dimension $t$, using a non-linear mapping function [28]. Another useful consequence is its application to constructing metric balls in high dimensions.

Letting $d_{\mathrm{\Omega }}^{\ast }$ denote any of the above metrics and given a point $p\in \mathrm{int}(\mathrm{\Omega })$ and scalar $r\ge 0$, the associated metric balls are defined in the standard way.

It is well known that the Funk ball about a point $p$ is a scaling of $\mathrm{\Omega }$ about $p$ by an appropriate factor that depends on the radius. This can be derived directly from Proposition 2:

Fixing $p$ and $r$, let $c_i^{\ast }:=c_i-e^{-r}({𝐰}_i^{\top }𝐩+c_i)$, and let $S_i^F$ be the hyperplane represented by $({𝐰}_i,c_i^{\ast })$ (See Figure 2(a)). Observe that $S_i^F$ is parallel to $L_i$. We have the following:

A similar result can be proved for reverse-Funk balls (see Figure 2(b)). We next use Proposition 2 to demonstrate the Hilbert balls are convex polytopes, but the number of bounding facets is larger by the square. Following the same reasoning as in Eq. (4), we have

Fixing $p$ and $r$, let ${\alpha }_{j,k}:=e^{2r}\left({𝐰}_k^{\top }𝐩+c_k\right)$ and ${\alpha }_{j,k}^{\prime }:=\left({𝐰}_j^{\top }𝐩+c_j\right)$. We have

Let ${𝐰}_{j,k}^{\ast }=\left({\alpha }_{j,k}{𝐰}_j-{\alpha }_{j,k}^{\prime }{𝐰}_k\right)$, and $c_{j,k}^{\ast }=\left({\alpha }_{j,k}{c}_j-{\alpha }_{j,k}^{\prime }{c}_k\right)$. Let $S_{j,k}^H$ be the hyperplane represented by $({𝐰}_{j,k}^{\ast },c_{j,k}^{\ast })$. Observe that $S_{j,k}^H$ is a linear combination of $L_j$, and $L_k$, and therefore $S_{j,k}^H$ passes through the intersection of $L_j$ and $L_k$ (see Figure 2(c)). In summary, we have the following:

We assume every input parameter is given to us as a rational number, expressed as a fraction of two nonzero $B$-bit integers. We call this representation a $B$-bit rational number. Each of the $n$ points $p\in P^{\pm }$ is represented as a $d$-vector $𝐩$ whose coordinates are $B$-bit rational numbers. The domain $\mathrm{\Omega }$ is defined by a set $ℒ$ of $m$ hyperplanes, each of whose $(𝐰,c)$ representation is given as a sequence of $d+1$ $B$-bit rational numbers. We say that the resulting SVM problem instance has size parameters $(d,n,m,B)$. The total bit complexity of such an instance is $O(d(n+m)B)$.

Before describing the overall algorithm, we first establish an upper bound on $\gamma$, the maximum margin in terms of the bit size of the input. Let $K$ be the corresponding separating hyperplane for which $\gamma$ is achieved. Observe that for an arbitrary $p_{+}\in P^{+}$, and $p_{-}\in P^{-}$, we have $d_{\mathrm{\Omega }}^H(p_{-},p_{+})\ge d_{\mathrm{\Omega }}^H(p_{-},K)+d_{\mathrm{\Omega }}^H(p_{+},K)\ge 2\gamma$. Now let the line joining $p_{-}$ and $p_{+}$ intersect $\partial \mathrm{\Omega }$ in bounding hyperplanes $L_{-}:({𝐰}_{-},c_{-})$, and $L_{+}:({𝐰}_{+},c_{+})$. Therefore,

Consider any one of the terms in the numerator, say, $({𝐰}_{-}^{\top }{𝐩}_{+}+c_{-})$. Now, ${𝐰}_{-}$, and $p_{+}$ are given by $d$ $B$-bit rational numbers, therefore their inner product can have an absolute value of at most $d\cdot 2^{2B}$. Hence, the entire term ${𝐰}_{-}^{\top }{𝐩}_{+}+c_{-}$ has an absolute value at most $d\cdot 2^{2B}+2^B$. Recalling that the Hilbert distance is the logarithm of ratios, up to constant factors, $d_{\mathrm{\Omega }}^H(p_{-},p_{+})$ is at most $(8B+4\log d)\log 2=O(B+\log d)$, implying that $\gamma \le M$ for some $M\in O(B+\log d)$. Thus, we have:

Our overall algorithm is as follows. Since we are interested in the optimum margin up to an accuracy of $\epsilon$, we check if $P^{+}$ and $P^{-}$ are separable with a margin of at least $r$, where $r$ is an element from the range: $\mathrm{\Gamma }=[\epsilon ,2\epsilon ,3\epsilon ,\mathrm{\dots },M]$, where $M=M(d,n,m,B)$. To check separation for a particular value $r$, we will conduct an (approximate) LP-based feasibility test. We employ this test as part of a parametric binary search over the range $\mathrm{\Gamma }$. This implies that we only need to solve $O(\log B+\log \log d+\log (1/\epsilon ))$ many feasibility tests. We next describe this LP-based subroutine.

We consider the problem of determining whether it is possible to achieve a given margin $\gamma$, up to an additive error of $\epsilon$. For a particular margin $r$, recall that $B_{\mathrm{\Omega }}^H(p,r)$ is the Hilbert ball of radius $r$ centered at $p$. By Lemma 4, $B_{\mathrm{\Omega }}^H(p,r)$ is a polytope bounded by $m(m-1)$ hyperplanes. (In Section 3.3, we will show how to construct them efficiently.) Let $ℬ{(r)}^{+}=\{B_{\mathrm{\Omega }}^H(p^{+},r)\mid p^{+}\in P^{+}\}$, the collection of the Hilbert balls of radius $r$ around the positively labeled points, and define $ℬ{(r)}^{-}$ analogously for $P^{-}$.

The feasibility of $\gamma$ reduces to determining whether the collections of balls $ℬ{(r)}^{+}$ and $ℬ{(r)}^{-}$ are linearly separable. For $i\in [n]$, let $𝐀(r,i)$ be an $m(m-1)\times d$ matrix and let $𝐛(r,i)$ be an $m(m-1)\times 1$ vector such that

We can construct $𝐀(r,i)$ and $𝐛(r,i)$ from the hyperplanes $S_{j,k}^H:({𝐰}_{j,k}^{\ast },c_{j,k}^{\ast })$ described in Lemma 4. In particular, for $t\in [m(m-1)]$, if $({𝐰}_t^{\ast },c_t^{\ast })$ denotes the $t$-th bounding hyperplane of $B_{\mathrm{\Omega }}^H(p_i,r)$, then ${𝐰}_t^{\ast }$ is the $t$-th row of $𝐀(r,i)$ and $c_t^{\ast }$ is the $t$-th element of $𝐛(r,i)$.

Therefore, finding whether $ℬ{(r)}^{+}$ and $ℬ{(r)}^{-}$ are linearly separable is equivalent to the following decision problem:

For fixed $r$ and $i$, let $𝐀=𝐀(r,i)$ and $𝐛=𝐛(r,i)$. Eq. (8) can be rewritten as:

By standard LP duality (see, e.g., [16, pp. 81–84]), we have

Therefore we can simplify Eq. (8) as follows:

Analogously, Eq. (9) can be simplified to

Hence, to determine whether the collections $ℬ{(r)}^{+}$ and $ℬ{(r)}^{-}$ are linearly separable we solve the following LP-feasibility problem in the parameters ${𝐰}_{d\times 1}$, $c$, and $𝐲{(i)}_{m(m-1)\times 1}$, for $i\in [n]$.

We add the final constraint to avoid the trivial solution in which all the parameters are zero.

A hyperplane $L$ that is tangent to a polytope $\mathrm{\Omega }$, with bounding hyperplanes $L_1,\mathrm{\dots },L_m$, can be written as a positive linear combination (often referred to as the conical combination) of the bounding hyperplanes.

The vector $𝐲(i)$ in Opt. (10) corresponds to the factors for this conical combination. The third constraint in Opt. (10) guarantees a hyperplane $K_B$ parallel to $K$, along with being a conical combination of the supporting hyperplanes for each $B\in ℬ{(r)}^{+}\cup ℬ{(r)}^{-}$. The first two constraints ensure $K_B$ is above or below $K$, depending on whether $B\in ℬ{(r)}^{+}$ or $ℬ{(r)}^{-}$.

In this section, we present a procedure for constructing the bounding hyperplanes for a Hilbert ball, $B_{\mathrm{\Omega }}^H(p_i,r)$. Recall that $ℒ={\{L_i\}}_{i=1}^m$ denotes the set of hyperplanes bounding $\mathrm{\Omega }$. First, we take two bounding hyperplanes of $\mathrm{\Omega }$: $L_j:({𝐰}_j,c_j)$ and $L_k:({𝐰}_k,c_k)$, $j\ne k$, $j,k\in [m]$. For $p_i\in P^{\pm }$, we find $S{(i,r)}_{j,k}:(𝐮{(i,r)}_{(j,k)},t{(i,r)}_{j,k})$, the hyperplane at a Hilbert-distance of $r$ from $p_i$ with respect to the boundary defined by $L_j$ and $L_k$, such that there exists a line $\mathrm{\ell }$ that intersects $L_j$, $S{(i,r)}_{j,k}$, $p_i$, and $L_k$ in that order (see Figure 4).

It is clear that $\exists \alpha :0\le \alpha \le 1$, such that

For any point $s$ on $S{(i,r)}_{j,k}$, $s\in L_j^{+}\cap L_k^{+}$, it is easy to see that

Solving for $\alpha$ using the following:

For $p_i\in \mathrm{int}(\mathrm{\Omega })$, $r$ is finite and positive: . Therefore, Eq. (12) can be equivalently written as a linear equation in $\alpha$. Since for $j,k\in [m]$, $j\ne k$, $i\in [n]$, $S{(i,r)}_{j,k}$ is a bounding hyperplane for $B_{\mathrm{\Omega }}^H(p_i,r)$, we can use Eqs. (11), and (12) to construct $B_{\mathrm{\Omega }}^H(p_i,r)$, for all $p_i\in P^{\pm }$ in $O(nd{m}^2)$ time.

Recall that to obtain $\gamma$ within an additive error of $\epsilon$, we solve $O(\log B+\log \log d+\log (1/\epsilon ))$ LPs of the form Opt. (10). We can use any standard interior-point method, such as Khachiyan’s Ellipsoid method [25] or Karmarkar’s method [23] to solve Opt. (10) in time that is polynomial in the number of variables, number of inequalities, and bit-length of each variable. We first establish the bit-length required to encode a parameter in our LP-feasibility problem (Opt. (10)).

Recall that we are searching for $r$ over the range $\mathrm{\Gamma }=[\epsilon ,2\epsilon ,\mathrm{\dots },M]$, with $M=M(d,n,m,B)=O(B+\log d)$. Therefore, the quantity $e^{2r}$ can take on values in the range ${\mathrm{\Gamma }}_e=[e^{2\epsilon },e^{4\epsilon },\mathrm{\dots },e^{2M}]$. Instead of fixing $r$’s value exactly over $\mathrm{\Gamma }$, it is sufficient for our purposes if we search for $r$ over $[r_1,r_2,\mathrm{\dots },r_{M/\epsilon }]$, where .

The minimum difference between two elements in ${\mathrm{\Gamma }}_e$ is at least $e^{4\epsilon }-e^{2\epsilon }>\epsilon$. (This can be verified using Taylor’s series for $e^x$, at $x=0$.) Therefore, to represent ${\mathrm{\Gamma }}_e$, it is sufficient for our purposes to find a bit-representation which allows for a maximum value $e^{2M}$ up to a resolution of $\epsilon$. This can be done by using $O(M)$ bits for the integer part, and $O(\log (1/\epsilon ))$ bits for the fractional part. Hence, it is sufficient to represent the elements of ${\mathrm{\Gamma }}_e$ as $O(M+\log (1/\epsilon ))=O(B+\log d+\log (1/\epsilon ))$-bit rational numbers.

Using Eq. (12), we solve for and represent $\alpha$, using $O(B+\log d+\log (1/\epsilon ))$-bit rational numbers. Therefore, using Eq. (11) every parameter of $S{(i,r)}_{j,k}$, which acts as a bounding hyperplane for $B_{\mathrm{\Omega }}^H(p_i,r)$, can also be represented using $O(B+\log d+\log (1/\epsilon ))$-bit rational numbers.

Now, the number of variables in Opt. (10) is $O((n+d)m^2)$, with the number of inequalities being $O(n(m^2+d))$. Hence, we can determine if Opt. (10) is feasible in $O(\text{poly}(n,m,d)(B+\log d+\log (1/\epsilon ))$ time, for a fixed $r$. And since we solve $O(\log B+\log \log d+\log (1/\epsilon ))$ such LPs, our overall running time is $O(\text{poly}(n,m,d,B,\log (1/\epsilon ))$. This proves our main result in Theorem 1. Recall that the input bit-length is $d(n+m)B$, implying the overall running time is also polynomial in the input bit-length and the log of the desired accuracy.

Up to this point, we assumed $P^{+}$ and $P^{-}$ are linearly separable. If they are not, a common approach is to use a hyperplane classifier with appropriate penalties for misclassifying points in the training set. In this section, we propose a formulation for such a “soft” classifier.

We modify our LP-feasibility problem: Opt (10) to introduce penalties in the form of slack variables. Reiterating the observation from Remark 6, we note that the first two constraints of Opt (10) enforce the condition that, for $p\in P^{+}$, $B_{\mathrm{\Omega }}^H(p,r)$ is completely above the separator $K:(𝐰,c)$. Instead, we only require that $B_{\mathrm{\Omega }}^H(p,r)$ is above $K^{\prime }:(𝐰,c+\xi )$ for some positive $\xi$. Here $\xi$ works as a penalty for the improper separation of $B_{\mathrm{\Omega }}^H(p,r)$. We similarly set individual penalties for each point.

Next, we want the following desirable property: points that are closer to the boundary of $\mathrm{\Omega }$ should pay a heavier penalty for being misclassified. It is because for a fixed point $q$, $d_{\mathrm{\Omega }}^H(p_i,q)$ scales inversely with $p_i$’s distance to the boundary. Therefore, we scale the penalty associated with $p_i$ by ${\omega }_i$, defined as the inverse of its distance to the boundary:

Finally, we propose the following LP in the parameters $𝐰$, $c$, and ${\xi }_i$, $𝐲(i)$, for $i\in [n]$, to minimize the overall weighted penalty for a fixed Hilbert radius $r$:

Let the optimum value derived from Opt. (14) be ${\mathrm{\Xi }}_r$, and the corresponding separating hyperplane, $K_r=(𝐰,c)$. Recall that $r$ attains values over ${\mathrm{\Gamma }}_r=[r_1,r_2,\mathrm{\dots },r_{M/\epsilon }]$, where $r_i$’s are any values satisfying , and $M=O(B+\log d)$. To find an appropriate classifier $K^{\ast }$, we take

Note that $C$ is a user-defined constant, a weight associated with improper separation. A higher value would favor proper separation, while a lower value would favor a larger margin.

A slight drawback of this approach is that it no longer suffices to perform a binary search on the range ${\mathrm{\Gamma }}_r$. Rather, we need to perform a grid search, i.e. solve Opt. (14) for every value of $r\in {\mathrm{\Gamma }}_r$ in the worst case. This implies the overall running time for the soft-margin classifier is $O(\text{poly}(n,m,d,B,1/\epsilon ))$.

In this section, we consider an alternative approach to binary classification in the Hilbert geometry. Rather than using a separating hyperplane, we select two sites $q^{+}$ and $q^{-}$, and classify a point $p$ according to which of these two sites it is closer to. In the Euclidean setting, the bisector between two points is a hyperplane, and this is no different from SVM. However, in Hilbert, bisectors are generally not hyperplanes. (An analysis of the structure of Hilbert bisectors in the 2-dimensional case was presented in [17], where it was shown that they are piecewise conics.)

As before, we assume that Hilbert geometry is defined with respect to a polytope $\mathrm{\Omega }$ in ${ℝ}^d$ defined by $m$ bounding hyperplanes $ℒ={\{L_i\}}_{i=1}^m$. Extending results of de la Harpe [12], Vernicos presented an elegant isometry from the polytopal Hilbert geometry $(\mathrm{\Omega },d_{\mathrm{\Omega }}^H)$ to a finite-dimensional normed vector space [42]. In particular, he presented an isometric mapping $f_{\mathrm{\Omega }}:(\mathrm{\Omega },d_{\mathrm{\Omega }}^H)\to ({ℝ}^{m-1},||\cdot |{|}_{{\mathrm{\Sigma }}_{2m}})$, where $||\cdot |{|}_{{\mathrm{\Sigma }}_{2m}}$ is a norm defined by a regular polytope $\mathrm{\Sigma }$ bounded by $2m$ facets in ${ℝ}^{m-1}$. In other words, the embedding space is ${ℝ}^{m-1}$ with ${\mathrm{\Sigma }}_{2m}$ as the unit ball.

Although one might be tempted to solve the SVM problem in the embedding space, the result would be far from ideal. Since $f_{\mathrm{\Omega }}$ is nonlinear, a linear classifier $\widehat{K}$ in the embedding space would not translate to a simple classifier in the input space. Moreover, since $f_{\mathrm{\Omega }}$ is not a bijection it is not clear how complex the intersection of $\widehat{K}$ with the image of $\mathrm{\Omega }$, $f_{\mathrm{\Omega }}(\mathrm{\Omega })$, would be.

Instead, we propose a simple nearest neighbor-based classifier in the embedding space. Given $\mathrm{\Omega }$, let $q_i$, $Q^{+}$, and $Q^{-}$ denote the images of $p_i$, $P^{+}$, and $P^{-}$ under the embedding $f_{\mathrm{\Omega }}$. ($q_i$ for all $i\in [n]$ can be computed in $O(m^2)$ time by solving $m$ linear equations). We find two representative centers $c^{+}$, and $c^{-}$, for $Q^{+}$, and $Q^{-}$ respectively such that the following is maximized:

Stated differently, $\beta$ is the value such that any point $q$ is at least $\beta$ times away from its nearest neighbor in the opposite class, as from its representative. This implies that the points can be correctly classified using an approximate nearest-neighbor algorithm with approximation factor at most $\beta$.

This can be rewritten as an optimization problem over the variables ${𝐜}^{+}$, ${𝐜}^{-}$, and $1/\beta$

We note that ${\parallel {𝐪}^{+}-{𝐪}^{-}\parallel }_{\mathrm{\Sigma }}$ in the above optimization is a pre-determined constant. If we let $W=\{{𝐰}_1,{𝐰}_2,\mathrm{\dots },{𝐰}_{2m}\}$ denote the directions determining the norm polytope $\mathrm{\Sigma }$, then the condition that ${\parallel 𝐱\parallel }_{\mathrm{\Sigma }}\le t$ can be expressed as a set of linear inequalities: ${𝐰}_i^{\top }𝐱\le t$, for $i\in [2m]$. Therefore, Opt. (4.2) is an LP in $O(m)$ variables, and $O(nm)$ inequalities.