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

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ this looks like a rather standard multivariate calculus question. $\endgroup$
    – Dima Pasechnik
    Jan 3, 2020 at 3:46
  • 1
    $\begingroup$ What is "the previous one"? (Oh, I guess mathoverflow.net/questions/349554/… .) $\endgroup$
    – LSpice
    Jan 3, 2020 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, 2020 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, 2020 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$
    – RyanChan
    Jan 4, 2020 at 0:29

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.