Talk:Stretch factor

I think we should remove the terminology "distortion" from the article, as it is used with many different meanings, sometimes in a context more specific than ours. (For instance, assuming f is injective.)

• According to Burago et al. (2001),^{[1]: p. 249, Definition 7.1.4} the distortion of f is ${\displaystyle \operatorname {dis} f=\sup _{x,y\in X}|d(f(x),f(y))-d(x,y)|.}$ Following Verbeek & Subhash (2016),^[2] we might call this quantity the additive distortion to distinguish it from the multiplicative distortion defined below.
• According to Nayyeri & Raichel (2019),^[3] if f is injective (so that we can talk about ${\displaystyle f^{-1}:f^{\text{img}}(X)\to X}$), then the distortion of f is ${\displaystyle \operatorname {Lip} (f)\operatorname {Lip} (f^{-1}).}$ Nayyeri & Raichel interestingly use the terms expansion for ${\displaystyle \operatorname {Lip} (f)}$ and contraction for ${\displaystyle \operatorname {Lip} (f^{-1}).}$ Albiac & Kalton (2016)^[4] call the same quantity the distortion constant (rather than distortion) of f and employ the notation ${\displaystyle \operatorname {dist} (f),}$ though they also assume beforehand that ${\displaystyle f}$ and ${\displaystyle f^{-1}}$ are both Lipschitz. (They call such f Lipschitz embeddings.) Following Verbeek & Subhash (2016),^[2] we might call this quantity the multiplicative distortion to distinguish it from the additive distortion defined above. (Gromov (1983) uses the notation ${\displaystyle \operatorname {Distor} (f).}$^{[5]: p. 113})
• Given a real number ${\displaystyle 1\leq C,}$ Deza & Deza (2014)^[6] say f is C-bi-Lipschitz to mean ${\displaystyle \exists r\in \mathbb {R} _{>0}\forall x,y\in X\quad rd(x,y)\leq d(fx,fy)\leq Crd(x,y).}$ (Cf. Deza & Laurent (1997)^{[7]: Definition 10.1.1} and Indyk et al. (2017).^{[8][note 1]}) They define the distortion of f to be "the smallest C for which f is C-bi-Lipschitz." I think this definition agrees with the above definition. (I haven't checked the details, but I think we can equivalently take ${\displaystyle r=1/\operatorname {Lip} (f^{-1})}$ to show that ${\displaystyle \operatorname {Lip} (f)\operatorname {Lip} (f^{-1})}$ is such a ${\displaystyle C}$ and is smallest among such ${\displaystyle C.}$^{[note 2]})^{[note 3]}
• Sidiropoulos et al. (2019)^[9] use the term distortion precisely as the article currently does, albeit only for a special case (f having the property ${\displaystyle \forall x,y\in X\quad d(x,y)\leq d(fx,fy)}$, ${\displaystyle |X|<\aleph _{0}}$ (they only consider finite-order graphs), and ${\displaystyle Y\subseteq \mathbb {R} }$(?) (a "line")). However, given the existence of multiple other meanings of distortion (even in the context of quantitites assigned to functions between two metric spaces) and the availability of extant terminology (stretch factor, Lipschitz constant, dilation, dilatation), there is little reason why we should follow their lead.

Thatsme314 (talk) 06:49, 3 June 2022 (UTC)

References

Notes

You are mixing up references from vastly different literatures, in an unconvincing argument that people in a specific literature use this term inconsistently. As for whether it is the Lipschitz constant itself or its product with the inverse Lipschitz constant: that is a technicality used to avoid restricting to short or distance-increasing maps. If you normalized by the inverse constant (as can be done when the target space is a Euclidean space, or at least a normed vector space, as it usually is in this context) the inverse constant would then go away from the definition of this value. —David Eppstein (talk) 07:01, 3 June 2022 (UTC)

Note to self on material written by Matousek:

(2001) Embedding finite metric spaces into normed spaces (Chapter 15 in Lectures on Discrete Geometry)

(20??) Updated version of the above chapter https://kam.mff.cuni.cz/~matousek/dg-nmetr.ps.gz (sometime between 24 August 2007 and 26 December 2010, according to a search in the Wayback Machine)

(2013) Lecture Notes on Metric Embeddings https://kam.mff.cuni.cz/~matousek/ba-a4.pdf

Thatsme314 (talk) 07:10, 30 July 2022 (UTC)

We should probably merge this page with Lipschitz continuity. Thatsme314 (talk) 06:44, 3 June 2022 (UTC)

But the stretch factor notion as described here is largely applied to discrete sets of points or to geometric shapes such as curves or knots, while the Lipschitz continuity notion is largely applied to continuous functions of real numbers or other spaces where (unlike for discrete points) continuity is a meaningful concept. Although, when defined abstractly by metric spaces, they have the same definition, their areas of application and main results are largely unrelated. For that reason, it would be seriously misleading and confusing to try to merge them. How are you going to talk about geometric spanners or the Johnson–Lindenstrauss lemma in a merged version of the Lipschitz continuity article, for instance? Those are subtopics that are central here but not even on the map there. If you re-linked the discussion of stretch in the spanner or JL-lemma articles to Lipschitz continuity instead of to here, no readers of those articles would be able to make heads or tails of the link or whether it was even talking about the same concept. And if you tried to incorporate any significant content about spanners or the JL-lemma into the article on Lipschitz continuity, all the real analysts trying to read the article would think "why do we even care about finite sets? everything about them is trivial", and see it as a time-wasting distraction. —David Eppstein (talk) 06:50, 3 June 2022 (UTC)

I'm late to this discussion but Assaf Naor's ICM paper is a good example of the close relationship between the analysis and discrete math sides of this subject.

I'm agnostic about whether to merge it with Lipschitz continuity. That page is already kind of a dumping ground. But it definitely doesn't seem inconceivable to me.

—platypeanArchcow (talk) 07:31, 18 September 2022 (UTC)

I just added a note on the JL lemma in the "See also" section of the Lipschitz-continuity article. And you're wrong that all analysts would see discrete math as useless, or that readers of the JL article would not be able to understand the Lipschitz article.

• I came to the JL article because I needed it for machine-learning stuff, and I thought the bi-Lipschitz formulation was the most natural / the easiest to understand. Also, metric spaces are my go-to setting for thinking about Lipschitz functions.
• Many mathematicians, including Bela Bollobas, Timothy Gowers, and Terence Tao, are interested in analysis yet are also interested in combinatorics.
• As an example of people caring about discrete spaces in analysis, consider Kantorovich-Rubinstein duality, which for any complete, separable metric space X gives a formula for the Wasserstein distance between any two probability Borel measures on X. Wainwright, in High-Dimensional Statistics (Example 3.17), considers the case where X is countable and we put the discrete metric on X, where the Wasserstein metric coincides with total-variation distance. This example centers around discrete spaces and is still interesting -- it relates two popular metrics on probability Borel measures.

After a closer reading of the article, I agree that geometric spanners don't belong in the Lipschitz article. What bugs me now is the whole thing about S and T being distinct and this function f. I feel the concept of "stretch factor"/"distortion" might be better developed in the context of a single metric space, without any mention of a function f. In all three of the examples on geometric spanners, knot theory, and curve-shortening flows, we have S=T, we have no function f, and it seems the intrinsic metric plays an important role. It looks like your sentences about intrinsic and extrinsic distance are a rephrasing of Gromov's remarks for the case S=T and with no f (well, f=id, but in this setting f is sort of a distraction). I question the relevance of generalizing to the case where we have both S and T and an extra function f. I assume you wrote this generalization so you could talk about the JL lemma, the CNRS conjecture, and approximation algorithms. I have no background in the CNRS conjecture and next to no background in approximation algorithms, but my impression for the JL lemma is that it does not belong in this article. Even if some papers use the terminology "distortion" when talking about the JL lemma, they seem to be using it in a different sense than the papers on geometric spanners/knot theory/curve-shortening flows; the JL lemma lies much closer to Lipschitz/bi-Lipschitz continuity, and (if I'm not mistaken) it deals with the extrinsic metric, not with the intrinsic metric. Thatsme314 (talk) 11:16, 3 June 2022 (UTC)

The citation to the Johnson-Lindenstrauss lemma used to say: "The Johnson–Lindenstrauss lemma asserts that any finite metric space with n points can be embedded into a Euclidean space of dimension O(log n) with distortion 1 + ε..." This is definitely false, and the way in which it fails is a major part of the study of CAT(0) geometry. (For instance, a 4-point space with pairwise distances d(x,y) = d(y,z) = d(x,z) = 2 and d(w,x) = d(w,y) = d(w,z) = 1 cannot be embedded in any Euclidean space with distortion less than sqrt(2/sqrt(3)) (realized as the vertices and center of an equilateral triangle). I'm not an expert on that lemma, but I hope I corrected it to a true statement. Dylan Thurston (talk) 22:25, 21 July 2022 (UTC)