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.
Battaglia
Demian
D
SISSA, Via Beirut 9, I-34100 Trieste, Italy.
Braunstein
Alfredo
A
Chavas
Joël
J
Zecchina
Riccardo
R