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.
