Month: February 2016

Solving Nonograms with Compressive Sensing: Part 2

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:

stylish_lambda

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

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!

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

Find the Right Whale

This is a right whale. Right now, there are only 450 right whales alive in the North Atlantic Ocean. They are the rarest among all large whales.

But fear not. A month ago, a group of people came to their rescue, and those people? They were data scientists.

Continue reading “Find the Right Whale”

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.)

heart_diagram

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)?

Continue reading “Monte Carlo Simulations: How Big Is Your Heart?”

Visualize Linear Algebra

Since last week, I’ve worked on a side project for Robert, my former advisor and good friend. He told me that Matlab has a function called eigshow, which creates a GUI to help us “see” singular value decomposition and eigenvalue decomposition. He wanted a GUI that would similarly help us see and understand induced matrix norm.

The GUI that eigshow creates is cool but rudimentary. What really bothers me is how poorly the code was maintained, with no documentation. I could follow it after some time, but I decided it would be better if I write my GUI from scratch.

So far, my GUI helps you visualize three things:

  1. Matrix norm
  2. Singular value decomposition
  3. Eigenvalue decomposition

The GUI feels great if you have touchscreen and move the vectors with your finger instead of a mouse. I’m hoping to add more features (my code are very modular!) before I get to present linear algebra here. We’ll definitely go over some of the GUI aspects then. Until then, please enjoy these screenshots that I made.

You can find the code in its entirety here:
Download from GitHub

vla_matrix_norm

vla_singular_values

vla_eigenvalues