Tuesday, February 26, 2013

Sunday, February 17, 2013

Total variation


The total variation of a real valued function f on an interval I is defined as
taking the supremum over all possible partitions of I = [p0, pN]. Notably, if the function is (continuously) differentiable, the total variation becomes
but f does not have to be differentiable, and the total variation may be unbounded.

Sometimes the function itself may be evaluated at any point of the interval, although its derivative either does not exist or is far too complicated to deal with. Then the total variation may be estimated by sampling the function at several points and checking whether or not it converges to some limit as the mesh gets finer. If it doesn't, the curve may be a fractal, so its fractal dimension can be estimated from the procedure.

The length of a fractal curve is a function of the scale of measurement. As the scale of measurement ε varies, the measured length N varies according to N ~ ε −D, where D is the fractal dimension. The common procedure then is to fit a double logarithmic plot of N against ε and finding the slope. However, it would be a grave mistake to blindly accept any automatically calculated slope without checking the error of the fit.

Estimating the total variation at several arbitrary sampling resolutions can be inefficient, unless a clever trick is used. Suppose we begin with a fine resolution with uniform distance Δ = xi - xi-1 > 0 between the points. Then it is easy to obtain the total variation for subdivisions by nΔ, for n = 1, 2, … just by skipping so many points. Even better, one can take averages
so as to obtain estimates that do not depend (as much) on the particular chosen sample points.  

A somewhat related concept is arc length, which is, conceptually, the length of a string superposed on the graph of the function (assuming the function is continuous). The total variation is smaller than the arc length. For the straight line y = kx, 0 < x < t, the total variation squared is V2 = (kt)2 as compared to the arc length squared which is t2+(kt)2. Now suppose the function is monotonous over the interval under consideration. Then, if the function is deformed so as to become more curved, only the arc length will increase while the total variation remains the same. For example, if fn(x) = xn, 0 ≤ x ≤ 1 and n = 1, 2, ..., then the arc length approaches 2 as n increases, whereas the total variation remains 1.