Channel Simulation with Poisson Processes


Gergely Flamich

05/04/2023

1. Lossy Image Compression

image_compression.png

2. Channel Simulation

Source \(X\), latent \(Z\), model \(P_{X, Z}\)

Encoder:

  1. Receive \(X \sim P_X\) from source
  2. Encode \(Z \sim P_{Z \mid X}\) using \(P_Z\)

Decoder:

  1. Recover \(Z\) using \(P_Z\)
  2. Recover \(\hat{X} \sim P_{X \mid Z}\)

3. Channel Simulation

Assumptions

  • \(I[X; Z] < \infty\)
  • Can simulate \(Z \sim P_Z\)
  • Encoder and decoder share PRNG seed

4. Poisson Processes

  • Collection of random points in space
  • Focus on spatio-temporal processes on \(\mathbb{R}^D \times \mathbb{R}^+\)
  • Exponential inter-arrival times
  • Spatial distribution \(P_{X \mid T}\)

4.1. Poisson Processes

pp_alg.png

4.2. Example with \(P_{X \mid T} = \mathcal{N}(0, 1)\)

empty_pp.png

4.3. Example with \(P_{X \mid T} = \mathcal{N}(0, 1)\)

pp_t1.png

4.4. Example with \(P_{X \mid T} = \mathcal{N}(0, 1)\)

pp_x1.png

4.5. Example with \(P_{X \mid T} = \mathcal{N}(0, 1)\)

pp_t1_x1.png

4.6. Example with \(P_{X \mid T} = \mathcal{N}(0, 1)\)

pp_t2.png

4.7. Example with \(P_{X \mid T} = \mathcal{N}(0, 1)\)

pp_x2.png

4.8. Example with \(P_{X \mid T} = \mathcal{N}(0, 1)\)

pp_t2_x2.png

4.9. Example with \(P_{X \mid T} = \mathcal{N}(0, 1)\)

pp_sim.png

5. Rejection Sampling

  • Sampling algorithm for target distribution \(Q\).
  • Using proposal \(P\)
  • Bound on their density ratio \(q/p\): \(M\)

5.1. Rejection Sampling

5.2. RS with \(P = \mathcal{N}(0, 1), Q = \mathcal{N}(1, 1/16)\)

rs_0.png

5.3. RS with \(P = \mathcal{N}(0, 1), Q = \mathcal{N}(1, 1/16)\)

rs_1.png

5.4. RS with \(P = \mathcal{N}(0, 1), Q = \mathcal{N}(1, 1/16)\)

rs_2.png

5.5. RS with \(P = \mathcal{N}(0, 1), Q = \mathcal{N}(1, 1/16)\)

rs_3.png

5.6. RS with \(P = \mathcal{N}(0, 1), Q = \mathcal{N}(1, 1/16)\)

rs_4.png

5.7. RS with \(P = \mathcal{N}(0, 1), Q = \mathcal{N}(1, 1/16)\)

rs_5.png

5.8. RS with \(P = \mathcal{N}(0, 1), Q = \mathcal{N}(1, 1/16)\)

rs_6.png

5.9. RS with \(P = \mathcal{N}(0, 1), Q = \mathcal{N}(1, 1/16)\)

rs_7.png

5.10. RS with \(P = \mathcal{N}(0, 1), Q = \mathcal{N}(1, 1/16)\)

rs_8.png

5.11. RS with \(P = \mathcal{N}(0, 1), Q = \mathcal{N}(1, 1/16)\)

rs_9.png

5.12. RS with \(P = \mathcal{N}(0, 1), Q = \mathcal{N}(1, 1/16)\)

rs_10.png

5.13. RS with \(P = \mathcal{N}(0, 1), Q = \mathcal{N}(1, 1/16)\)

rs_accept.png

6. Channel Simulation with Rejection Sampling

Encoder:

  • Receive \(X \sim P_X\)
  • Rejection sample from \(P_{Z \mid X}\) using \(P_Z\).
  • Send index \(K\) of the accepted sample.

Decoder:

  • Simulate the same \(K\) samples from \(P_Z\)

7. Efficiency of RS

Best possible bound is \(M^* = \sup_{z} \frac{p(z \mid X)}{p(z)}\).

Define \(D_{\inf}[P_{Z \mid X} \Vert P_Z] = \log M^*\).

\(K\) is geometric.

\(H[K \mid X] \geq D_{\inf}[P_{Z \mid X} \Vert P_Z]\).

\(\mathbb{E}[K \mid X] = \exp(D_{\inf}[P_{Z \mid X} \Vert P_Z])\).

8. Greedy Poisson Rejection Sampling

gprs_alg.png

8.1. GPRS with \(P = \mathcal{N}(0, 1), Q = \mathcal{N}(1, 1/16)\)

gprs_0.png

8.2. GPRS with \(P = \mathcal{N}(0, 1), Q = \mathcal{N}(1, 1/16)\)

gprs_1.png

8.3. GPRS with \(P = \mathcal{N}(0, 1), Q = \mathcal{N}(1, 1/16)\)

gprs_2.png

8.4. GPRS with \(P = \mathcal{N}(0, 1), Q = \mathcal{N}(1, 1/16)\)

gprs_3.png

8.5. GPRS with \(P = \mathcal{N}(0, 1), Q = \mathcal{N}(1, 1/16)\)

gprs_4.png

8.6. GPRS with \(P = \mathcal{N}(0, 1), Q = \mathcal{N}(1, 1/16)\)

gprs_5.png

8.7. GPRS with \(P = \mathcal{N}(0, 1), Q = \mathcal{N}(1, 1/16)\)

gprs_accept.png

9. How to find \(\sigma\)?

Define

\[ W(h) = \int_0^h \min\left\{h \cdot p(z), p(z \mid X)\right\} \, dz \]

Then

\[ \sigma(h) = \int_0^h \frac{1}{1 - W(\eta)} \, d\eta. \]

10. How to find \(\sigma\)?

11. Analysis of GPRS

Codelength

\[ H[K \mid X] \leq D_{KL}[P_{Z \mid X} \Vert P_Z] + \log(D_{KL}[P_{Z \mid X} \Vert P_Z] + 1) + \mathcal{O}(1) \]

\[ H[K] \leq I[X; Z] + \log(I[X; Z] + 1) + \mathcal{O}(1) \]

Runtime

\[ \mathbb{E}[K \mid X] = \exp(D_{\inf}[P_{Z \mid X} \Vert P_Z]) \]

12. Speeding up GPRS

gprs_accept.png

12.1. Fast GPRS with \(P = \mathcal{N}(0, 1), Q = \mathcal{N}(1, 1/16)\)

fast_gprs_0.png

12.2. Fast GPRS with \(P = \mathcal{N}(0, 1), Q = \mathcal{N}(1, 1/16)\)

fast_gprs_1.png

12.3. Fast GPRS with \(P = \mathcal{N}(0, 1), Q = \mathcal{N}(1, 1/16)\)

fast_gprs_2.png

12.4. Fast GPRS with \(P = \mathcal{N}(0, 1), Q = \mathcal{N}(1, 1/16)\)

fast_gprs_3.png

12.5. Fast GPRS with \(P = \mathcal{N}(0, 1), Q = \mathcal{N}(1, 1/16)\)

fast_gprs_4.png

12.6. Fast GPRS with \(P = \mathcal{N}(0, 1), Q = \mathcal{N}(1, 1/16)\)

fast_gprs_5.png

13. Analysis of faster GPRS

Now, encode search path \(\pi\).

\(H[\pi] \leq I[X; Z] + \log(I[X; Z] + 1) + \mathcal{O}(1)\)

\(\mathbb{E}[\lvert\pi\rvert] = \mathcal{O}(I[X; Z])\)

14. Some Open Questions

  • Fast algorithm for multivariate Gaussians?
  • Tighter general lower bound on runtime?