Feeds:
Posts

## How to calculate Besov parameters on graphs

Suppose $G=(V,E)$ is a graph with lengths on edges and suppose $f:V->R$ is a function and we want to calculate the Besov norm.  Suppose known at each $x\in V$ the smoothness modulus $\omega(f,x,t)$ for say $t<1$ and all the edge lengths are at most 1.  Then we have to perform an integration between 0 and 1 of parameters $(s,p,q)$ and for convenience let’s work with $p=q=1$.  We want the best $s$ we can obtain for which the Besov norm is finite.  So the computational task is to compute these norms for fixed $s>0$.

While it is possible to define Besov spaces using the traditional definition using modulus of smothness and an integral so that the three parameters (s,p,q) defermine the Besov norm it is quite worthwhile to abandon the formal procedure if necessary and ask the fudnamental questions of what smoothness or roughness will mean on a graph in the first place and whether this formal procedure has any chance of representing something deeper than a formal hack.  In other words, taking our cue from a planar domain in R^2 and a grid graph covering it, we see that for the lattice situation, smoothness defined analogously to that on the domain does make sense.  At the same time when we consider even planar finite graphs, where the edges have the induced Lebesgue measure, a second factor comes in, which is the congestion of the graph, and for functions defined by the procedure of assigning values to vertices and interpolating on edges gives a different set of possibilities than the evenly spaced grid situation.

So if F is a function defined on a planar domain, suppose only measurable, and G=(V,E) is isometrically embedded in the domain, and we take restriction of F to the vertices, then only some parts of F containing the graph will matter obviously, and if the graph is congested in one part of the domain and sparse in another, then even highly unsmooth functions will be smoother in the sparse ares and unsmooth in the congested areas.  So the definition of smoothness classes for functions should definitely include the edge lengths in the denominator of whatever norm we assign for smoothness.  So derivative defined by a procedure such as Df(n1,n2) = (1/len(n1,n2))*[F(n1)-F(n2)] takes this into account somewhat since smaller lengths produce bigger derivatives.

Besov spaces are more refined local measures meant for functions on a continuous domain.  Instead of simply carrying forward the standard definition of Besov here we should consider some different measures as follows.  Let R>0 and let’s try to define the function space F^1(G,R,s,p,q) in terms of behavior of functions in the R-balls around each node as taking a derivative now a function of edges and take some integral mimicking the Besov norm exponent placements but with the derivative function.

This gives us a measure of smoothness at the level we care about, that of higher congestion rather than being local.  This approach has the benefit of fitting the intuition of smoothness from computer graphics where smoothness to the eye is determined by congestion rather than by local considerations.  This also jibes generally with the statistical physics idea of macroscop observables being smooth when the microscopic particles can exhibit discontinuities and sharp spikes as in ideal gas.

The smoothness measure must have some adaptation to this issue for otherwise on a finite graph it is always possible to get finite values for all norms anyway without matching our expectations.