Thursday, December 13, 2018

Christmas tree denoising via SDP

In our last year's Christmas special we ran logistic regression on a sampled Christmas tree. By public demand this year we treat the tree with some semidefinite programming.

We start with a $50 \times 100$ binary image with noise.

It is convenient to encode the image as a sequence of pixels $x_i\in\{-1,1\}$. Then we can write (see eg. here) a simple binary quadratic denoising model
$$\mathrm{maximize} \sum_{i\sim j}z_iz_j+\gamma\sum_i x_iz_i,\quad z_i\in\{-1,1\}$$
which favors similarity between neighboring ($i\sim j$) pixels in $z$ and the similarity between $z$ and the original $x$, with tradeoff between the two measures provided by $\gamma$.

Binary quadratic problems have a natural SDP relaxation, in this case 
$$ \begin{array}{ll} \mathrm{mazimize} & \sum_{i\sim j} Z_{ij} +\gamma x^Tz \\ \mathrm{s.t.} & \left[ \begin{array}{cc}Z&z\\z^T&1\end{array} \right] \succeq 0, \\ & \mathrm{diag}(Z)=1.\end{array} $$
We solve the SDP for various $\gamma$ ($Z$ has dimension $5000$; this is not the most efficient image processing algorithm ever invented). To further simplify we don't round but let the raw $z$ interpolate between shades of green. 

Merry Christmas from the MOSEK team.