The Setting
The copy hierarchy works with a finite set of nodes and a matrix of transition weights between them. The case of interest is a matrix that is nonnegative and strictly forward, each positive weight leading from a node to a larger one, so that the weighted graph on has no cycles, and whose rows sum to at most , as in a substochastic transition matrix. The exact correction builds from a correction matrix step by step, in a pilot run steered by the probed values of a detector, a score computed at every node from random affine channels, and in an actual run that reuses the last probed values.
The question is what the corrections keep of the shape of after steps, and how the actual corrections compare with the pilot ones.
Matrices and Corrections
Nodes are natural numbers, and a node set is a finite set of them.✦ A real vector is a function assigning a real number to each node , and a real matrix is a function assigning a real entry to each pair of nodes and . The product over a node set of real matrices and is the real matrix with , and the row weight of at a node over is .✦
Write for the clamp of a real number to ✦, and for the cutoff scale.✦ The threshold profile is the shoulder function with threshold and gap , the real function (1)✦ which vanishes for and equals for .
The entrywise correction at scale of a real matrix , with column weights from a real vector , is the real matrix built from the profile (1): (2)✦ For a node set , a scale , a real vector and a real matrix , the iterated correction of over is the sequence of real matrices with (3) where , with the product over , is the combined matrix of and .
For node sets and and reals and , a real matrix is a bounded support matrix with bound on , over at scale , written , when for all nodes and (4)✦
The Detector
Fix a prime and write .✦ A channel over is a pair of a nonzero vector of and a vector of ✦; its point at a residue modulo is , the point at parameter of an affine line.✦ The rate of a level is ✦, and the box of level is the set of vectors of whose four coordinates, read as integers in , are smaller than the side .✦ Given a node set , the retained vertices of a channel at level form the subset of of the nodes with .✦
For a finite set , a real function on and a natural number , the padded rank of over is (5)✦
The fade is the real function , equal to for and to for ✦, and the ramp from to is .✦ With and , the cutoff is , equal to up to and to from on✦; the light ramp is ✦, and the gate at a real is .✦
Let be a real matrix, a level and , natural numbers. The mark of an entry of at a channel is the light ramp of the scaled entry times the throttle of row , the gate at of the padded rank (5) of that row over : (6) The score of a pair of channels at a node is the padded rank (5) of the marks of column over the retained vertices of : (7) The averaged score of at a node is the mean of the score over all channels , averaged again over the channels whose point at lies in the box of level , with and uniform over the channels over : (8)✦
The Pilot Run
A stage consists of parameter constants, a level , a node set and a real matrix of transition weights✦; its rate is .✦ The parameter constants are four natural numbers: an iteration count that is admissible, which means and , a number with , a number of copies , and a number with .✦
A pilot pair is a real vector together with a real matrix .✦ Over a prime , the update of a pilot pair is the pilot pair with (9)✦ where the product is over and is the averaged score (8) at the level , with the stage’s and .
The pilot run is the sequence of pilot pairs that starts at the zero vector and the zero matrix and moves by the update: (10)✦ The probed values of the pilot run are the vectors , its pilot corrections are the matrices , and its pilot inputs are the test matrices .
The actual corrections are the iterated correction (3) of over at scale with the column weights , the cutoff of the probed values at the last step ; the matrices are the actual inputs.✦
The Claim
Theorem 1. Let be a stage with iteration count , node set , matrix and rate , and let be a prime. For steps the probed values satisfy (11)✦ Let moreover be a node set such that . Then for every step the pilot correction, the pilot input and the actual correction satisfy (12)✦ (13)✦ (14)✦ and for every step the actual correction lies below the pilot correction: (15)✦
In the paper, the result reads: all pilot and actual inputs and corrections are nonnegative and strictly forward; for their row sums are at most and their entries at most ; and ; and their row and column supports lie in and , with and standing for the paper’s and , and , and being the paper’s own symbols for the actual input and for the row and column index sets of .
What Is Checked
The claim is stated over a stage, with its parameter constants, level , rate , node set and matrix , a prime and a node set ; over the pilot run (10) with its update (9), probed values, pilot corrections and pilot inputs; over the actual corrections, the iterated correction (3) with weights ; and over the bounded support matrices (4).