The closest vector problem and the zero-temperature p-spin landscape for lossy compression

Abstract

We consider a high-dimensional random constrained optimization problem in which a set of binary variables is subjected to a linear system of equations. The cost function is a simple linear cost, measuring the Hamming distance with respect to a reference configuration. Despite its apparent simplicity, this problem exhibits a rich phenomenology. We show that different situations arise depending on the random ensemble of linear systems. When each variable is involved in at most two linear constraints, we show that the problem can be partially solved analytically, in particular we show that upon convergence, the zero-temperature limit of the cavity equations returns the optimal solution. We then study the geometrical properties of more general random ensembles. In particular we observe a range in the density of constraints at which the systems enters a glassy phase where the cost function has many minima. Interestingly, the algorithmic performances are only sensitive to another phase transition affecting the structure of configurations allowed by the linear constraints. We also extend our results to variables belonging to $\text{GF}(q)$, the Galois Field of order $q$. We show that increasing the value of $q$ allows to achieve a better optimum, which is confirmed by the Replica Symmetric cavity method predictions.

arXiv comment29 pages, 13 figures

References in corpus (18)

• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Rigorous Inequalities between Length and Time Scales in Glassy Systems
• Maximum Weight Matching via Max-Product Belief Propagation
• Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
• Learning by message-passing in networks of discrete synapses
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• On the dynamics of the glass transition on Bethe lattices
• The Dynamic Phase Transition for Decoding Algorithms
• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
• On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms
• The cavity method at zero temperature
• Statistical Mechanics of Low-Density Parity Check Error-Correcting Codes over Galois Fields
• Biased landscapes for random Constraint Satisfaction Problems
• Clustering of solutions in the symmetric binary perceptron
• High dimensional optimization under non-convex excluded volume constraints
• Efficient data compression from statistical physics of codes over finite fields
• Optimization of the dynamic transition in the continuous coloring problem