Discrete Diffusion (D3PM)

• For scalar discrete random variables with $K$ categories

Forward process

• Transition matrix $[Q_t{]}_{ij}=p(x_t=j|x_{t-1}=i)$
• Forward process
  • $q(x_t|x_{t-1})=Cat(x_t;p=x_{t-1}{Q}_t)$
    • where $Cat(x;p)$ is a categorical distribution over the one-hot row vector $x$ with probabilites given by the row vector $p$.
    • $x_{t-1}{Q}_t$ is a row vector-matrix product
  • It is assumed that $Q_t$ is applied to each pixel or token independently, so $q(x_t|x_{t-1})$ represents the forward process for the entire object
• Closed forms
  • Forward: $q(x_t|x_0)=Cat(x_t;p=x_0{\bar{Q}}_t)$ with ${\bar{Q}}_t=Q_1...Q_t$
  • Posterior: $q(x_{t-1}|x_t,x_0)=\frac{q(x_t|x_{t-1},x_0)q(x_{t-1}|x_0)}{q(x_t|x_0)}=Cat(x_{t-1};p=\frac{x_t{Q}_t^T\odot x_0{\bar{Q}}_{t-1}}{x_0{\bar{Q}}_t{x}_t^T})$

Choice of transition matrix $Q_t$

• must converge to a know stationary distribution