The Setting
Let be an integrable vector density on the plane, in the application the gradient of an input function , and its total mass. Tested against the bilinear hats of a dyadic grid, has a vector mass at each scale and each vertex, and a nonzero vector mass has a direction on the unit circle. Weighted along paths of vertices by transition weights, the vector masses at the finest scale form a forest of finite trees, one rooted at each vertex of a box. The item asks how often the directions turn along this forest and what the turning costs against : the mass at the nodes where the direction has moved by more than a threshold , the energy of the local disagreement of directions, and the number of times a label taken from a finite palette of directions has to switch as particles run down the trees.
Trees, Marks and Particles
A finite branching tree with labels in a finite set and values in a normed space is either a leaf carrying a vector of or a branch with one child , again such a tree, for each label .✦ A node of is named by the finite sequence of labels that leads to it from the root, one child per label; is the length of , its prefix of length , and the sequence preceded by . A valid path of is a sequence of labels that, followed from the root, ends exactly at a leaf.✦ An active path of is a sequence of labels ending at a leaf that carries a nonzero vector.✦
The total vector of is the sum of the vectors at its leaves✦, and the terminal mass of is the sum of their norms.✦ The direction of a vector with fallback is when and when .✦ Fix a unit vector . At a node , is the total vector of the subtree hanging from , is its mass and its direction.
Fix also a real number and a reference direction . The marks of from are found from the root down: a node is a mark when (1) where is the direction of the nearest mark among the strict ancestors of , or if there is none. The mark indicator of from is the function on finite sequences of labels equal to at a sequence ending at a mark and elsewhere✦, and the first crossing cost of from is the sum of over the marks of from .✦ The intrinsic marks of are the root of , named by the empty sequence , and, in the subtree of each child, the marks from the root direction . The marked cost of is the sum of over its intrinsic marks✦, and the root mark indicator is when ends at an intrinsic mark and otherwise.✦
The node charge of under a real weight on finite sequences of labels is the sum over all nodes of .✦ The path charge of a sequence of labels from a birth level under is (2)✦
The particles of run down its valid paths, each from a birth level. The survival fraction of a branch is the proportion of its children, one for each label, that survive. Let be a real function on finite sequences of labels and a real function of a sequence and a birth level; write for the function , for and for . The root birth evaluation of is when is a leaf carrying , and (3)✦ when is a branch. The late birth evaluation of is when is a leaf, and (4)✦ when is a branch. The particle evaluation of is .✦
The Dyadic Vector Forest
The tent is the function on given by .✦ For a scale and an index , the bilinear hat is the function on given by (5)✦ The grid point of an index at scale is the complex number .✦ The vector mass and the scalar mass of at are (6) The dyadic scale of level is , level being the finest scale .✦ The box grid is the square index box of half-width , the set of with and .
At a scale , the mass direction at a vertex is , the direction of the vector mass with fallback .✦ The window of radius around is the square of the vertices with and ✦, and a maximizing vertex of a real function on in is a vertex of the window at which attains its maximum over the window, chosen once and for all.✦ The chosen vertex of maximizes the scalar mass in ✦, and the chosen direction at is .✦ The worst vertex of maximizes in ✦, and the energy of at scale is (7)✦
Fix the finest scale and a depth . The dyadic vector tree rooted at is the finite branching tree with labels in and values in whose nodes of depth less than are branches and whose leaf at a sequence carries (8)✦ where is the transition weight from to ; the trees , , form the dyadic vector forest. The last vertex of a sequence in is its last term, or when is empty✦, and the path energy of in is (9)✦
Labels and Switching
A finite circle palette is a finite set of points of the unit circle in such that every point of the circle lies at distance less than from one of them.✦ The fixed palette is one such palette chosen once and for all✦, and its points are the labels.✦
A law on a finite set is a probability distribution on , a function on with .✦ The expectation of a real function on under a law on is .✦
For a tolerance , the switch probability ramp is the function of a distance given by (10) At a scale and with , the switch chance of a label at a vertex is ✦, and the switching rate of at a point is the tent interpolation of the switch chance, (11)✦
Along a sequence of radii , the label marginal gives for each level and point a law on the labels: is the initial label law, a law on the labels attached to the scale and the point , and is the mixture, with the weights of , of the scale transition rows , the laws on the labels that the scale and the point attach to each label .✦ The switching cost, the expected chance that the label switches on passing to the next level, is (12)✦
For the forest, take . The path switch total of a sequence from a birth level at a point is (13)✦ The particle switch count of is the path switch total at the grid point of the last vertex of , .
The Claim
Theorem 1. Let be integrable with , let and , and let , , be the dyadic vector trees of depth , with directions taken with fallback . For every , (14)✦ Suppose moreover that and that vanishes outside the closed disk of radius about the origin, where . Then the mass-weighted path energies of the forest equal the mass-weighted sum of the energies of the vertices of over the scales , , (15)✦ the path switch totals satisfy, for all , all active paths of , all birth levels and all points with , (16)✦ and the particle switch counts of the forest satisfy (17)✦ Finally, let be a finite branching tree with labels in a finite set and values in a normed space , let be a unit vector and , with directions taken with fallback . Then (18)✦ and if a real number , a real weight on finite sequences of labels and a real function of a sequence and a birth level satisfy for every valid path of and every , then (19)✦
In the paper, the result reads: , and , where is the measure on the particles, a particle’s birth level, its position at level , its terminal position, the number of levels and a constant.
What Is Checked
The claim is stated over finite branching trees of vectors in a normed space, with their intrinsic marks, node and path charges and particle evaluations, and over the dyadic vector forest of an integrable density on the box grid , with the energies of its mass and chosen directions and the switching costs of the label law on the fixed palette; the energy identity and the two switch bounds of the forest assume in addition that and that vanishes outside the closed disk of radius about the origin, with . Beside the claim, the library shows that a finite circle palette exists✦ and that every real function on attains its maximum on every window .✦