What is the "Toeplitz matrices from the discrete gradient operators with forward difference"

Question

Recently I have read many papers which focusing on the image enhancement. The description,

$D$ are the Toeplitz matrices from the discrete gradient with forward difference

occurs many times.

An example is shown below:

To minimize an object function,

$$ F(T)=\sum_x\left((T(x)-L(x))^2 + \lambda\sum_{d\in\lbrace h,v\rbrace}A_d(x)\left(\partial_dT(x)\right)^2\right), $$

where $L(x)$ and $A_d(x)$ is known. So to minimize this function, we differentiating it and setting the derivative to 0, the problem is simplified to:

$$t=\left(I + \sum_{d\in\lbrace h, v\rbrace}D_d^TDiag(a_d)D_d\right)^{-1}l,$$

where $m$ is the vectorized version of $M$ and the operator $Diag(m)$ is to construct a diagonal matrix using vector $m$, and $D$ are the Toeplitz matrices from the discrete gradient with forward difference .

So my question is, what on earth is $D$ ? How to calculate this $D$ ? And what does the transpose (or adjoint) of this $D^T$ mean ?

Answer 1

A Toeplitz matrix is a band matrix in which each descending diagonal from left to right has constant elements. The derivative of a function can be represented in a finite-difference calculation as the product of a Toeplitz matrix and equally spaced values of $f$. One distinguishes forward differences and backwards differences, the forward difference is given by $$D[f](x)=f(x+\delta x)-f(x),$$ corresponding to a matrix with elements (in the $4\times 4$ case) $$D=\begin{pmatrix} -1&1&0&0\\ 0&-1&1&0\\ 0&0&-1&1\\ 1&0&0&-1 \end{pmatrix} $$ The backward difference is given by $-D^\top$, minus the transpose of the forward difference, $$-D^\top[f](x)=f(x)-f(x-\delta x).$$