Given a vector space and a map (linear or not), consider the displacement set of , denoted . For linear maps this is simply the range of the operator and therefore is a subspace.
The essentially nonlinear operations of taking the inverse or composition of maps become almost linear when the displacement set is considered. Specifically, if has an inverse, then , which is immediate from the definition. Also, .
When is a topological vector space, the maps for which has compact closure are of particular interest: these are compact perturbations of the identity, for which degree theory can be developed. The consideration of makes it very clear that if is an invertible compact perturbation of the identity, then is in this class as well.
It is also of interest to consider the maps for which is either bounded, or is bounded away from . Neither case can occur for linear operators, so this is essentially nonlinear analysis. In the nonlinear case, the boundedness assumption for linear operators is usually replaced by the Lipschitz condition. Let us say that is -bi-Lipschitz if for all in the domain of .
Brouwer’s fixed point theorem fails in infinite-dimensional Hilbert spaces, but it not yet clear how hard it can fail. The strongest possible counterexample would be a bi-Lipschitz automorphism of the unit ball with displacement bounded away from 0. The existence of such a map is unknown. If it does not exist, that would imply that the unit ball and the unit sphere in the Hilbert space are not bi-Lipschitz equivalent, because the unit sphere does have such an automorphism: .
Concerning the maps with bounded displacement, here is a theorem from Patrick Biermann’s thesis (Theorem 3.3.2): if is an -bi-Lipschitz map in a Hilbert space, , and has bounded displacement, then is onto. The importance of bounded displacement is illustrated by the forward shift map for which but surjectivity nonetheless fails.
It would be nice to get rid of the assumption in the preceding paragraph. I guess any bi-Lipschitz map with bounded displacement should be surjective, at least in Hilbert spaces, but possibly in general Banach spaces as well.
How to measure the nonlinearity of a function where is an interval? A natural way is to consider the smallest possible deviation from a line , that is . It turns out to be convenient to divide this by , the length of the interval . So, let . (This is similar to β-numbers of Peter Jones, except the deviation from a line is measured only in the vertical direction.)
Relation with derivatives
The definition of derivative immediately implies that if exists, then as shrinks to (that is, gets smaller while containing ). A typical construction of a nowhere differentiable continuous function is based on making bounded from below; it is enough to do this for dyadic intervals, and that can be done by adding wiggly terms like : see the blancmange curve.
The converse is false: if as shrinks to , the function may still fail to be differentiable at . The reason is that the affine approximation may have different slopes at different scales. An example is in a neighborhood of . Consider a small interval . The line with is a good approximation to because on most of the interval except for a very small part near , and on that part is very close to anyway.
Why the root of logarithm? Because has a fixed amount of change on a fixed proportion of , independently of . We need a function slower than the logarithm, so that as decreases, there is a smaller amount of change on a larger part of the interval .
Nonlinearity of Lipschitz functions
Suppose is a Lipschitz function, that is, there exists a constant such that for all . It’s easy to see that , by taking the mid-range approximation . But the sharp bound is whose proof is not as trivial. The sharpness is shown by with .
Proof. Let be the slope of the linear function that agrees with at the endpoints of . Subtracting this linear function from gives us a Lipschitz function such that and . Let . Chebyshev’s inequality gives lower bounds for the measures of the sets and : namely, and . By adding these, we find that . Since , the mid-range approximation to has error at most . Hence .
Turns out, the graph of every Lipschitz function has relatively large almost-flat pieces. That is, there are subintervals of nontrivial size where the measure of nonlinearity is much smaller than the Lipschitz constant. This result is a special (one-dimensional) case of Theorem 2.3 in Affine approximation of Lipschitz functions and nonlinear quotients by Bates, Johnson, Lindenstrauss, Preiss, and Schechtman.
Theorem AA (for “affine approximation”): For every there exists with the following property. If is an -Lipschitz function, then there exists an interval with and .
Theorem AA should not be confused with Rademacher’s theorem which says that a Lipschitz function is differentiable almost everywhere. The point here is a lower bound on the size of the interval . Differentiability does not provide that. In fact, if we knew that is smooth, or even a polynomial, the proof of Theorem AA would not become any easier.
Proof of Theorem AA
We may assume and . For let . That is, is the restricted Lipschitz constant, one that applies for distances at least . It is a decreasing function of , and .
Note that and that every value of is within of either or . Hence, the oscillation of on is at most . If , then the constant mid-range approximation on gives the desired conclusion, with . From now on .
The sequence is increasing toward , which implies for some . Pick an interval that realizes , that is and . Without loss of generality (otherwise consider ). Let be the middle half of . Since each point of is within distance of both and , it follows that for all .
So far we have pinched between two affine functions of equal slope. Let us consider their difference:
. Recall that , which gives a bound of for the difference. Approximating by the average of the two affine functions we conclude that as required.
It remains to consider the size of , about which we only know so far. Naturally, we want to take the smallest such that holds. Let be this value; then . Here and . The conclusion is that , hence . This finally yields as an acceptable choice, completing the proof of Theorem AA.
A simple closed curve on the plane can be parameterized by a homeomorphism in infinitely many ways. It is natural to look for “nice” parameterizations, like nonexpanding ones in the previous post. This time, let us look for noncontracting parameterizations: for all . Note that Euclidean distance is used here, not arclength. And we still want to be a homeomorphism. Its noncontracting property simply means that the inverse is nonexpanding aka 1-Lipschitz.
What are some necessary conditions for the existence of a noncontracting parameterization? We can mimic the three from the earlier post Nonexpanding Jordan curves, with similar proofs:
The curve must have length at least .
The curve must have diameter at least 2.
The curve must enclose some disk of radius 1. (Apply Kirszbraun’s theorem to and note that the resulting Lipschitz map G of the plane will attain 0 somewhere, by a topological degree / winding number argument. Any point where G = 0 works as the center of such a disk.)
This time, the 3rd item supersedes both 1 and 2. Yet, the condition it presents is not sufficient for the existence of a noncontracting parameterization. A counterexample is a disk with a “comb-over”:
Indeed, suppose that is a nonexpanding map from this curve onto the unit circle. Let be the three points at which the curve meets the positive x-axis. Since every point of the curve is within small distance from its arc AB, it follows that is a large subarc of that covers almost all of the circle. But the same argument applies to the arcs and , a contradiction.
No matter how large the enclosed disk is, a tight combover around it can force arbitrarily large values of the Lipschitz constant of . Sad!
What about sufficient conditions?
It is sufficient for the curve to be star-shaped with respect to the origin, in addition to enclosing the unit disk. (Equivalent statement: has a polar equation in which .) Indeed, the nearest-point projection onto a convex set is a nonexpanding map, and projecting onto the unit circle in this way gives the desired parameterization.
It is sufficient for the curve to have curvature bounded by 1. I am not going into this further, because second derivatives should not be needed to control a Lipschitz constant.
Recall that for nonexpanding parameterizations, the length of the curve was a single quantity that mostly answered the existence question (length at most 4 — yes; length greater than — no). I do not know of such a quantity for the noncontracting case.
A simple closed curve on the plane can be parameterized by a homeomorphism in infinitely many ways. It is natural to look for “nice” parameterizations: smooth ones, for example. I do not want to require smooth here, so let us try to find that is nonexpanding, that is for all . Note that Euclidean distance is used here, not arclength.
What are some necessary conditions for the existence of a nonexpanding parameterization?
The curve must have length at most , since nonexpanding maps do not increase length. But this is not sufficient: an equilateral triangle of sidelength has no nonexpanding parameterization, despite its length being .
The curve must have diameter at most 2 (which the triangle in item 1 fails). Indeed, nonexpanding maps do not increase the diameter either. However, is not sufficient either: an equilateral triangle of sidelength has no nonexpanding parameterization, despite its diameter being 2 (and length ).
The curve must be contained in some closed disk of radius 1. This is not as obvious as the previous two items. We need Kirszbraun’s theorem here: any nonexpanding map extends to a nonexpanding map , and therefore is contained in the closed disk of radius 1 centered at . (This property fails for the triangle in item 2.)
The combination of 1 and 3 (with 2 being superseded by 3) still is not sufficient. A counterexample is given by any polygon that has length but is small enough to fit in a unit disk, for example:
Indeed, since the length is exactly , a nonexpanding parametrization must have constant speed 1. But mapping a circular arc onto a line segment with speed 1 increases pairwise Euclidean distances, since we are straightening out the arc.
Since I do not see a way to refine the necessary conditions further, let us turn to the sufficient ones.
It is sufficient for to be a convex curve contained in the unit disk. Indeed, the nearest-point projection onto a convex set is a nonexpanding map, and projecting the unit circle onto the curve in this way gives the desired parameterization.
It is sufficient for the curve to have length at most 4. Indeed, in this case there exists a parameterization with . For any the length of the shorter subarc between and is at most . Therefore, the length of is at most , which implies .
Clearly, neither of two sufficient conditions is necessary for the existence of a nonexpanding parameterization. But one can consider “length is necessary, length is sufficient” a reasonable resolution of the problem: up to some constant, the length of a curve can decide the existence one way or the other.
Stay tuned for a post on noncontracting parameterizations…
Just finished writing a summary of Gromov’s Hilbert Volume in Metric Spaces, Part 1 for Zentralblatt. Not an easy task to summarize such an article, and I essentially limited myself to the introductory part. But at least I contributed a Parseval frame analogy, which is not explicit in the article. I like frames in general, and tight/Parseval frames most of all.
And since the Zentralblatt server for review submission is down at the moment, the outlet for this text defaults to my blog.
Let denote the Jacobian matrix of a differentiable map . One way to quantify the infinitesimal dilation of is to consider the operator norm . This corresponds to the local form of the Lipschitz constant , and thus makes sense in general metric spaces. Another natural, and often more convenient way to measure dilation is the Hilbert-Schmidt norm . However, the latter does not immediately generalize to metric spaces. The present article developes such a generalization and uses it to derive several known previously results in a unified and elegant way.
Instead of trying to describe the construction in full generality, let us consider the special case of Lipschitz maps , where is a metric space. Let be a measure on the set of all rank- projections, which can be identified on the -dimensional projective space. Of particular importance are the measures for which for all . Such a measure is called an axial partition of unity; a related term in harmonic analysis is a Parseval frame. The -dilation of with respect to is . In terms of frames, this definition means that one applies the analysis operator to and measures the Lipschitz constant of the output. Another approach is to use the synthesis operator: consider all Lipschitz maps from which can be synthesized and define .
For every axial partition of unity one has because the composition of analysis and synthesis recovers . Taking the infimum over all axial partitions of unity yields minimal -dilations and .
For linear maps between Euclidean spaces the minimal -dilation of either kind is exactly the Hilbert-Schmidt norm. For non-linear maps they need to be localized first, by taking restrictions to small neighborhoods of a point. The concept turns out to be useful, e.g., for proving volume comparison theorems. The author proves an elegant form of F. John’s ellipsoid theorem in terms of , recasts the Burago-Ivanov proof of the Hopf conjecture [Geom. Funct. Anal. 4, No.3, 259-269 (1994; Zbl 0808.53038)] in these new terms, and presents further extensions and applications of his approach.
In some sense (formal or informal) the following classes of maps are dual to each other.
Injective : Surjective
Immersion : Submersion
Monomorphism : Epimorphism
An isometric embedding of metric space into a metric space is a map such that for all . This concept belongs to the left column of the table above. What should be its counterpart?
Candidate 1. Observe that a 1-Lipschitz map is an isometric embedding iff it does not factor through any 1-Lipschitz surjection (for any space ) unless is an isometric isomorphism. Reversing the order of arrows, we arrive at the following concept:
A 1-Lipschitz map is a metric quotient map if it does not factor through any 1-Lipschitz injection (for any space ) unless is an isometric isomorphism.
This can be reformulated as follows: is the greatest pseudo-metric on subject to
This seems reasonable: does as little damage as possible, given the structure of its fibers. There is also a natural way to construct for any reasonable fibering of : begin by defining for points in different fibers and otherwise. Then force the triangle inequality by letting subject to and . As long as the fibers stay at positive distance from one another, this will be a metric. The corresponding metric quotient map sends each point of onto its fiber.
Here is a simple example, in which a part of an interval is mapped to a point.
However, the above example made me unhappy. The only nontrivial fiber is the interval . Both points and belong to trivial fibers, but the distance between them decreases from 3 to 2. This looks like a wrong kind of quotient to me.
Candidate 2 already appeared in my post on Lipschitz quotient, but wasn’t recognized at the time. It could be called -Lipschitz quotient, but a better name is available. A map is a submetry if where the balls are closed (using open balls yields something almost equivalent, but generally weaker). Such need not be an isometry: consider orthogonal projections in a Euclidean space. It does have to be 1-Lipschitz. The additional property that distinguishes it from general 1-Lipschitz maps is the 2-point lifting property: for every and every there is such that . Incidentally, this shows that is an isometric embedding of into the hyperspace which I covered earlier (“This ain’t like dusting crops, boy“).
The concept and the name were introduced by В.Н. Берестовский (V.N. Berestovskii) in his paper “Submetries of space-forms of nonnegative curvature” published in 1987 in Siberian Math. J. Among other things, he proved that a submetry between spheres (of any dimension) is an isometry. Of course, there are many submetries of onto other spaces: take the quotient by a subgroup of , which can be either discrete or continuous. Are there any submetries that are not quotients by isometries?
Yes, there are. I’ll describe a (modified) example given by Berestovskii and Guijarro (2000). Let be the hyperbolic plane realized as the upper half-plane with the metric . Define by
Don’t panic; this is just the signed distance function (in the metric of ) to the fat green curve below. I also drew two other level sets of , to the best of my Friday night line-drawing ability.
To convince yourself that is a submetry, first consider for which the submetry property is clear (it’s the quotient by horizontal translation), and then note that the inversion in the unit circle exchanges horizontal lines (horocycles at infinity) with horocycles at 0. An interesting feature of this submetry that it is not very smooth: but not .
The hyperspace is a set of sets equipped with a metric or at least with a topology. Given a metric space , let be the set of all nonempty closed subsets of with the Hausdorff metric: if no matter where you are in one set, you can jump into the other by traveling less than . So, the distance between letters S and U is the length of the longer green arrow.
The requirement of closedness ensures for . If is unbounded, then will be infinite for some pairs of sets, which is natural: the hyperspace contains infinitely many parallel universes which do not interact, being at infinite distance from one another.
Every continuous surjection has an inverse defined in the obvious way: . Yay ambiguous notation! The subset of that consists of the singletons is naturally identified with , so for bijective maps we recover the usual inverse.
Exercise: what conditions on guarantee that is (a) continuous; (b) Lipschitz? After the previous post it should not be surprising that
Even if is open and continuous, may be discontinuous.
If is a Lipschitz quotient, then is Lipschitz.
Proofs are not like dusting crops—they are easier.