Source coding by efficient selection of ground-state clusters

We analyze the geometrical structure of clusters of ground states which appear in many frustrated systems over random graphs. Focusing on the regime of connectivities where the number of clusters is exponential in the size of the problems, we identify an appropriate generalization of the survey propagation equations efficiently exploring the geometry. The possibility of selecting different clusters has also computational consequences. As a proof of concept here we show how a well-known physical system can be used to perform nontrivial data compression, for which we introduce a unique compression scheme. Performances are optimized when the number of well-separated clusters is maximal in the underlying physical model.

Figure 1

Distribution of distances. A solution ${\zeta }_d$ is generated by forcing along a vector with $d$ spins flipped with respect to a reference solution $\sigma$. The difference between the 1-RSB and $f$-RSB cases appears by both looking at the stability diagrams themselves (white circles against black squares) and at the reciprocal distances histograms.

Figure 2

Rate-distortion profile for the compression of a random source. Various decompression methods are used—simple cluster reconstruction, reconstruction with doping, and with doping and SP/BP interpolation. The performance of repetition codes and of random guessing is also plotted for comparison.

Figure 3

Phase diagram for fixed degree 5-SAT and compression performance for two biased sources ($b=0.2$ and $b=0.3$). The white circles—following closely the Gardner instability line—show the position of the best instances found for the compression of differently biased sources.