The Setting
Take a set and a matrix whose columns , , are real functions on , with finite. For , a function from to , the combination is a mixture of the columns when for every and . The mixtures fill the convex hull of and the columns in , and the question is how many translates of the cube , with and , it takes to cover .
A set of real functions on is a positive compression of at accuracy when every mixture is uniformly within of some : (1)✦ A finite positive compression is the set of centers of a covering of by translates of .
In this item the columns are profiles of distances in graphs built from partitions of , and the compression is the set of functions decoded from a finite set of codes.
Partition Graphs and Their Profiles
For a natural number , . Let be a positive integer and labelings of , that is, maps from to sets of labels, each splitting into the classes of points that share a label. The partition graph of the labelings, for a set of indices, is the simple graph on in which two distinct points and are adjacent when for some .✦ The graph distance is the least number of edges on a path from to in , and when the two points lie in different components.✦ The closed graph ball of radius about a point of is the set of points with ✦; its indicator function is ✦.
The cutoff profile of radius is the real function on distances given by (2)✦
For a family of subsets of , the column index set is ✦, and the graph distance column at in is the real function on (3)✦ For a finite set , centers , index sets and weights , the profile mixture is the real function on (4)✦
Codes and the Compression List
Fix and positive integers and . For a positive integer , a fixed label encoding of the labelings with codes is a choice of maps and , one pair for each , such that for all , exactly when , and .✦
The rounding mesh is ✦ and the weight code size is ✦; a weight code decodes to the weight ✦. A compression code is a triple of an index , a label code for each level and slot , and a weight code for each level, slot and subset of .✦ With the family of subsets of , the compression codes form the finite set (5)✦
The decoder of sends a compression code , with pivots , to the real function on (6)✦ where is the log increment of radius . The compression list of is the image of the decoder, the finite set of the functions for .✦
With the number of pivot slots , the encoding cost is (7)✦
The Claim
Theorem 1 (Uniform compression). Let be positive integers, , and labelings of a set .
Suppose that is finite, that each takes at most values, that and , and that is a family of subsets of with . Then some nonempty finite set of real functions on is a positive compression at accuracy of the columns (3), and (8)✦
Under the conditions of (a) on , , , and , let be a fixed label encoding with codes. Every with and has some with (9)✦
Suppose only that and , and let be a fixed label encoding with codes. Let be a finite set, centers, index sets with , and weights with . Then some code satisfies (10)✦
Every fixed label encoding with codes satisfies (11)✦
If , every nonempty finite set with satisfies (12)✦
In the paper, the result reads: if is finite and nonempty, , , is nonempty and satisfies the paper’s condition (3.1), with , and , then there is a list of real functions on such that every nonnegative combination of the columns of total mass at most one, the paper’s class , has some with pointwise, so that , and with .
Parts (b), (d) and (e), with , give the one-sided bounds and the bound on for the single list of a fixed label encoding.
What Is Checked
The theorem is stated over the partition graphs of the labelings with their distances and graph balls, the cutoff profile and its log increments , the columns on and the profile mixtures , positive compression at accuracy , fixed label encodings, the compression codes with their rounding mesh and weight codes, the decoder with its image , and the encoding cost .