3. Introducing compressive sensing

Today, we will consider how to turn the solution of a nonogram into a sparse vector. But first, let me take a detour and illustrate an approach that Oscar and I initially had considered and comment on its strengths and weaknesses in solving the puzzle.

Throughout our discussion, we will consider the stylish lambda example:

Solving Nonograms with Compressive Sensing: Part 1

Over the next month, I want to present a project that my friend Oscar and I came up with and worked on for a class. We developed a new technique to solve nonograms using compressive sensing.

The trick is knowing how to write the solution to any nonogram as a sparse vector $\vec{x}$. Sparse means there are many entries that are zero, and compressive sensing considers this fact to find a unique solution to an underdetermined system! It’s strikingly different from traditional linear algebra, which says that an underdetermined system that has a solution has, in fact, infinitely many solutions.

Our method avoids (1) partial fill-ins, (2) heuristics, and (3) over-complication, and only requires that we solve a binary integer programming problem. There was one issue that Oscar and I couldn’t solve in time, however. I hope that I can now by revisiting this project after three years. Ideas are welcome!

Monte Carlo Simulations: How Big Is Your Heart?

Our final problem has no known exact solution. We want to find the area of the shape formed by,

$(x^{2} + y^{2} - r^{2})^{3} - a\,x^{2}y^{3} \leq 0$

The inequality has two parameters $r$ and $a$. They are quantities of length, so they take on a nonnegative value. Let’s try out some values and see what these parameters do. I have colored the resulting shapes in red. (Note, the scales are different.)

When $r = a$ (move along the diagonal, starting from bottom-left), we get the shape of a nice heart. When we increase $r$ while holding $a$ fixed, the heart morphs into a circle. On the other hand, when we increase $a$ while holding $r$ fixed, the heart turns into two petals. Well, I see bunny ears.

Clearly, the shape (i.e. area) of our heart depends on the radius $r$ and the ear length $a$. Can you guess the formula for the area $A = A(r, a)$?

Monte Carlo Simulations: Buffon’s Needle

Buffon’s needle is a classic Monte Carlo simulation that we can conduct in a classroom. We give the students, say 10 needles each, and have them drop the needles on a paper that we provide also. The paper is special, in that it has parallel lines that are separated by the length of a needle. Each student records how many needles intersect one of the lines, then we tally their numbers to arrive at a very special number. (Guess who?)

In a class of 30, we have 300 samples to determine this special number. If the students had repeated the experiment ten times (any more than this risks frustration and wrath), we would have 3,000 samples at best. But with a computer program, we can make a million samples easily. In less than a second!

So today, we will learn how to write a program that generates needles (line segments). Our program needs to determine if a needle intersects a line. In general, checking if two line segments intersect is not an easy task. It’s rather amazing how we can look at many line segments (like the ones in the picture above) and instantly tell which lines intersect with which others. In our problem, fortunately, the lines on the paper are parallel and are equally spaced apart. We can use this fact to come up with a simple solution. Lastly, we will learn how to vectorize our code. Vectorization allows us to arrive at the answer quickly.