Lossy compression and other hard optimization problems: a statistical physics approach

The task of data compression originally arises in the field of communications, where messages from a source must be delivered to a receiver in the most compact form, without losing (too much) information. Besides the countless practical applications in engineering, data compression is interesting enough to be studied on its own, its foundations being rooted in probability theory, optimization and other related disciplines which are in turn deeply linked to statistical physics. The class of problems analyzed here can be described as follows: given a random bit string of fixed length, design a compressing algorithm that casts it into a shorter string and a de-compressing algorithm that is able to reconstruct the original message up to some error. A cunning approach from Information Theory addresses the challenge by setting up a constrained optimization problem. It just so happens that such problem is completely equivalent to that of finding the Ground State of an Ising model defined on a graph that encodes the system of constraints. This opens up the way for a variety of well-known tools from statistical physics to be used in order to find an approximate solution that works in polynomial time, in our case the Belief Propagation algorithm. An efficient computer implementation is presented along with the results and a proof of exactness of the algorithm under some conditions is given. From the practical point of view, it was found that better performances are achieved by working with strings of numbers taking values in the so-called Galois Field GF(q), which can be thought of as a generalization of bits, taking values in 0,...,q-1. From the theoretical point of view, the most relevant observation is that a small modification of the graph's structure can lead to a remarkable increase in performance. There is good reason to think that this fact, together with the rest of our method, may be applied to other hard problems in the constrained optimization family.