The Setting
Let be a set and a finite set. The real space is the vector space of all functions from to , and a real matrix with rows indexed by and columns indexed by is given by its columns , . The norm of a point of is ✦, and the unit ball is the set of points of of norm at most ✦. The combination of the columns with coefficients is the point of given by (1)✦
As runs over , the combination runs over the absolutely convex hull of the columns; with nonnegative coefficients of sum at most it runs over the convex hull of the columns and the origin. The item is about covering in the uniform norm, by translates of the cube with centers anywhere in , once such a cover of is at hand: what the signs of the coefficients cost in the number of centers and in the accuracy.
The library states the result for every matrix and, again, for one family of matrices whose entries are graph distances on a finite set, cut off at a radius.
Approximation Lists and Codes
For a real number , two points and of are uniformly -close, , when at every point of .✦ A uniform -approximation list for is a finite set of points of that comes within of every member of : (2)✦ Its members need not lie in .
A positive list for at scale is a finite set of points of that comes within of every member of : (3)✦
The difference list of a finite set of points of is the finite set .✦ A pair code for is an ordered pair of members of , a point of ✦, and its decoding is the difference ✦.
Graph Distance Columns
Let be a finite set and, for each index in a set , let be a labeling of , a map from to a set of labels. The partition graph of the labelings, for a finite set of indices, is the simple graph on in which two distinct points and are adjacent when some index gives them the same label, .✦ The graph distance between points and of is the least number of edges on a path from to in , a value in that is when and lie in different components.✦
The cutoff profile of radius is the function on given by (4)✦
Let be a finite family of finite sets of indices. The column index set is : a column index is a pair of a point and a member of , which selects the partition graph.✦ The graph distance column at the column index is the function on given by (5)✦
The Claim
Theorem 1 (Signed compression). (a) Let be a set, a finite set, a real matrix with columns , a real number, and a positive list for at scale . Then the difference list has at most members, (6)✦ and is a uniform -approximation list for : (7)✦ The set of pair codes for has exactly members, (8)✦ and there is a map such that, for all , (9)✦
(b) Let be positive integers and a real number with and . Let be labelings of a finite set , each taking at most values, and let be a finite family of subsets of , each missing at most indices. Then, for the graph distance columns (5) indexed by , there are finite sets and of functions on such that (10)✦
In the paper, the result reads: with and , there is a list of at most functions approximating every member of to uniform error , and can be partitioned into at most nonempty clusters on each of which , where bounds the size of the positive list .
The paper’s clusters are the nonempty fibers of the map in (9), a map into the pair codes of (8).
What Is Checked
The claim is stated over the combinations of the columns of a matrix with coefficients in the unit ball, uniform closeness, approximation lists, positive lists, the difference list and the pair codes with their decoding, and, in part (b), over the graph distance columns (5) on the column index set , built from the partition graphs , their distances and the cutoff profile .