Does Richter's "4096 Colours" painting fulfill the Restricted Isometry Property for Sparse Signal Recovery ?

When Rich Baraniuk gave a talk at Lawrence Livermore two weeks ago, he probably wasn't expecting each and every one word of his talk to be dutifully parsed.

However Jovana Helms was attending the talk. So when Rich claimed that Gerhart Richter's famous "4096 Colours" painting might satisfy the Restricted Isometry Property (RIP) when used as a sensing matrix for sparse signal recovery, it triggered some investigation.

Jovana and Hyrum Anderson, a reader of Nuit Blanche, did the only thing that had to be done....Check that property out. As Hyrum points out:

"...Well, it's NP hard to certify RIP. So, instead here's a quick phase transition diagram from using the first [or some random] M rows of the painting (converted to grayscale) as a sensing matrix, using Michael Friedlander's SPGL1 for basis pursuit reconstruction. Turns out that the painting has CS properties. But only slightly. =)...

....Normalizing rows of A is unimportant, since it's just a convention; but making the elements of A zero mean is quite important (as D. Brady and others have said, it doubles the compression power by allowing negative elements)."

Here are the transition diagrams (both for random and non random selection of rows)

My take was that...:

.....The phase transition curve looks very low indeed but, if I remember correctly from the computations performed by Jared Tanner, so does an RIP phase transition ( see slides 35/36 of this presentation http://www.math.tamu.edu/%7Epopov/L12008/talks/slides_threshold.pdf )

It is in fact, because RIP is only sufficient (i.e. low phase transition) that the phase transition found by Donoho and Tanner became a better result to try to emulate.

To summarize, the low phase transition [you found] may indeed show that this matrix is RIP but it also shows that it does not seem to fulfill a weaker condition for sparse recovery, which is a shame :)

Hyrum eventually added:

"....I saw this on Wikipedia the other day, but failed to mention it to you: 

"When he began to make these paintings, Richter had his friend Blinky Palermo randomly call out colors, which Richter then adopted for his work. Chance thus plays its role in the creation of his first series." 

There is randomness in the painting afterall---its intensity histogram far from maximum entropy, however---so it's not surprising that it has CS properties. ..

It's, at least, a sign that human random generators are probably not that optimal.  Hyrum  provided the implementation that produced the graph above. It is here.

Now the other question that needs investigating is whether the 2007 stained glass window of the Cologne Cathedral is more optimal when it comes to the Donoho-Tanner transition ? It needs to be said but the arrangement of the glass reminds me of a tree like structure which might be a good sensing matrix for some structured signal acquisition.  At the very least, it looks like an implementation of a multispectral coded aperture. 

The exercise might look a little futile and maybe a little nerdy but it shows really the good reflex to have when faced with particular sensing matrices. Every so often, on the Compressive Sensing group we get a question about whether  a specific matrix needs to fulfill the RIP, when in fact, in most engineering situation, your real concern should be about whether your measurement matrix fulfills a weaker sparse signal condition. The only way to answer  that efficiently is to perform a test as Hyrum and Jovana did..

Anyway, thanks Hyrum, Jovana and  Rich for the insight and the chuckle :)

Credit photos: wikipedia

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.