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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.