# name for a polytope constructed from a system of linear equations?

To a system of inhomogeneous linear equations, one can associate a polytope, as follows. Let $A\in\mathbb{R}^{m\times n}$, $b\in\mathbb{R}^m$ and $V=\{x\mid Ax=b, \text{support of$x$minimal}\}\subset \mathbb{R}^n$, where by the support of a vector I mean the index set of nonzero entries. Assume $V$ finite (this is not always the case, but happens often enough). Now the polytope $P(A,b)$ in question is the convex closure of $V$.

How does one call $P(A,b)$? Were such things studied anywhere?

Edit: a way to deal with it might be to blow up the dimension and work instead with $Y:=\{y\geq 0 \mid (A; -A)y=b\}\subset\mathbb{R}^{2n}$. Then $Y=S+C$, with $S$ a polytope and $C$ the recession cone of $Y$; the vertices of $S$ are naturally split into pairs $(x_+,x_-)$, with $x_+,x_-\in\mathbb{R}^n$, and $x_+$ and $x_-$ having disjoint support (provided $b\neq 0$). Thus $A(x_+-x_-)=b$, and it looks as if it should hold that each $x\in V$ gives rise to a vertex $(x_+,x_-)$ of $S$, by splitting $x$ into positive and negative parts.

-
add comment

## 1 Answer

Maybe a term you are looking for is "sparse solutions of underdetermined linear systems". At least this would maybe be a good name for your set $V$. It can be viewed as solution set of the following optimization problem:

$$\min||x||_0 \text{ subject to }Ax=b.$$

where $||\cdot||_0$ counts the number of nonzeros. Then $P(A,b)$ could be called "convex hull of sparse solutions".

References in this direction are for example Donoho and a survey by Lai.

-
add comment