How to sample a total variation prior?

Question

I am interested in drawing samples from a total variation prior: $$\pi_{\mathrm{pr}}(\boldsymbol{x})=\left(\frac{\alpha}{2}\right)^n\exp\left(-\alpha\sum_{j=0}^{n-1}\vert x_{j+1}-x_{j}\vert\right)=\left(\frac{\alpha}{2}\right)^n\exp\left(-\alpha\Vert\mathbf{L}\boldsymbol{x}\Vert_1\right)=\mathrm{Laplace}(\Vert\mathbf{L}\boldsymbol{x}\Vert_1;0,\alpha^{-1}),$$ where $\mathbf{L}$ is a difference matrix and $\alpha$ is the inverse of the scale parameter of a Laplace distribution.

My initial guess was to generate sample paths of a process such that: (i) it starts at 0, (ii) the increments are independent, and (iii) the increments are distributed according to $\mathrm{Laplace}(\cdot;0,\alpha^{-1})$. Is this procedure correct? Or is there any other way to generate samples from such distribution (other than MCMC)?

Thanks in advance!

Answer 1

The joint density $$\pi(\boldsymbol{x})=\overbrace{\left(\frac{\alpha}{2}\right)^n}^{\substack{ \text{correct}\\ \text{constant}}}\exp\left(-\alpha\sum_{j=0}^{n}\vert x_{j+1}-x_{j}\vert\right)$$ assuming $\boldsymbol{x}=(x_1,\ldots,x_n)$ writes as $$\pi(\boldsymbol{x})=\frac{\alpha}{2}\exp\left(-\alpha\vert x_{1}-x_{0}\vert\right)\frac{\alpha}{2}\exp\left(-\alpha\vert x_{2}-x_{1}\vert\right)\cdots\frac{\alpha}{2}\exp\left(-\alpha\vert x_{n}-x_{n-1}\vert\right)$$ and can be expressed as a product of conditional Laplace densities $$\pi(\boldsymbol{x})=f_\alpha(x_1|x_0)f_\alpha(x_2|x_1)\cdots f_\alpha(x_n|x_{n-1})$$meaning it can be simulated as

• simulate $X_1\sim \mathfrak{L}(x_0,\alpha)$
• simulate $X_2|X_1=x_1\sim \mathfrak{L}(x_1,\alpha)$
• $\qquad\vdots$
• simulate $X_n|X_{n-1}=x_{n-1}\sim \mathfrak{L}(x_{n-1},\alpha)$