Return to Question

Let $\mathbf{S}$ be a $m\times n$ matrix, with $m < n$. We define a subdimensional polytope as the space of $n$-dimensional vectors $\mathbf{x}$ that satisfy the following equation:

$$\mathbf{S}\cdot\mathbf{x}=0$$

subject to the inequalities:

$$\mathbf{a}\le\mathbf{x}\le\mathbf{b}$$

where $\mathbf{a}$ and $\mathbf{b}$ are $n$-dimensional vectors.

Denote by $\Omega$ this space of solutions. The projection of $\Omega$ over the $i$'th coordinate ($0\le i\le n$) is the function:

$$f_{k}\left(x_{k}\right)=\int\delta\left(\mathbf{S}\cdot\mathbf{x}\right)\prod_{i\ne k}\mathrm{d}x_{i}$$

where the integral goes through all the values of $x_i$ for all $i\ne k, 1\le i \le n$, and $\delta(\mathbf{y})$ is the $m$-dimensional Dirac's delta function, given by:

$$\delta\left(\mathbf{y}\right)=\prod_{j}\delta\left(y_{j}\right)$$

where $\delta(y_j)$ are ordinary one-variable Dirac's delta functions.

I understand that the exact computation of $f_{k}\left(x_{k}\right)$ is NP-hard. But I was wondering if something can be said about its form. I have the intuition that $f_{k}\left(x_{k}\right)$ should be concave, or at least unimodal. Can you prove this? What other properties $f_{k}\left(x_{k}\right)$ satisfies in general?

Let $\mathbf{S}$ be a $m\times n$ matrix, with $m < n$. We define a subdimensional polytope as the space of $n$-dimensional vectors $\mathbf{x}$ that satisfy the following equation:

$$\mathbf{S}\cdot\mathbf{x}=0$$

subject to the inequalities:

$$\mathbf{a}\le\mathbf{x}\le\mathbf{b}$$

where $\mathbf{a}$ and $\mathbf{b}$ are $n$-dimensional vectors.

Denote by $\Omega$ this space of solutions. The projection of $\Omega$ over the $i$'th coordinate ($0\le i\le n$) is the function:

$$f_{k}\left(x_{k}\right)=\int\delta\left(\mathbf{S}\cdot\mathbf{x}\right)\prod_{i\ne k}\mathrm{d}x_{i}$$

where the integral goes through all the values of $x_i$ for all $i\ne k, 1\le i \le n$, and $\delta(\mathbf{y})$ is the $m$-dimensional Dirac's delta function, given by:

$$\delta\left(\mathbf{y}\right)=\prod_{j}\delta\left(y_{j}\right)$$

where $\delta(y_j)$ are ordinary one-variable Dirac's delta functions.

I understand that the exact computation of $f_{k}\left(x_{k}\right)$ is NP-hard. But I was wondering if something can be said about its form. I have the intuition that $f_{k}\left(x_{k}\right)$ should be concave, or at least have zero or one maximum. Can you prove this? What other properties $f_{k}\left(x_{k}\right)$ satisfies in general?

Let $\mathbf{S}$ be a $m\times n$ matrix, with $m < n$. We define a subdimensional polytope as the space of $n$-dimensional vectors $\mathbf{x}$ that satisfy the following equation:

$$\mathbf{S}\cdot\mathbf{x}=0$$

subject to the inequalities:

$$\mathbf{a}\le\mathbf{x}\le\mathbf{b}$$

where $\mathbf{a}$ and $\mathbf{b}$ are $n$-dimensional vectors.

Denote by $\Omega$ this space of solutions. The projection of $\Omega$ over the $i$'th coordinate ($0\le i\le n$) is the function:

$$f_{k}\left(x_{k}\right)=\int\delta\left(\mathbf{S}\cdot\mathbf{x}\right)\prod_{i\ne k}\mathrm{d}x_{i}$$

where the integral goes through all the values of $x_i$ for all $i\ne k, 1\le i \le n$, and $\delta(\mathbf{y})$ is the $m$-dimensional Dirac's delta function, given by:

$$\delta\left(\mathbf{y}\right)=\prod_{j}\delta\left(y_{j}\right)$$

where $\delta(y_j)$ are ordinary one-variable Dirac's delta functions.

I understand that the exact computation of $f_{k}\left(x_{k}\right)$ is NP-hard. But I was wondering if something can be said about its form. I have the intuition that $f_{k}\left(x_{k}\right)$ should be truncated polynomials of degree related to $m$ and $n$. Can this be proved? If they are polynomials, what else can be said about them?

Let $\mathbf{S}$ be a $m\times n$ matrix, with $m < n$. We define a subdimensional polytope as the space of $n$-dimensional vectors $\mathbf{x}$ that satisfy the following equation:

$$\mathbf{S}\cdot\mathbf{x}=0$$

subject to the inequalities:

$$\mathbf{a}\le\mathbf{x}\le\mathbf{b}$$

where $\mathbf{a}$ and $\mathbf{b}$ are $n$-dimensional vectors.

Denote by $\Omega$ this space of solutions. The projection of $\Omega$ over the $i$'th coordinate ($0\le i\le n$) is the function:

$$f_{k}\left(x_{k}\right)=\int\delta\left(\mathbf{S}\cdot\mathbf{x}\right)\prod_{i\ne k}\mathrm{d}x_{i}$$

where the integral goes through all the values of $x_i$ for all $i\ne k, 1\le i \le n$, and $\delta(\mathbf{y})$ is the $m$-dimensional Dirac's delta function, given by:

$$\delta\left(\mathbf{y}\right)=\prod_{j}\delta\left(y_{j}\right)$$

where $\delta(y_j)$ are ordinary one-variable Dirac's delta functions.

I understand that the exact computation of $f_{k}\left(x_{k}\right)$ is NP-hard. But I was wondering if something can be said about its form. I have the intuition that $f_{k}\left(x_{k}\right)$ should be concave, or at least unimodal. Can you prove this? What other properties $f_{k}\left(x_{k}\right)$ satisfies in general?

Let $\mathbf{S}$ be a $m\times n$ matrix, with $m < n$. We define a subdimensional polytope as the space of $n$-dimensional vectors $\mathbf{x}$ that satisfy the following equation:

$$\mathbf{S}\cdot\mathbf{x}=0$$

subject to the inequalities:

$$\mathbf{a}\le\mathbf{x}\le\mathbf{b}$$

where $\mathbf{a}$ and $\mathbf{b}$ are $n$-dimensional vectors.

Denote by $\Omega$ this space of solutions. The projection of $\Omega$ over the $i$'th coordinate ($0\le i\le n$) is the function:

$$f_{k}\left(x_{k}\right)=\int\delta\left(\mathbf{S}\cdot\mathbf{x}\right)\prod_{i\ne k}\mathrm{d}x_{i}$$

where the integral goes through all the values of $x_i$ for all $i\ne k, 1\le i \le n$, and $\delta(\mathbf{y})$ is the $m$-dimensional Dirac's delta function, given by:

$$\delta\left(\mathbf{y}\right)=\prod_{j}\delta\left(y_{j}\right)$$

where $\delta(y_j)$ are ordinary one-variable Dirac's delta functions.

I understand that the exact computation of $f_{k}\left(x_{k}\right)$ is NP-hard. But I was wondering if something can be said about its form. I have the intuition that $f_{k}\left(x_{k}\right)$ should be polynomials of degree related to $m$ and $n$. Can this be proved? If they are polynomials, what else can be said about them?

Let $\mathbf{S}$ be a $m\times n$ matrix, with $m < n$. We define a subdimensional polytope as the space of $n$-dimensional vectors $\mathbf{x}$ that satisfy the following equation:

$$\mathbf{S}\cdot\mathbf{x}=0$$

subject to the inequalities:

$$\mathbf{a}\le\mathbf{x}\le\mathbf{b}$$

where $\mathbf{a}$ and $\mathbf{b}$ are $n$-dimensional vectors.

Denote by $\Omega$ this space of solutions. The projection of $\Omega$ over the $i$'th coordinate ($0\le i\le n$) is the function:

$$f_{k}\left(x_{k}\right)=\int\delta\left(\mathbf{S}\cdot\mathbf{x}\right)\prod_{i\ne k}\mathrm{d}x_{i}$$

where the integral goes through all the values of $x_i$ for all $i\ne k, 1\le i \le n$, and $\delta(\mathbf{y})$ is the $m$-dimensional Dirac's delta function, given by:

$$\delta\left(\mathbf{y}\right)=\prod_{j}\delta\left(y_{j}\right)$$

where $\delta(y_j)$ are ordinary one-variable Dirac's delta functions.

I understand that the exact computation of $f_{k}\left(x_{k}\right)$ is NP-hard. But I was wondering if something can be said about its form. I have the intuition that $f_{k}\left(x_{k}\right)$ should be truncated polynomials of degree related to $m$ and $n$. Can this be proved? If they are polynomials, what else can be said about them?