The Setting
Let be a vector density, that is, an integrable function, in the main argument the gradient of a real function with compact support. Averaged against the piecewise bilinear tent functions centered at the vertices of a square grid, has a direction at each vertex, a point of the unit circle. A random label, a direction taken from a fixed finite palette, is followed at a fixed point from coarse scales to fine ones: at each scale it stays put while it agrees with the directions near up to a small tolerance, and otherwise it jumps to one of them.
The question is which labels can carry mass at a point near a vertex when the directions around all lie close to the direction of mass at .
Masses and Directions on the Grid
Let be a scale. The grid point of index is the point of ✦, and the max norm of is ✦. The tent is the function on ✦, and the bilinear hat of index at scale is the function on given by (1)✦ The tent interpolation at scale of a real function on is the function on , a finite sum at each point.✦
For a vector density on , the vector mass of at a vertex is the complex number ✦, and its scalar mass there is ✦. The direction of a vector of a normed space, with fallback , is when and when .✦ The mass direction at a vertex is the direction of with fallback .✦
The grid window of radius around a vertex is the square of vertices.✦ The maximizing vertex of a real function on in is a vertex of at which attains its maximum over the window, chosen once and for all.✦ The chosen vertex of a vertex is the maximizing vertex of the scalar mass in ✦, and the chosen direction at is the mass direction at its chosen vertex, ✦. The worst vertex of is the maximizing vertex of in ✦, and the direction energy of is the largest squared disagreement between and the chosen directions near : (2)✦
Labels and Their Laws
A finite circle palette is a finite set of complex numbers of modulus one such that every point of the unit circle lies at distance less than from one of them.✦ One such palette is fixed✦, and its elements are the labels✦. The quantization of a complex number of modulus one is a label with , chosen once and for all.✦
For and real , the cone coordinate is the real-linear functional on given by , where is the real inner product of .✦ A point lies in the good sector of when and ; for this sector is the closed cone of half-angle about .✦ A label is good for a direction when lies in the good sector of , and bad for it otherwise.
A law on a finite set is a probability distribution on : a function with .✦ The point mass at is the law with for and otherwise.✦ Given an old element , a target and a chance at each vertex , the spatial transition row at scale and point is the law on that keeps with weight one minus the interpolated chance at and hands the rest to the targets of the vertices near , in proportion to their hats and chances: (3)✦
The thresholded probability of a distance at tolerance is .✦ For a vector density , the switch chance of a label at a vertex is with ✦, and the target label of is ✦. The scale transition row from a label at a point is the row (3) on with old label , targets and chances .✦ The initial label law is the row (3) with old label , targets and chance at every vertex; it gives each label the mass .✦
A sequence of radii assigns a scale to each level and descends from the coarsest level . The label marginal of at level and point is the law on given by the initial law at level and, at each later level, by moving the previous marginal through the scale transition rows: (4)✦
The Claim
Theorem 1. Let be a vector density on , let be a sequence of radii and a level with , let be a vertex with , and let satisfy . Then every label bad for has no mass in the label marginal at level : (5)✦ Likewise, at a single scale : if has and has , then every label bad for has no mass in the scale transition row from any label , (6)✦ nor in the initial label law, (7)✦
In the paper, the result reads: set ; if , and , then is good with -probability one, where the paper’s level is the page’s index , is the set of grid vertices at that level, is the label at that level and is the law of the labels at .
At the constant is , and the label at a level is good with probability one exactly when its marginal vanishes on bad labels, as in (5).
What Is Checked
The claim is stated over the vector masses, mass directions, chosen directions and direction energies (2) of a vector density on the grid of each scale, and over the initial label law, the scale transition rows and the label marginals (4), which the fixed palette, the quantization, the switch chances and the spatial transition rows (3) build from them.
The library proves that a finite circle palette exists✦, that every real function on a grid window attains its maximum there✦, and that every switch chance lies between and .