5
$\begingroup$

This is a rewrite of the OP's question to emphasize what I think are the research level issues here.

Let $\mathscr{R}$ be a bounded convex body in $\mathbb{R}^n$ and let $H : \mathbb{R}^n \to \mathbb{R}^r$ be a surjective linear map for $r<n$. How can we compute the volume of $H(\mathscr{R})$? Of course, the answer to this question will depend on how $\mathscr{R}$ is given. I don't know what the OP intended, but here are some options I can see:

  • $\mathscr{R}$ is a convex polytope, given as a list of vertices.

  • $\mathscr{R}$ is a convex polytope, given as a list of facet inequalities

  • $\mathscr{R}$ is a $\{ f(x_1, \ldots, x_n) \leq c \}$, for $f$ some convex polynomial. We could generalize this to $\{ f_1 \leq c_1,\ f_2 \leq c_2,\ \cdots,\ f_N \leq c_N \}$ for some list of convex polynomials $f_j$.

  • There is some polynomial function $\phi$ sending $\mathbb{R}^n$ to symmetric $k \times k$ matrices, and $\mathcal{R}$ is the set of $\vec{x}$ so that $\phi(\vec{x})$ has at least $\ell$ nonnegative eigenvalues. (This sort of formulation is very common in semidefinite programming.)

There will probably also be different answers depending on whether we are considering $r$ and $n$ bounded, $r$ bounded with $n \to \infty$, or both $r$ and $n$ going to $\infty$.

The original question is below.


Consider a convex body $\mathscr{R}\subset \mathbb{R}^n$ and a rank-$r$ matrix $\mathbf{H}=[\mathbf{h}_1,\cdots,\mathbf{h}_n]\in \mathbb{R}^{r\times n}$. Assume that the $r$-dimensional volume of $\mathbf{H}\mathscr{R}=\{\mathbf{Hr}:\mathbf{r}\in\mathscr{R}\}$ is finite and nonzero.

How to compute it?

This problem is extended by the previous one (The $r$-dimensional volume of the Minkowski sum of $n$ ($n\geq r$) line sets).

$\endgroup$
  • 1
    $\begingroup$ this looks like a rather standard multivariate calculus question. $\endgroup$ – Dima Pasechnik Jan 3 at 3:46
  • 1
    $\begingroup$ What is "the previous one"? (Oh, I guess mathoverflow.net/questions/349554/… .) $\endgroup$ – LSpice Jan 3 at 5:11
  • 1
    $\begingroup$ If $\mathcal{R}$ is a polytope given by facet inequalities, POLYMAKE polymake.org/doku.php can compute its vertices but possibly at the cost of an exponential explosion. I suspect there are smarter things to do in this case. $\endgroup$ – David E Speyer Jan 3 at 14:40
  • 1
    $\begingroup$ I've taken the liberty of rewriting the question; see meta.mathoverflow.net/questions/4417 . $\endgroup$ – David E Speyer Jan 3 at 15:19
  • 1
    $\begingroup$ Thanks for DES-SupportsMonicaAndTransfolk's help. The edited question is more precise and tractable. Actually, this is a problem I met in the communication theory. I am not sure the region is indeed a convex polytope. Another interesting question is how to decompose the region into a disjoint union of subregions. In the original problem, I mentioned the rank of the matrix $\mathbf{H}$, which implies that $r\le n$. It is meaningful to emphasize $n>r$. $\endgroup$ – Ryan Chen Jan 4 at 0:29

Your Answer

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

Browse other questions tagged or ask your own question.