The Setting
This item belongs to the exact correction and copy hierarchy of Section 4, a sequence of stages indexed by a level . At level the walk of interest is substochastic and only moves forward, from a vertex to a larger one, as a clocked randomized machine does on its configuration graph; its vertices form a finite set of natural numbers, and no single transition weight exceeds the rate .
From probed values at its vertices, a stage builds a correction and with it a residual matrix . It passes to level by splitting each vertex into copies, where is one of the stage’s parameter constants, and spreading the weight of each entry of over copies of its endpoints, in amounts set by the probed values and by the size of the entry against the rate. This single step is the copy stage of a walk at level of the shape above, and the residual is seen on the copies through a weighted projection.
Stages and Their Residuals
Vertices are natural numbers, and a finite domain is a finite set of them.✦ A real vector assigns a real number to each natural number✦, and a matrix of reals assigns one to each pair of natural numbers.✦ Over a finite domain , for matrices of reals and and a real vector , the product of the two matrices and the product of a matrix with a vector are (1) and the row weight of at over is .✦
A stochastic step matrix on a finite domain at rate is a matrix of reals such that, for all natural numbers and , (2)✦ we write for the set of them. More generally, for finite domains and , a rate and a real number , a bounded support matrix is a matrix of reals with entries in , row weights over at most , and positive entries only for in ; the stochastic step matrices are the bounded support matrices with and .✦
A stage consists of parameter constants, a level , a finite domain of vertices and a matrix of reals of transition weights✦; its rate is , the retention rate of level .✦ An iteration count is admissible when it is positive and ✦, where is the cutoff scale.✦ The parameter constants are natural numbers , , and , with admissible and (3)✦ where ✦ and ✦.
A stage is considered at a field size , a prime, the modulus of the group on which the channels of the hierarchy act. A pilot pair is a pair of a real vector , the probed values, and a matrix of reals , the correction.✦ The update map of a stage is the map from pilot pairs to pilot pairs that gives, from the probed values and the correction of one round, those of the next. The pilot sequence of at field size is the sequence of pilot pairs that starts from the zero vector and the zero matrix, each later term being the image of the one before under the update map of ; the probed vector of after rounds is the vector of the term of index of the pilot sequence.
The clamp of a real number to is ✦, and the smooth fade is the real function (4)✦ a continuously differentiable ramp that vanishes for and equals for . The smooth rising ramp from to is ; for it vanishes up to and equals from on.✦ The cutoff , the boost and the slice are the functions (5)
The entrywise correction at scale with weights is the operation on matrices of reals that replaces each entry of a matrix by a value determined by that entry, the scale and the weights . For a finite domain , a scale , a real vector and a matrix of reals , the corrected iteration is the sequence of matrices of reals with and obtained from the combined matrix by the entrywise correction at scale with weights .✦ The stage correction matrix of a stage is the term of index of the corrected iteration for the domain , the scale , the matrix and the weights of , and the corrected residual of is (6) the products taken over .
The Copy Stage
Let be a stage at field size , with level , domain , matrix , rate and constants and . The copies of a vertex are the numbers with , the copy with being its primary copy✦, and the copy domain of is (7)✦ The boost factor of copy of is on the primary copy and for .✦ The share of copy at a real number is
The copy matrix of the stage is the matrix of reals with (9)✦ and the copy stage has the same constants, level , domain and matrix .✦ The weighted projection takes a real vector to the real vector (10)✦
The active set of the stage is the set of vertices whose probed value exceeds .✦ The node set of a matrix of reals on a finite domain is the set of vertices with or for some .✦
The Claim
Theorem 1. Let be a stage at field size , with level , domain , matrix , rate and constants and , and let , , and be its corrected residual, copy domain, copy matrix and weighted projection. Suppose that is a stochastic step matrix on at rate . Then (11)✦ and every entry of satisfies (12)✦ For natural numbers , and with , the vertex satisfies (13)✦ If moreover , then (14)✦ and (15)✦ For every real vector , with the product by taken over and the product by over , (16)✦
In the paper, the result reads: for and the paper’s , the copy matrix is strictly forward and substochastic, , , and for the weighted projection , where , , and stand for the paper’s , , and , the copy for its , and , and are the paper’s constants.
What Is Checked
The claim is stated over a stage at field size with its parameter constants, the stochastic step matrices (2) at the rates and , the probed vector of the pilot sequence, the corrected residual (6) with its correction , the copy domain (7), the copy matrix (9) with its boost factors and shares, the weighted projection (10), the active set and the node sets.