Interpreting Simplicity

In A Low Complexity Solver ? I mentioned the possibility of finding low complexity solutions to an underdetermined linear system of equations through the use of a combination of the TV and the l_infty norm. Dror Baron kindly sent me the following on the matter of complexity:

I think that you might be interpreting complexity (or simplicity) in an overly simplified way (no pun intended). Yes, a signal whose values are all {-const,+const} as illustrated in this discussion is simple, because its entropy (complexity) is upper bounded by 1 bit per signal entry. Another signal that takes on 10 or so values but is zero 90% of the time also has an entropy below 1 bit per entry, because 90% of the time the signal entry has little information complexity. And Figure 1 in our paper uses a source where each of 2 values happens half the time (technically 1 bit per entry), but they occur in such a predictable pattern that the entropy was only 0.19 bits per entry. My point here is that low entropy corresponds to high probability, and different different types of structures - even those that appear complex to the naked eye - might have high probability. Hope that this clarification helps.
By the way, experts can now compress English text at just a bit above 1 bit per character. That is, you get all the capital letters, punctuation, and many different letters for 1 bit per character, because there is a lot of higher order structure.

Thanks Dror.!

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.