# Lifting of a polyhedron

The $$l_1$$-ball in $$\mathbb{R}^d$$ is $$\{x \in \mathbb{R}^d : \sum_{i=1}^{d} |x_i| \leq 1 \}$$.

This is a bounded polyhedron $$\mathcal{P}_1$$, specified by $$2^d$$ inequalities as

$$\{x \in \mathbb{R}^d : \left (\sum_{i=1}^{d} (-1)^{n_i}. x_i \right ) \leq 1$$, $$\forall n_i \in \{1,2\}, i=1,...,d \}$$.

Is it possible to find a matrix $$A \in \mathbb{R}^{d \times 2d}$$ and polyhedron $$\mathcal{P}_2$$ in $$\mathbb{R}^{2d}$$ specified by at most $$2d+1$$ inequalities such that $$\mathcal{P}_1 = \{ Ax : x \in \mathcal{P}_2 \}$$.

I think the trick lies in somehow capitalizing on the extra variables available in the higher dimension to reduce the number of inequalities.

• Can you make an educated guess as to what those additional variables could represent? – Michael Grant Sep 12 '19 at 3:57