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.


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.


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.

  • $\begingroup$ I must say I don't recall details right now - I was computing something generalising triangulations, using 4t2. $\endgroup$ – Dima Pasechnik Mar 27 '15 at 8:31

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.