Friday, October 28, 2011

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


Dirk said...

Kind of weird to give a comment to Dror on another man's blog, but well...

I think that the complexity of a solution of a jointly l-infty
and TV constrained problem has a complexity which is lower than 1-bit per sample: The l-infty constraint will push the solution to +const and -const and the TV constraint will probably lead to a small number and sign changes. Hence, the signal can be encoded by the position of the sign changes which is a small number.

Igor said...


I'd have to wholeheartidily agree with you :) but eventually the proof is in the pudding, if someone gets to implement this i'd be really interested in hearing back about it.