Describe an orthoplex as a polyhedron [duplicate]

Check if $x \in \mathbb{R}^n$ satisfies $\|x\|_1\leq 1$ using linear methods only, that is, find $A \in \mathbb{R}^{m\times n}$, $b \in \mathbb{R}^m$ such that

$$Ax \leq b \Leftrightarrow x \in \overline{\mathbb{B}}_{(\mathbb{R}^n, \|\cdot\|_1)}$$

where $m$ is not exponentially dependent on $n$.

My straightforward solution, checking the sums $x_1+\dots+x_n$, $x=(x_1,\dots,x_n)$, with plus replaced by minus in all possible ways, against $b=(1,\dots,1)$, leads to $m=2^n$. Is there a way to do this in non-exponential time? Thanks in advance.

Solution 1:

As we discussed in the comments: it is not possible to express the $\ell_1$ norm ball without an exponential number of rows, unless you allow for additional variables.

The simplest approach is to introduce new variables $y_i$, $i=1,2,\dots, n$. Then you have: \begin{array}{ll} -x_i \leq y_i & i = 1,2,\dots,n \\ +x_i\leq y_i & i=1,2,\dots, n \\ \sum_i y_i \leq 1 \end{array} So with $n$ additional variables you can express this with $2n+1$ inequalities. However, try and convince yourself that this still produces the same result: \begin{array}{ll} -x_i \leq y_i & i = 1,2,\dots,n \\ +x_i\leq y_i & i=1,2,\dots, n \\ \sum_i y_i = 1 \end{array} All I have done is change the last inequality to an equation. If $\|x\|_1=1$, then this obviously holds, because the only valid values of $y$ are $y_i=|x_i|$. But it will work even if $\|x\|_1<1$; for instance, you can choose $y_i=|x_i|+\frac{1 - \|x\|_1}{n}$. Once you accept the validity of this system, then, you can eliminate one of the $y_i$ values: \begin{array}{ll} -x_i \leq y_i & i = 1,2,\dots,n-1 \\ +x_i\leq y_i & i=1,2,\dots, n-1 \\ -x_n\leq 1 - y_1 - y_2 - \dots - y_{n-1} \\ +x_n\leq 1 - y_1 -y_2 - \dots - y_{n-1} \end{array} So in fact, with $n-1$ additional variables we can express the norm ball with $2n$ inequalities.