Skip to main content
edited title
Link
dohmatob
  • 6.9k
  • 1
  • 18
  • 76

Using Kac-Rice formula to count average number of sub-regions carved out by $n$ random hyperplaneshyper-planes

added 211 characters in body
Source Link
dohmatob
  • 6.9k
  • 1
  • 18
  • 76

Context. This is the first in a set of tiny pieces of a problem I've formulated to help me measure the "complexity" of certain piecewise linear functions. Thanks in advance for your help and patience.

So, let $W$ be drawn from a Ginibre ensemble (i.e the entries are i.i.d $\mathcal N(0, 1)$) of size $n\times m$ and let $b \in \mathbb R^n$ be fixed (we might consider variations where $b$ is random...). For $1 \le i \le n$, consider the random hyperplane defined by $\mathcal H_i := \{x \in \mathbb R^m \mid w_i^Tx = b_i\}$. The $\mathcal H_i$'s cut $\mathbb R^m$ into $N_W \ge 1$ disjoint regions.

Question

What is the expected value of $N_W$ over all possible realizations of $W$ ?

Observations

  • Somehow, I feel I should be able to pull off something via the Kac-Rice formula for random Gaussian fields, but I don't quite know how to start.

  • It's not difficult to get the upper bound $N_W \le \sum_{j=0}^{\text{rank}(W)} {{n}\choose{j}}$. For example, one can use the counting arguments in https://math.stackexchange.com/a/339853/168758. Thus, using the fact $W$ is of full rank $r=\max(n,m)$ almost surely, we have the (very very crude bound) $$ \begin{split} \mathbb E_W[N_W] \le \mathbb E_W\left[\sum_{j=0}^{\text{rank}(W)} {{n}\choose{j}}\mid \text{rank}(W)=k\right] &= \sum_{k=0}^{r} P(\text{rank}(W)=k)\sum_{j=0}^k {{n}\choose{j}}\\ &= \sum_{j=0}^r {{n}\choose{j}} \end{split} $$

Context. This is the first in a set of tiny pieces of a problem I've formulated to help me measure the "complexity" of certain piecewise linear functions. Thanks in advance for your help and patience.

So, let $W$ be drawn from a Ginibre ensemble (i.e the entries are i.i.d $\mathcal N(0, 1)$) of size $n\times m$ and let $b \in \mathbb R^n$ be fixed (we might consider variations where $b$ is random...). For $1 \le i \le n$, consider the random hyperplane defined by $\mathcal H_i := \{x \in \mathbb R^m \mid w_i^Tx = b_i\}$. The $\mathcal H_i$'s cut $\mathbb R^m$ into $N_W \ge 1$ disjoint regions.

Question

What is the expected value of $N_W$ over all possible realizations of $W$ ?

Observations

  • Somehow, I feel I should be able to pull off something via the Kac-Rice formula for random Gaussian fields, but I don't quite know how to start.

  • It's not difficult to get the upper bound $N_W \le \sum_{j=0}^{\text{rank}(W)} {{n}\choose{j}}$. For example, one can use the counting arguments in https://math.stackexchange.com/a/339853/168758.

Context. This is the first in a set of tiny pieces of a problem I've formulated to help me measure the "complexity" of certain piecewise linear functions. Thanks in advance for your help and patience.

So, let $W$ be drawn from a Ginibre ensemble (i.e the entries are i.i.d $\mathcal N(0, 1)$) of size $n\times m$ and let $b \in \mathbb R^n$ be fixed (we might consider variations where $b$ is random...). For $1 \le i \le n$, consider the random hyperplane defined by $\mathcal H_i := \{x \in \mathbb R^m \mid w_i^Tx = b_i\}$. The $\mathcal H_i$'s cut $\mathbb R^m$ into $N_W \ge 1$ disjoint regions.

Question

What is the expected value of $N_W$ over all possible realizations of $W$ ?

Observations

  • Somehow, I feel I should be able to pull off something via the Kac-Rice formula for random Gaussian fields, but I don't quite know how to start.

  • It's not difficult to get the upper bound $N_W \le \sum_{j=0}^{\text{rank}(W)} {{n}\choose{j}}$. For example, one can use the counting arguments in https://math.stackexchange.com/a/339853/168758. Thus, using the fact $W$ is of full rank $r=\max(n,m)$ almost surely, we have the (very very crude bound) $$ \begin{split} \mathbb E_W[N_W] \le \mathbb E_W\left[\sum_{j=0}^{\text{rank}(W)} {{n}\choose{j}}\mid \text{rank}(W)=k\right] &= \sum_{k=0}^{r} P(\text{rank}(W)=k)\sum_{j=0}^k {{n}\choose{j}}\\ &= \sum_{j=0}^r {{n}\choose{j}} \end{split} $$

added 211 characters in body
Source Link
dohmatob
  • 6.9k
  • 1
  • 18
  • 76

Context. This is the first in a set of tiny pieces of a problem I've formulated to help me measure the "complexity" of certain piecewise linear functions. Thanks in advance for your help and patience.

So, let $W$ be drawn from a Ginibre ensemble (i.e the entries are i.i.d $\mathcal N(0, 1)$) of size $n\times m$ and let $b \in \mathbb R^n$ be fixed (we might consider variations where $b$ is random...). For $1 \le i \le n$, consider the random hyperplane defined by $\mathcal H_i := \{x \in \mathbb R^m \mid w_i^Tx = b_i\}$. The $\mathcal H_i$'s cut $\mathbb R^m$ into $N$$N_W \ge 1$ disjoint regions.

Question

What is the expected value of $N$ (over$N_W$ over all possible realizations of $W$) ?

Observations

Somehow, I feel I should be able to pull off something via the Kac-Rice formula for random Gaussian fields, but I don't quite know how to start.

  • Somehow, I feel I should be able to pull off something via the Kac-Rice formula for random Gaussian fields, but I don't quite know how to start.

  • It's not difficult to get the upper bound $N_W \le \sum_{j=0}^{\text{rank}(W)} {{n}\choose{j}}$. For example, one can use the counting arguments in https://math.stackexchange.com/a/339853/168758.

Context. This is the first in a set of tiny pieces of a problem I've formulated to help me measure the "complexity" of certain piecewise linear functions. Thanks in advance for your help and patience.

So, let $W$ be drawn from a Ginibre ensemble (i.e the entries are i.i.d $\mathcal N(0, 1)$) of size $n\times m$ and let $b \in \mathbb R^n$ be fixed (we might consider variations where $b$ is random...). For $1 \le i \le n$, consider the random hyperplane defined by $\mathcal H_i := \{x \in \mathbb R^m \mid w_i^Tx = b_i\}$. The $\mathcal H_i$'s cut $\mathbb R^m$ into $N$ disjoint regions.

Question

What is the expected value of $N$ (over all possible realizations of $W$) ?

Observations

Somehow, I feel I should be able to pull off something via the Kac-Rice formula for random Gaussian fields, but I don't quite know how to start.

Context. This is the first in a set of tiny pieces of a problem I've formulated to help me measure the "complexity" of certain piecewise linear functions. Thanks in advance for your help and patience.

So, let $W$ be drawn from a Ginibre ensemble (i.e the entries are i.i.d $\mathcal N(0, 1)$) of size $n\times m$ and let $b \in \mathbb R^n$ be fixed (we might consider variations where $b$ is random...). For $1 \le i \le n$, consider the random hyperplane defined by $\mathcal H_i := \{x \in \mathbb R^m \mid w_i^Tx = b_i\}$. The $\mathcal H_i$'s cut $\mathbb R^m$ into $N_W \ge 1$ disjoint regions.

Question

What is the expected value of $N_W$ over all possible realizations of $W$ ?

Observations

  • Somehow, I feel I should be able to pull off something via the Kac-Rice formula for random Gaussian fields, but I don't quite know how to start.

  • It's not difficult to get the upper bound $N_W \le \sum_{j=0}^{\text{rank}(W)} {{n}\choose{j}}$. For example, one can use the counting arguments in https://math.stackexchange.com/a/339853/168758.

added 5 characters in body
Source Link
dohmatob
  • 6.9k
  • 1
  • 18
  • 76
Loading
Source Link
dohmatob
  • 6.9k
  • 1
  • 18
  • 76
Loading