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

Question

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.

Answer 1

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.

Answer 2

Dima, your edit is correct. Note that the generators of the recession cone are in 1-1 correspondence to the circuit of the matrix $A$ (just split them into positive and negative parts), plus the obvious generators $(e_i,e_i)$.

Finding (overall) support minimal nonnegative solutions to a linear system of equations is an NP-hard problem in optimization, but I am not aware of consideration of the set of all such sparse solutions (including those with a non-minimum number of nonzeros). A natural suggestion for your polytope would be "polytope of sparse solutions".

Do you really have examples with infinite sets V? This looks impossible to me (= I could provide a proof).

Do you have some paper (by now) where you deal with this polytope? I'd be happy to read it.