Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

1 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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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