Decoding from pooled data: sharp information-theoretic bounds

DOI10.1137/18M1183339MaRDI QIDQ5025779zbMATH OpenOpenAlexFDO

Authors Aaditya Ramdas, Florent Krzakala, Lenka Zdeborová, Michael Jordan, Ahmed El Alaoui

Publication date 3 February 2022

Published in SIAM Journal on Mathematics of Data Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1611.09981

zbMATH Keywords

categorical datacompressed sensingplanted modelsrandom constraint satisfactionsatisfiability threshold

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Statistical aspects of information-theoretic topics (62B10) Analysis of algorithms and problem complexity (68Q25)

Abstract: Consider a population consisting of n individuals, each of whom has one of d types (e.g. their blood type, in which case d=4). We are allowed to query this database by specifying a subset of the population, and in response we observe a noiseless histogram (a d-dimensional vector of counts) of types of the pooled individuals. This measurement model arises in practical situations such as pooling of genetic data and may also be motivated by privacy considerations. We are interested in the number of queries one needs to unambiguously determine the type of each individual. In this paper, we study this information-theoretic question under the random, dense setting where in each query, a random subset of individuals of size proportional to n is chosen. This makes the problem a particular example of a random constraint satisfaction problem (CSP) with a "planted" solution. We establish almost matching upper and lower bounds on the minimum number of queries m such that there is no solution other than the planted one with probability tending to 1 as n tends to infinity. Our proof relies on the computation of the exact "annealed free energy" of this model in the thermodynamic limit, which corresponds to the exponential rate of decay of the expected number of solution to this planted CSP. As a by-product of the analysis, we show an identity of independent interest relating the Gaussian integral over the space of Eulerian flows of a graph to its spanning tree polynomial.

Recommendations

• Population recovery and partial identification
• Decoding in pooling designs
• scientific article; zbMATH DE number 910893
• Optimal group testing

Cites work

• A Better Algorithm for Random k-SAT
• A Combinatorial Proof of the All Minors Matrix Tree Theorem
• A spectral approach to analysing belief propagation for 3-colouring
• A statistical-mechanics approach to large-system analysis of CDMA multiuser detectors
• Algebraic Potential Theory on Graphs
• Analyzing Walksat on random formulas
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Belief propagation on replica symmetric random factor graph models
• Compressed sensing
• Convex Analysis
• Decoding by Linear Programming
• Decoding From Pooled Data: Phase Transitions of Message Passing
• Exact matrix completion via convex optimization
• For most large underdetermined systems of linear equations the minimal 𝓁₁‐norm solution is also the sparsest solution
• Gibbs states and the set of solutions of random constraint satisfaction problems
• Group Testing With Random Pools: Optimal Two-Stage Algorithms
• Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
• scientific article; zbMATH DE number 3134390 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• Information theory. Coding theorems for discrete memoryless systems
• Information-Theoretically Optimal Compressed Sensing via Spatial Coupling and Approximate Message Passing
• On the chromatic number of random regular graphs
• On two random search problems
• Phase transitions in group testing
• Pooling designs and nonadaptive group testing. Important tools for DNA sequencing.
• Proof of the satisfiability conjecture for large k
• Quiet planting in the locked constraint satisfaction problems
• Reweighted belief propagation and quiet planting for random K-SAT
• Satisfiability threshold for random regular \textsc{nae-sat}
• Stable signal recovery from incomplete and inaccurate measurements
• The condensation phase transition in random graph coloring
• The two possible values of the chromatic number of a random graph
• Tight bounds on the threshold for permuted k-colorability
• Universality in polytope phase transitions and message passing algorithms
• Walksat Stalls Well Below Satisfiability

Cited in

(6)

• From Winner-Takes-All to Winners-Share-All: Exploiting the Information Capacity in Temporal Codes
• The committee machine: computational to statistical gaps in learning a two-layers neural network
• Optimal group testing
• Approximate message passing with rigorous guarantees for pooled data and quantitative group testing
• Noisy group testing via spatial coupling
• On a near-optimal and efficient algorithm for the sparse pooled data problem

This page was built for publication: Decoding from pooled data: sharp information-theoretic bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5025779)