Compressed sensing games

Compressed sensing has been proved having intimate connections to tremendous problems in signal processing and harmonic analysis. The fundamental idea of compressed sensing and its extension matrix completion can be illustrated as:

It is possible to recover a signal (e.g., series, matrix, data, …) from a few measurements (e.g., FFT, DCT, sampling, linear, nonlinear, …) of it, if the signal has some particular properties (e.g., sparse, grouping, low-rank, low rank+sparse, on manifold, …).

What is more interesting is that compressed sensing is also strongly related to several intelligent games. To name a few:

1. Sudoku.

Example of Sudoku

The objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 sub-grids that compose the grid (also called “boxes”, “blocks”, “regions”, or “sub-squares”) contains all of the digits from 1 to 9. The measurements are the known entries, and the properties is the ruleset. The problem can be formulated into a linear system with sparse solutions, which is exactly a compressed sensing problem. An interesting paper named “Linear Systems, Sparse Solutions, and Sudoku” can be found at:

http://uu.diva-portal.org/smash/get/diva2:292157/FULLTEXT01

The link of corresponding code in Python and MatLab can be found at

http://transfinite.wordpress.com/2009/12/06/solving-sudoku-with-l1-norm-minimization/

2. 12 balls problem. There are 12 balls with the same appearance. One of them has different weight compared with the others. One balance is given and only 3 measurements are permitted. The goal is to identify the different ball and justify whether it is heavier or lighter. Here is an example solution:

Example of 12-balls problem

Example of 12-balls problem

The signal is a vector with 1 or -1 on the index w.r.t the different ball and 0 on the other entries. The measurements are the 3 weighting experiments on the balance. So again, a compressed sensing can be formulated. It can also be formulated as a Group testing problem. There is a paper illustrating the relationship between compressed sensing and group testing:

Group Testing and Sparse Signal Recovery

The above are only two representatives and I believe there exist many. It is very interesting that some of these problems are discrete optimization problems. This may provide potential to solve discrete optimization problems by using compressed sensing techniques.

Igor makes a website about compressed sensing games, where other 3 games related to compressed sensing are introduced. You can find it here. Thanks a lot, Igor!

Advertisements

About tianyizhou

Research Assistant at University Washington, Seattle, Working on Machine Learning & Statistics in MODE lab leaded by Prof. Carlos Guestrin, and MELODI lab leaded by Prof. Jeff Bilmes.
This entry was posted in notes and tagged , , . Bookmark the permalink.

2 Responses to Compressed sensing games

  1. Igor Carron says:

    Hi Tianyi,

    You can find others here: http://sites.google.com/site/igorcarron2/games

    Cheers,

    Igor.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s