Wednesday, July 22, 2015

Compressed sensing, information theory and economics

A comment from Bill made me recall how I'd looked at markets as an algorithm to solve a compressed sensing problem before starting this blog. This is mostly a placeholder post for some musings.

The idea behind "compressed sensing" is that if what you are trying to sense is sparse, then you don't need as many measurements to "sense" it if you measure it in the right basis [1]. A typical example is a sparse image that looks like a star field: a few points (k = 3) in mostly blank space (first image above). If you were incredibly lucky, you could measure exactly the three points (m = k = 3) and reproduce the image. However, information theory tells us that we need (see e.g. here [pdf]):

m > k log(n/k)

measurements. As what you are trying to measure gets more complex, you start to need all of the points (m ~ n) which is behind the Nyquist sampling theorem. You can think of the economic allocation problem as fairly sparse -- most of the time any one person is not buying bacon (note the diagram on the upper right if you are viewing this on a desktop browser). And the compressed measurement (the m's) happens when you read off the market price of bacon [2].

There are different algorithms that take advantage of the information provided by knowing your image is sparse. One of the least efficient algorithms is linear programming. Sound familiar? That's also a very inefficient way to solve the market allocation problem.

The algorithms that solve the sparse problem also have a tendency to fail if m is too low or if you add noise to the image (second image above). Additionally, the transition from failure to success can be fairly sharp -- referred to as a Donoho-Tanner phase transition by Igor Carron. Does this tell us something about market behavior? I don't know. As I said, these are just some musings.

Footnotes:

[1] For natural images, this basis tends to be the wavelet basis. For something like our star field above, the Fourier basis works.

[2] Does a market create a basis for sparsifying an economic allocation problem?

1. Interesting. Some years ago my boss asked me to write a proposal about compressed sensing and gave me (and an analog design engineer) 3 days (total: divided between the two of us) to do it... so I got out some papers and started reading. And no, of course we didn't win.

1. Yeah, we frequently end up with only a few days to respond to those things too. And your boss wonders why you don't win ...

2. O/T: this comment to a Nick Rowe post got me thinking (I know: dangerous!): I wonder if it's possible to design an experiment in which a room full of game theorists are given some sort of game, which they can win (if they chose the best number between 0 and 1), which seemingly is amenable to game theory, but the actual result of which produces a uniform "random" distribution of numbers on the interval.

1. I have no intuition regarding how one would construct such a game, but I've thought about the information transfer model as a limit of a large number of random games.

3. O/T #2: Kenneth Duda leaves a comment to David Glasner with this statement:

"Your point that we have no theoretical framework that explains the value of money is interesting as well."

Would your framework provide this?

1. I think it may be more social contrivance than economic theory ... But economic theory may pick the social contrivance:

http://informationtransfereconomics.blogspot.com/2015/06/the-definition-origin-and-purpose-of.html

2. Also what is interesting is that a theory of goods and services can be rewritten in terms of money if something like money exists:

http://informationtransfereconomics.blogspot.com/2015/05/money-defined-as-information-mediation.html

That post is linked to the post in the previous comment.

That is to say if something acts as money, it's going to appear to have value even if it doesn't (except as a social contrivance).

3. Also also, the idea of the worthlessness of money involves rational expectations ... Glasner says there might be a bit of irrationality.

However, the value of all things in a monetary economy is dependent on the existence of money (without money, you have less than ideal information transfer and thus everything is worth a bit less). Thus everyone has sunk costs associated with everyone continuing to accept money :)

4. Instead of another sucker, people are out looking for ways to accept money because it means their stuff has more value.

5. Or yet another way, it would be irrational for someone not to accept money, because it would mean his assets would fall in value (non ideal information transfer).

6. Thanks Jason. A lot to think about there.

Comments are welcome. Please see the Moderation and comment policy.

Also, try to avoid the use of dollar signs as they interfere with my setup of mathjax. I left it set up that way because I think this is funny for an economics blog. You can use € or £ instead.