Lossy data compression with random gates

Abstract

We introduce a new protocol for a lossy data compression algorithm which is based on constraint satisfaction gates. We show that the theoretical capacity of algorithms built from standard parity-check gates converges exponentially fast to the Shannon's bound when the number of variables seen by each gate increases. We then generalize this approach by introducing random gates. They have theoretical performances nearly as good as parity checks, but they offer the great advantage that the encoding can be done in linear time using the Survey Inspired Decimation algorithm, a powerful algorithm for constraint satisfaction problems derived from statistical physics.

References in corpus (7)

• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Clustering of solutions in the random satisfiability problem
• On the nature of the low-temperature phase in discontinuous mean-field spin glasses
• Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
• A variational description of the ground state structure in random satisfiability problems
• Statistical mechanics of lossy data compression using a non-monotonic perceptron
• Minimizing energy below the glass thresholds

Cited by in corpus (14)

• Solving Constraint Satisfaction Problems through Belief Propagation-guided decimation
• Survey-propagation decimation through distributed local computations
• Encoding for the Blackwell Channel with Reinforced Belief Propagation
• The theoretical capacity of the Parity Source Coder
• Statistical Mechanical Approach to Lossy Data Compression:Theory and Practice
• Efficient LDPC Codes over GF(q) for Lossy Data Compression
• Polar Codes are Optimal for Lossy Source Coding
• A Practical Approach to Lossy Joint Source-Channel Coding
• Efficient data compression from statistical physics of codes over finite fields
• Low density majority codes and the problem of graceful degradation
• Lower Bounds on the Rate-Distortion Function of Individual LDGM Codes
• Universal Behavior in Large-scale Aggregation of Independent Noisy Observations
• Rate Distortion Theorem and the Multicritical Point of Spin Glass
• On Low Density Majority Codes