Solving Nonograms with Compressive Sensing: Part 4

Last time, we considered the linear equations and linear inequalities that the solution of a nonogram must satisfy. Let us now solve the minimization problem and see how well compressive sensing works. I will consider several examples, then offer a simple fix for the problems that we will encounter.

Continue reading “Solving Nonograms with Compressive Sensing: Part 4”

Advertisements

Solving Nonograms with Compressive Sensing: Part 3

We know how to represent the solution of a nonogram as a sparse vector \vec{x} \in \{0,\,1\}^{N}. Let us now design the constraints; they will be linear equations and linear inequalities that the entries of \vec{x} must satisfy according to the nonogram. The only information that the nonogram provides are the row and column sequences, so we want to make the most of it. Afterwards, we obtain the sparse vector \vec{x} by minimizing its 1-norm under these constraints. I will discuss the code and the results in the next and final post.

Continue reading “Solving Nonograms with Compressive Sensing: Part 3”