Fundamental Limits on Data Acquisition: Trade-offs between Sample Complexity and Query Difficulty
share
In this paper, we consider query-based data acquisition and the corresponding information recovery problem, where the goal is to recover k binary variables (information bits) from parity measurements of some subsets of those variables. The queries and the corresponding parity measurements are designed by the encoding rule of Fountain codes. By using Fountain codes, we can design potentially limitless queries and the corresponding parity measurements, and guarantee that the original k information bits can be recovered from any set of measurements of size n larger than some threshold. In the query design, the average number of information bits involved in the calculation of one parity measurement is called query difficulty (d̅) and the minimum number of measurements required to recover the k information bits is called sample complexity (n). We analyze the fundamental trade-offs between the query difficulty and the sample complexity, and show that the sample complexity of n=c{k,(k k)/d̅} for some constant c>0 is necessary and sufficient to recover k information bits with high probability as k→∞.
READ FULL TEXT