The Setting
The signed walk, the sequence of signed prefix sums of a family of vectors, is constructed with a filter on real matrices. A run takes vectors in , for a finite set of state coordinates, one at a time; the filter steps of the run, defined below, act in turn on a matrix with rows indexed by , and each produces a row, its predictor row; the predictor rows of the run form the predictor matrix. The question is how much squared norm a single column of the predictor matrix can collect over a run of any length, measured against the squared norms of the vectors.
The library bounds it in two settings: for a run of symmetric steps, defined below, on any starting matrix, at the columns where that matrix vanishes, and for the predictor rows built from a finite family of vectors.
Filter Steps and Predictor Rows
For a finite set , the mass of a vector is its squared Euclidean norm (1)✦
The normalizer of a vector is the real number ✦, and its symmetric contraction is the square real matrix indexed by , where (2)✦
A filter step on real matrices with rows indexed by and columns indexed by a set is a triple of a square real matrix indexed by , a vector and a column , acting on such a matrix by (3)✦ with the standard basis vector of at . The symmetric step of into the column is the filter step .✦ A column of is fresh when it is zero, and a list of filter steps has fresh columns for when the column of each of its steps is fresh.✦
The predictor rows of a matrix along a list of filter steps, with , are the rows indexed by that the steps produce, one each, as they act in turn on : with (4)✦ the row is the predictor row of the step at .
The Family Predictor
Let be vectors in , and index columns by : the state coordinates, then one noise coordinate for each vector. The initial matrix is the real matrix with rows indexed by and columns by that is the identity on the state columns and zero on the noise columns.✦ Write . The family of symmetric steps of is the list of the symmetric steps of , in this order, the step of writing into the noise column .✦
The noise part of a row indexed by is the row that vanishes on the state coordinates and agrees with on every noise coordinate.✦ The family predictor rows of are the noise parts of the predictor rows of along the family of symmetric steps of .✦
The Claim
Theorem 1. Let be a real matrix with rows indexed by and columns by , and let be a list of symmetric steps , , that has fresh columns for , with pairwise distinct columns and with for every . Let satisfy for every . Then for every fresh column of , the predictor rows of along satisfy (5)✦
Theorem 2. Let be vectors in with for every , and let satisfy for every . Then at every coordinate , the family predictor rows of satisfy (6)✦
What Is Checked
Both claims are stated over the mass (1), the normalizer and the symmetric contraction (2), the filter steps (3), fresh columns and the predictor rows (4), and the second also over the initial matrix , the family of symmetric steps, noise parts and the family predictor rows.