Tighter Bounds for Random Projections of Manifolds

Kenneth L. Clarkson^{∗}

July 22, 2008

Abstract

The Johnson-Lindenstrauss random projection lemma gives a simple way to reduce the dimensionality of a set of points while approximately preserving their pairwise distances. The most direct application of the lemma applies to a finite set of points, but recent work has extended the technique to affine subspaces, curves, and general smooth manifolds. Here the case of random projection of smooth manifolds is considered, and a previous analysis is sharpened, reducing the dependence on such properties as the manifold’s maximum curvature.

1 Introduction

The difficulty of dealing with high-dimensional data is a problem of long standing and continuing effort. One approach to it is to reduce the dimension: to map the original dataset in high dimension to another dataset in lower dimension, while preserving important properties as much as possible. While the singular value decomposition (SVD) gives such a mapping, and is optimal in some ways, an alternative approach simply rotates the data randomly, and then drops all but a small number of coordinates. Equivalently, it picks a random subspace of a given appropriate dimension, and projects the data to that subspace. Surprisingly, this approach can work well: as shown by Johnson and Lindenstrauss [JL84], it approximately preserves the distances between all pairs of points, with high probability. Its simplicity, and its obliviousness in some respects to the original data, allow it to be used in settings where the SVD is not appropriate.

An active area of research in recent years has been to extend this approach in various ways: finding similar transformations that also work well, finding additional properties that are preserved by random projection [Mag02], finding faster methods of implementing it [AC06], and determining the most general conditions on the dataset under which it can be applied.

∗IBM Almaden Research Center, San Jose, CA.

This paper is a contribution to the latter line of work. Results for random projections were first proved for a single vector and so immediately for finite sets of vectors; recently affine subspaces [Sar06], sets with bounded doubling dimension [IN07], and curves and surfaces[AHPY07, BW06] have been considered. Here the results for curves and surfaces are extended, by giving somewhat weaker conditions under which the random projection technique can be applied.

These results give insight into a related question: what could we regard as the “complexity” of a geometric data set? While the (intrinsic) dimension of the set is a crucial property, including for algorithms, it is inadequate for telling the difference between a circle C and a curve C′ that is approximately spacefilling. We know heuristically that solving algorithmic problems for points that are samples of C should be easier than for samples of C′, but why? This paper continues work that gives a partial but quantitative answer: in the analysis here, a dimension that is large enough for a random projection to preserve preserve distances among points of C is smaller than that needed for C′.

The remainder of this introduction will introduce the topic in more technical detail, describe some previous work, and outline the results and give some pointers to the rest of the paper.

We are interested in linear mappings from IR^{m} to its linear subspaces of some smaller dimension k. In particular, the maps will be chosen at random from a distribution constructed as follows: pick a random k-dimensional subspace F of IR^{m}, uniform under Haar measure. Call the orthogonal projection onto F, scaled by \sqrt{m/k}, a k-map for short. An equivalent k-map construction is: pick a random rotation of IR^{m}, apply it, project to IR^{k}, and then scale by \sqrt{m/k}. (The scaling by \sqrt{m/k} serves to make the expected length of the projection of a vector equal to its length.)

For S ⊂ IR^{m}, say that the linear map P : IR^{m} → IR^{k} is an ϵ-isometry on S, or ϵ-isometrizes S, if for all x ∈ S,

(1 − ϵ)∥x∥ ≤ ∥Px∥ ≤ (1 + ϵ)∥x∥.

Here, and throughout the paper, ∥x∥ is the Euclidean norm of x. (The p-norm for p ≠ 2 will have the explicitly subscripted form ∥x∥_{p}.)

Note that if P ϵ-isometrizes point {x}, it also ϵ-isometrizes any scalar multiple of x, since P is linear. So we might assume for example that points of S have unit norm: if we define U(S) := {x/∥x∥ | x ∈ S, x ≠ 0}, a subset of the unit sphere 𝕊^{m−1}, then P ϵ-isometrizes S if and only if it ϵ-isometrizes U(S).

Say that P ϵ-embeds S if for all a, b ∈ S,

(1 − ϵ)∥a − b∥ ≤ ∥Pa − Pb∥ ≤ (1 + ϵ)∥a − b∥.

Comparing these definitions, and using the linearity of P, clearly P ϵ-embeds S if and only if it ϵ-isometrizes U(S − S), where for A, B ⊂ IR^{m}, the Minkowski difference A − B := {x − y | x ∈ A, y ∈ B}. The vectors of S − S will be called the chords of S.

Johnson and Lindenstrauss showed that for large enough k, for a single point x, a k-map is an ϵ-isometry of {x}, with high probability.

Lemma 1.1. (single-point JL, [JL84]) There is a constant c_{JL} so that for a given x ∈ IR^{m} and ϵ, δ > 0, with probability at least 1−δ a (c_{JL}log(1/δ)/ϵ^{2})-map ϵ-isometrizes {x}. Put another way, with failure probability at most

exp(−kϵ^{2}/c_{JL}),

a k-map ϵ-isometrizes {x}.

By the union bound, for sets S with more than one element, the failure probability for a k-map can simply be multiplied by the size |S| of the set. Applying this to obtain an ϵ-isometry for S, and to U(S−S) to imply embedding of S, the following is obtained.

Lemma 1.2. (finite-set JL, [JL84]) There is a constant c_{JL} so that for a given S ⊂ IR^{m} of n points and ϵ, δ > 0, with probability at least 1−δ a (c_{JL}log(n/δ)/ϵ^{2})- map ϵ-isometrizes S. Put another way, with a probability of failure bounded by n exp(−kϵ^{2}/c_{JL}), a k-map ϵ-isometrizes S. Similarly, with probability at least 1 − δ, a k-map with k = c_{JL}log(n^{2}/δ)/ϵ^{2} ϵ-embeds S, or equivalently, with a probability of failure bounded by n^{2} exp(−kϵ^{2}/c_{JL}), a k-map ϵ-embeds S.

Random projection as in the JL Lemma has found many applications, as surveyed by [Vem04, Lin02, Ind00, IM04]. It can be even extended beyond a finite number of points: as shown by Sarlós [Sar06], for example, a d-flat can be ϵ-embedded by an O(d/ϵ^{2})-map. (See [Sar06] also for previous and related results for embedding flats. A d-flat is a d-dimensional affine subspace, so a 1-flat is a line and an (m − 1)-flat in IR^{m} is a hyperplane.)

Theorem 1.3. (subspace JL, [Sar06]) There is a constant c_{JLs} so that for a given d-flat F ⊂ IR^{m} and ϵ, δ > 0, with probability at least 1 − δ a (c_{JL}(c_{JLs}d + log(1/δ))/ϵ^{2})-map ϵ-embeds F. Put another way, with a probability of failure bounded by exp(c_{JLs}d − kϵ^{2}/c_{JL}), a k-map ϵ-embeds F.

Proof. (Sketch) It is shown that F is ϵ-isometrized if all the points in an ϵ_{0}- cover of the unit ball of F are ϵ-isometrized, for a small enough constant ϵ_{0}. The number of points in such a cover is 1/ϵ_{0}^{d} = exp(c_{JLs}d). Since U(F − F) ⊂ F, an ϵ-isometry of F is also an ϵ-embedding. □

For any of these lemmas, call the value that is the failure probability upper bound for ϵ-isometry, times exp(kϵ^{2}/c_{JL}), the failure multiplier, so that the failure multiplier for a single point is one, for a finite set is n, and for a d-dimensional linear subspace is exp(c_{JLs}d).

Random projection results have been extended even beyond linear subspaces. Indyk and Naor showed [IN07] that S ⊂ IR^{m} with bounded doubling dimension, or more generally with bounded E[sup {x · y | x ∈ S, y ∼ N(0, 1)}], can be isometrized, or additively embedded, where the latter means that distance errors can bounded by an additive term. A key idea is to use finite ϵ-nets of S, as discussed in Section 2 on page 8, to approximate the points of S, and extend isometry and additive embedding results for those ϵ-nets to all of S.

A difficulty in extending results from additive embedding to relative embedding, in the general setting of bounded doubling dimension, is accounting for the embedding of “short” chords, vectors a − b for a, b ∈ S that are very close together. When S is smooth, however, short chords converge to tangent vectors, and it is possible to express the embedding complexity of short chords in terms of the overall complexity of the collection of tangent vectors. One measure of this complexity is the total absolute curvature of S, denoted here by μ_{III}(S). As discussed in §4.2 on page 18, the tangent vectors can be well-approximated by a set of cardinality O(μ_{III}(M)/ϵ^{d}); in §4.3, the properties needed to define the threshold τ(M, ϵ) of shortness are given, that is, the threshold at which chords are short enough that they are adequately approximated by the manifold’s tangent vectors.

One prior result involving μ_{III}, for the case of curves, is that of Agarwal et al. [AHPY07], who showed ϵ-isometry results for a k-map to a projection dimension that is proportional to the logarithm of curve total curvature. They also showed that manifolds that are contained in low-dimensional flats can be embedded, and that curves and sets with bounded doubling dimension can be embedded additively. The proof by Agarwal et al. of their Theorem 4.1 uses in part the ϵ-net approach of Indyk and Naor. Lemma 3.1 on page 14 in turn follows their proof, and extends it slightly in a few ways; for example, it is observed that the proof requires only a bounded box dimension of the associated metric space, and not the stronger condition of bounded doubling dimension.

The work most directly antecedent to this paper is that of Baraniuk and Wakin, who showed [BW06] that a smooth manifold M can be embedded by random projections, with a projection dimension that is O(ϵ^{−2}(d log(1/ϵ) + log(1/δ))) as ϵ → 0, with lower-order terms that depend on the manifold. In addition to the parameters ϵ and δ as above, their results depend on the ambient dimension m, and on several properties of the manifold: its (d-dimensional) surface area μ_{I}(M), its reach ρ (defined in §4.3.1 on page 19), and some quantities that can be bounded in terms of the reach: the maximum curvature, the tangent space “twisting,” the relation of the Euclidean distance between points of M to their geodesic distance, and the geodesic covering regularity. (For the precise definitions of these terms, please see [BW06]; they refer to 1/ρ as the condition number of the manifold.)

Their main result, in the notation here, is the following.

Theorem 1.4. (manifold JL, [BW06]) Let M be a compact d-submanifold of IR^{m} having d-volume μ_{I}(M), reach ρ, and geodesic covering regularity R. Then a k-map ϵ-embeds M with probability at least 1 − δ, where

k = O(L(d, ϵ, δ)) + O(ϵ^{−2}(d log(mRμ_{I}(M)/ρ)))

as ϵ → 0, where L(d, ϵ, δ) := ϵ^{−2}(d log(1/ϵ) + log(1/δ)).

The term L(d, ϵ, δ) is separated out for emphasis as the leading term. The geodesic covering regularity R in the lemma statement is motivated by considerations that led here to the use of the quantity ψ(M, ϵ), as discussed in §2.4 on page 12 and below.

This work is an attempt to tighten this result; for example, the dependence on the ambient dimension m is removed entirely. More generally, this work reduces the dependence on worst-case properties, and puts the bounds more in terms of average properties: the dependence on the maximum curvature (implicitly bounded above by 1/ρ), for example, is (partly) replaced by a dependence on the total absolute curvature. For connected manifolds, the dependence on reach and maximum curvature is generally replaced by a dependence on lowtorsion connectivity as discussed in §4.3.1 on page 19. Also, improved bounds are given for the setting where only the preservation of geodesic distances is needed.

Another motivation is to continue the study of the complexity of a d-dimensional manifold M as a function of its d-dimensional measure (surface area), its total absolute curvature, and other integral curvature measures. The surface area, denoted here by μ_{I}(M), together with the dimension d, has been seen to bound several quantities: the expected total length of an extremal graph of random points on M; the size of ϵ-nets for M with respect to geodesic distance; the expected error of vector quantization; and the expected number of intersections of M with a random line. The total absolute curvature, denoted here by μ_{III}(M), has a well-known relation to the expected number of maxima, minima, and saddle points of M with respect to a random orientation (height function), as well as a fundamental relation to topological invariants of M.

The relevance of total absolute curvature to random projection bounds has already been mentioned; another integral measure of M of interest is the total root curvature of M, denoted μ_{II}(M), which essentially determines the difficulty of approximating M by a simplicial mesh. This was shown by Gruber for the case where M is the boundary of a convex set [Gru93], and for more general manifolds of codimension one in [Cla06]. (Recall that the codimension here is m − d.) Similar approximation relations are discussed in this paper, but the approximation is by tangent flats, and not by simplices, and in only one direction: M is approximated by a collection of flats, a subset of its tangent flats, in the sense that for each point of M, there is a nearby point on a flat in the collection. This kind of approximation is called here a generalized cover, or just cover for short.) (Here the “tangent flat” at a ∈ M is a + T_{a}, the tangent subspace of M at a, translated to contain a.) The metric D_{II} is discussed in detail in §2.3 on page 10. A cover by flats can have considerably fewer members than a cover by a set of discrete points.

Moreover, consider the long chords a − b in U(M − M), those due to points a, b ∈ M that are far apart. A cover of M by flats can be used to build a cover for the long chords, as shown in Lemma 4.1 on page 17. The number of flats needed is no more than proportional to (μ_{II}(M)/ϵ^{d})^{2}, to approximate within distance ϵ; with this dependency, and the above dependence on μ_{III} for handling short chords, a bound is given here on the projection dimension k sufficient for ϵ-embedding a smooth compact connected manifold; this is stated in the theorems below. A rough version of the new bound uses the quantity τ(M, ϵ), which is a threshold for shortness: it is the largest Euclidean distance τ so that any a, b ∈ M with ∥a−b∥ ≤ τ are connected by either a low-curvature or a low-torsion path. The latter condition is motivated by Lemma 4.8 on page 21: the pairs a, b ∈ M that are connected by such paths can be adequately approximated by tangent vectors.

The rough version of the new bound is as follows.

Theorem 1.5. A connected, compact, orientable, differentiable manifold M is ϵ-embedded with probability at least 1 − δ by a k-map with

k = O(L(d, ϵ, δ)) + O(ϵ^{−2}(log(μ_{II}/τ^{d} + μ_{III})))

as ϵ → 0, with an asymptotic threshold depending on M, omitting dependencies of μ_{X}(M, ϵ) and τ(M, ϵ) on M and ϵ. Here as before

L(d, ϵ, δ) := ϵ^{−2}(d log(1/ϵ) + log(1/δ)).

Analogous statements hold with “I” replacing “II” in the above.

The condition of orientability can be removed, by appealing to a double cover, and the differentiable (C^{∞}) condition is stronger than strictly necessary: it is enough to be C^{k} for large enough k. Also, M may have a boundary, but the constants here, and in the main theorem below, will then depend on the complexity of the boundary.

For comparison: the added term in the prior bound Theorem 1.4 on page 4 is

O(ϵ^{−2}(d log(mRμ_{I}(M)/ρ)).

The “roughness” of this theorem is that the asymptotic threshold depends on M. This can hide complexity; moreover, with this dependence, the same statement could be made, but omitting the lower-order term in the bound: with that omission, the unstated asymptotic threshold be different, but that is the only difference. To make the lower-order term meaningful, therefore, we need to be more precise, which unfortunately means more complicated, with the definition of a few more technical quantities:

• The value ω(M) is a threshold for the curvature-based distance D_{II}, related to μ_{II}(M): when D_{II}(a, b) ≤ ω(M), then min_{y∈a+T_{a}}∥b − y∥ ≤ βD_{II}(a, b)^{2} for some constant β > 0 (§2.3 on page 10). The analogous threshold for D_{I}, such that D_{E}(a, b) = ∥a − b∥ ≤ D_{I}(a, b), is not needed, since the inequality always holds;

• The values ψ_{X}(M, ϵ), for X ∈ {I, II, III}, which are O(1) as ϵ → 0, relate the size C_{X}(M, ϵ) of an ϵ-net in the metric D_{X} to an asymptotic expression μ_{X}(M)/ϵ^{d} for that C_{X}(M, ϵ) (§2.4 on page 12).

With these quantities defined, it is possible to state the bounds using absolute asymptotic constants: that is, the threshold and constant factor of the asymptotic O() notation are absolute constants, and so in particular are independent of M.

Theorem 1.6. A connected, compact, orientable, differentiable manifold M is ϵ-embedded with probability at least 1 − δ by a k-map with

k = O(L(d, ϵ, δ)) + O(ϵ^{−2}(log(μ_{II}ψ_{II}^{d}(1/τ^{d} + 1/ω^{d}) + μ_{III}ψ_{III}^{d})))

as ϵ → 0, with absolute asymptotic constants, under the assumption that ψ_{X}(M, ϵ) is increasing in ϵ for X ∈ {II, III}. The dependence of some quantities on M and ϵ is omitted for brevity. Here as before

L(d, ϵ, δ) := ϵ^{−2}(d log(1/ϵ) + log(1/δ)).

If τ is not needed, that is, τ(M, ϵ) = diam(M), then the term depending on μ_{II}(M) is not needed. If only geodesic distances on M need be approximately preserved, a k-map with

k = O(ϵ^{−2}(log(1/δ) + log(μ_{II}ψ_{II}^{d}(1/τ^{d} + 1/ω^{d}) + μ_{III}ψ_{III}^{d}/ϵ^{d}))

suffices. Analogous statements hold with “I” replacing “II” in the above, where ω(M) can be omitted.

This theorem is proved in §4.4 on page 22; it implies Theorem 1.5 on the previous page. As mentioned, a key lemma is that the existence of families of small generalized ϵ-covers (as defined in Section 2 on the following page) implies ϵ-isometry results for k-mappings. Section 2 also discusses the measures μ_{X}, for X ∈ {I, II, III}, and the associated distance metrics D_{X}. The ϵ-isometry results can be applied to U(M−M), and as mentioned, the short-enough chords can be approximated by tangent vectors. (As a reminder: the short/long distinction comes from the length of vector in M − M, before it is normalized to be in U(M − M).) The long chords can be handled more directly: Lemma 4.1 on page 17 says that for an ϵ-cover N of M, the set U(N − N) is an ϵ-cover of long chords of U(M − M). As mentioned, in §4.3, the properties needed to show that the threshold τ(M, ϵ) can be useful are discussed.

While the use of μ_{II} gives the strongest results, it may seem unnatural. This is particularly so when it is extended to submanifolds of dimension or codimension not equal to one; then the corresponding metric D_{II} is not Riemannian in general (as defined here; see §2.3 on page 10). If μ_{II} is not palatable, the similar, but weaker result can be obtained using μ_{I}(M), and analogous related quantities, instead of μ_{II}(M). (This possibility may also be more general, as discussed in Section 5 on page 23.)

There are at least a few simple examples where the results here improve on Baraniuk and Wakin [BW06], beyond the removal of m from the bounds. For example, for a cylinder M of some given radius and length, their bound involves the length, since that quantity figures in the volume μ_{I}(M). (We assume that the “caps” of the cylinder are closed off in a reasonable way.) The results here, in contrast, give a bound that is independent of the length; the bounds use the existence of a good approximation for M involving tangent flats that are close to M over a long distance; the analog for simplices would be approximation by very long and skinny simplices. This also shows why using μ_{II} in the main theorem is stronger than using μ_{I}. (This example involves a slight falsehood: the bound is dependent on an arbitrarily small, but fixed, multiple of the length, as implied by the perturbation discussed in §2.3 on page 10.) For a manifold that is the graph of a quadratic function, the results here show that a sufficient projection dimension depends only on the total absolute curvature μ_{III}(M), and not on the surface area of M, in contrast to prior work.

Some recent work using Baraniuk and Wakin’s bound [BW06] for learning tasks relating to manifolds is correspondingly improved by the results here [HWB07].

As observed by Baraniuk and Wakin [BW06], various properties of a manifold are also preserved approximately if its pairwise Euclidean and geodesic distances are preserved: its dimension, topology, local neighborhoods, local angles, path curvatures, and surface area, for example.

A different direction of generalization of the JL Lemma is to show similar embedding results for mappings that are not projections to a random linear subspace, for example, the mapping that is multiplication by a d × m matrix of i.i.d. normal random variables. (Such variations are reviewed by Sarlós [Sar06], for example.) Since the theorem above ultimately relies only on embedding results for families of finite sets of points, and on the linearity of the embeddings, analogous results can be proved for those variant embedding techniques.

1.1 Approximation

For values x and y, and β > 0, let x ≤_{β} y denote the condition x ≤ (1 + β)y, and let x ≈_{β} y indicate that x ≤_{β} y and y ≤_{β} x both hold. When x ≤_{β} y ≤_{β} z, for some value z, it follows that x ≤ (1 + β)^{2}z, and thus x ≤_{3β} z for β < 1. So a version of the relation holds transitively, up to a constant factor. The β subscript may be sometimes dropped from ≈_{β}, and such book-keeping understood.

2 Covers and Manifold Metrics

Some basic facts about metric spaces, ϵ-covers, ϵ-packings, ϵ-nets, and associated measures will be needed. Given a metric space (𝕌, D) and a subset S ⊂ 𝕌, recall that an ϵ-cover of S is a subset C ⊂ 𝕌 such that for any point a ∈ S, there is some a′ ∈ C with D(a, a′) ≤ ϵ. Let C(S, D, ϵ) denote the minimum size of of an ϵ-cover for S. An ϵ-packing is a subset N ⊂ 𝕌 such that no two points a′, a′′ ∈ N have D(a′, a′′) < ϵ. An ϵ-net for S is both an ϵ-cover and an ϵpacking. It is a nearly optimal ϵ-cover, in the sense that if the size of an ϵ-net is no larger than the size of any (ϵ/2)-cover. The space (S, D) has box dimension d when C(S, D, ϵ) = 1/ϵ^{d+o(1)} as ϵ → 0, and the Hausdorff measure associated with D is approximately C(S, D, ϵ)/ϵ^{d}, as ϵ → 0, as discussed further in §2.4 on page 12.

It will be helpful to generalize the concept of an ϵ-cover from sets of points to sets of regions: that is, a generalized ϵ-cover of S is here a collection of subsets N := {F | F ⊂ 𝕌} such that for any a ∈ S, there is a′ ∈ F ∈ N such that D(a, a′) ≤ ϵ. Given a collection N of subsets of IR^{m}, let N − N := {F − F′ | F, F′ ∈ N}, where as before F −F′ := {x − x′ | x ∈ F, x′ ∈ F′}. Also for N a collection of subsets, let U(N) := {U(F) | F ∈ N}.

As sketched above, two such generalized ϵ-covers that will be used for manifolds are: a collection of tangent flats that approximate the manifold, bounded using μ_{II}, and a collection of tangent subspaces that approximate all the tangent subspaces of the manifold, bounded using μ_{III}.

Both kinds of generalized cover are derived from ϵ-nets of M, with respect to two different distance measures on M, called D_{II} and to D_{III}. These distance measures, and the measure D_{I}, are discussed in the next subsection.

The distances D_{I}, D_{II}, and D_{III} on manifolds are central to the constructions here. In contrast to these distances, the Euclidean distance between two points x, y ∈ IR^{m} will be denoted ∥x−y∥, while the minimum distance between a point p and a set, such as a tangent space T, will be denoted D_{E}(p, T).

The notation D_{X}, for X ∈ {I, II, III}, derives from the relation of these distances to the corresponding fundamental forms, which generally correspond to the metric tensors of these distances.

2.1 Distance D_{I}

Given a manifold M ⊂ IR^{m} and a, b ∈ M, the geodesic distance between a and b is denoted here by D_{I}(a, b); this is the length of the shortest path on M between a and b, where the metric tensor on vector v is simply v^{2}; that is, the length of a very short path is the Euclidean distance in IR^{m} between its endpoints. Note that always D_{I}(a, b) ≤ ∥a − b∥.

2.2 Distance D_{III}, Grassmann manifolds, principal angles

Another metric on M that will be needed is the curvature-based distance D_{III}(a, b), which is the length of the shortest curve between a and b in M, where the measure of the curve C is the length of the Gauss map image N(C) of C. The Gauss map N takes a point a ∈ M to its tangent subspace T_{a}, which can also be regarded as a point in G_{d,m}, the Grassmann manifold of d-dimensional linear subspaces of IR^{m}. (More precisely, the tangent subspace and the Grassmann manifold are in general oriented, but here the assumption of manifold orientability, which is nearly without loss of generality, using the double cover construction, allows this to be glossed over.) That is, for a, b ∈ M that are very close together, the distance D_{III}(a, b) ≈ D_{I}(T_{a}, T_{b}), where T_{a}, T_{b} ∈ G_{d,m}. For example, when M is a curve, the tangent subspaces are lines through the origin, and so (the oriented version of ) cG_{1,m} is identifiable with 𝕊^{m−1}. Similarly, when M has codimension one, the Grassmann manifold can be identified with 𝕊^{m−1}, by mapping from an (m − 1)-dimensional tangent subspace to its unit normal.

More generally, the distance between two nearby T_{a}, T_{b} ∈ G_{d,m} is a function of the principal angle vector between T_{a} and T_{b}. The principal angle vector θ ∈ IR^{d} can be described as follows: cos θ is the vector of singular values of Y_{a}^{T} Y_{b}, where Y_{a} and Y_{b} are an m×d orthonormal bases for T_{a} and T_{b}. (Here cos θ means the vector whose i’th coordinate is cos θ_{i}.) The arclength between T_{a} and T_{b} in G_{d,m} is ∥θ∥. The matrix Y_{a}Y_{a}^{T} projects points of IR^{m} onto T_{a}, and similarly for Y_{b}Y_{b}^{T}. The projection 2-norm ∥Y_{a}Y_{a}^{T} −Y_{b}Y_{b}^{T} ∥_{2} is a measure of distance between T_{a} and T_{b}, related to the principal angles by ∥Y_{a}Y_{a}^{T} − Y_{b}Y_{b}^{T} ∥ = ∥sin θ∥_{∞}. (The matrix norm ∥∥_{2} here is ∥M∥_{2} := sup_{x∈IR^{d}}∥Mx∥/∥x∥.) Note that

(1)  ∥sin θ∥_{∞} ≤ ∥sin θ∥ ≤ ∥θ∥,

so the projection 2-norm ∥Y_{a}Y_{a}^{T} −Y_{b}Y_{b}^{T} ∥_{2} is always bounded above by the Grassmannian arc length between T_{a} and T_{b}, which is bounded above by D_{III}(a, b). The relations among metrics on Grassmann manifolds are discussed in detail by Edelman et al. [EAS99].

A key property of D_{III} needed here follows from these relations. It implies that an ϵ-cover for D_{III} can be used to obtain a generalized ϵ-cover for all unit tangent vectors.

Lemma 2.1. For a, b ∈ M and unit vector v ∈ T_{a}, there is a unit vector v′ ∈ T_{b} such that ∥v − v′∥ ≤ D_{III}(a, b).

Proof. Using the notation and discussion just above, since ∥Y_{a}Y_{a}^{T} − Y_{b}Y_{b}^{T} ∥_{2} ≤ D_{III}(a, b), it follows by definition of the matrix norm and by (1) that

∥v − Y_{b}Y_{b}^{T} v∥ = ∥(Y_{a}Y_{a}^{T} − Y_{b}Y_{b}^{T})v∥ ≤ D_{III}(a, b)∥v∥
= D_{III}(a, b),

and so the lemma follows, with v′ = Y_{b}Y_{b}^{T} v. □

Section B on page 27 gives an explicit description of D_{III} and its metric tensor, in terms of the local Taylor expansions of charts of the manifold.

2.3 Distance D_{II}

The distance metric D_{II}(a, b) is the length of the shortest path between a and b in M, where the length of a very short path is roughly the square root of the absolute value of the curvature at a in the direction of b. For manifolds whose dimension and codimension are greater than one, the metric D_{II} as defined here is not Riemannian, and so it has no metric tensor as such. To define this metric and understand its properties, some preliminaries are needed, and discussed next.

Coordinates oriented to a ∈ M Given a point a on a d-manifold M in IR^{m}, translate the coordinate system so that a is at the origin, and rotate the coordinate system so that the tangent d-flat a + T_{a} to M at a is T_{a} := {x ∈ IR^{m}|x_{d+1} = x_{d+2} = … x_{m} = 0}. With this change, a+T_{a} is naturally identified with IR^{d}. Let ϕ : IR^{d} → IR^{m} be a coordinate chart of M at a, so that we can equivalently take the domain of ϕ to be a neighborhood of the origin in T_{a} = IR^{d}. To expand ϕ in Taylor series about zero, we can consider each coordinate of ϕ(x) as a separate function ϕ_{i} : IR^{d} → IR. Such a function has Taylor expansion

ϕ_{i}(x) = ϕ_{i}(0) + ∇ϕ_{i}(0)^{T} x + \frac{1}{2}x^{T} ∇^{2}ϕ_{i}(0)x + O(∥x∥^{3}).

Stacking the ∇ϕ_{i}(0)^{T} as rows of an n × d matrix G, and letting H_{i} := ∇^{2}ϕ_{i}(0), we obtain

(2)  ϕ(x) = ϕ(0) + Gx + \frac{1}{2} [ x^{T} H_{1}x ; x^{T} H_{2}x ; ⋮ ; x^{T} H_{m}x] + O(∥x∥^{3}).

By the translation, ϕ(0) = 0, and by a further rotation in IR^{d}, G = [ \begin{matrix}D \\ 0 \end{matrix} ], where D is a d × d diagonal matrix. By an appropriate change of variables for ϕ, we can assume that D is in fact the identity matrix I. (For d = 1, this says that the tangent vector is a unit vector, that is, the parameterization is “unit speed.”)

D_{II}, and Covering Manifolds by Tangent Flats We will define the D_{II} distance near a using the expansion (2): let A_{i} denote the matrix whose eigenvalues are the square root of the absolute values of the eigenvalues of H_{i}. let q_{II}(x; a) be defined by

(3)  q_{II}(x; a) := [ ∑_{d≤i≤m}∥A_{i}x∥^{4}]^{1/2} .

Then the D_{II}-length of a curve C on M can be defined as ∫_{M} \sqrt{q_{II}(f′(t); f(t))}dt, where f is a unit-speed parameterization of C, and D_{II}(a, b) is then defined as the infinum of the D_{II}-lengths of curves connecting a and b.

The motivation for this definition is that for a given point ϕ(x) ∈ M close to a, for a chart ϕ oriented to a as above, its distance to a + T_{a} satisfies

D_{E}(ϕ(x), a + T_{a})^{2} = ∑_{d≤i≤m} ϕ_{i}(x)^{2}

≈ ∑_{d≤i≤m}(x^{T} H_{i}x)^{2}. (4)

By choosing the A_{i} as described, we have that D_{E}(ϕ(x), a+T_{a}) is dominated by right hand side above; also, \sqrt{q_{II}(x; a)} is a seminorm on x, via the seminorms ∥A_{i}x∥, i = d … m, and the ℓ_{4}-norm on the vector of those ∥A_{i}x∥ values. (Here a seminorm satisfies the properties of a norm, except that some nonzero vectors may have seminorm zero.) This implies that D_{II}, as defined, is a pseudometric, that is, a function that satisfies the conditions of a metric, except that some distinct points may be at D_{II}-distance zero from each other.

For the approximate condition of (4) on the previous page to hold, strictly speaking it’s necessary to augment q_{II} so that the ϕ_{i} terms are dominated even when all x^{T} H_{i}x are zero. This can be done by replacing the ∥A_{i}x∥^{4} terms in (3) on the preceding page by ∥A_{i}x∥^{4} + η∥x∥^{2}, where η is an arbitrarily small, but fixed, value greater than zero. The result is that for ∥x∥ small enough, the approximation of (4) holds. The result of this perturbation is that μ_{II}(M) will have an arbitrarily small, but fixed, additive term behaving like μ_{I}(M). A positive side effect is that D_{II} becomes a metric.

With the given definition of D_{II}, we have the following lemma.

Lemma 2.2. There is a value ω(M) > 0 and absolute constant β > 0 so that for any a, a′ ∈ M, if D_{II}(a, a′) ≤ ω(M), then D_{E}(a′, a + T_{a}) ≤_{β} D_{II}(a, a′)^{2}.

Proof. By construction, the asserted inequality holds for a′ in a sufficiently small neighborhood of a given point a. Moreover, there is a neighborhood V of a that is the image of a single chart ϕ. For a point a′ ∈ V close enough to a, the projection P_{a}x′ of a tangent vector x′ ∈ T_{a′} onto T_{a} yields a value for the metric tensor q_{II}(P_{a}x′; a). For all points a′ close enough, by the smoothness of M this value is within a constant factor of q_{II}(x′; a′). Thus D_{II}(a, a′)^{2} is within a constant factor of of q_{II}(ϕ^{−1}a′; a), which for close enough a′ is within a constant factor of the distance of a′ to T_{a}.

Since for every a ∈ M, there is a neighborhood V′ of a within which the asserted inequality D_{E}(a′, a+T_{a}) ≤_{2} D_{II}(a, a′)^{2} holds, it follows by the Lebesgue Number Lemma that there is a value ω such that this condition holds for any a, a′ with D_{II}(a, a′) ≤ ω(M). □

Note that while H_{i} may not be positive semidefinite, A_{i}^{2} always is, so that for any x, ∥A_{i}x∥^{2} = x^{T} A_{i}^{2}x ≥ x^{T} H_{i}x, so D_{II}(a, b) may be much larger than D_{E}(b, a + T_{a}).

The D_{II} metric is related to curvature in several ways: when d = 1 and D_{II}(q, a) is small, it is approximately the integral of the square root of the curvature from a to q. When d = m − 1 and D_{II}(q, a) is small, it is proportional to the square root of the normal curvature at q in the direction a−q. In general, the D_{II}-length of a curve from a ∈ M to ϕ(αx), for x ∈ T_{a} and α = 0 … δ, is approximately equal to δ times the square root of the directional curvature at a in the direction x.

In the extreme cases of dimension or codimension equal to one, the function (3) on the previous page is a quadratic form, and so D_{II} is a Riemannian metric. Otherwise, D_{II} is only a Finsler metric.

2.4 Measures, Net Sizes, and ψ_{X}(M, ϵ)

Each distance measure D_{X}, for X ∈ {I, II, III}, has an associated Hausdorff measure μ_{X}, where μ_{I}(M) is the d-dimensional measure (surface area) of M, and μ_{III}(M) is its total absolute curvature. The corresponding measure μ_{II}(M) is the integral over M of the square root of the absolute value of the Gaussian curvature, for M with dimension or codimension one. For a manifold of codimension one, there is a triangulation comprising d-simplices whose Hausdorff distance to M is O(μ_{II}(M)/ϵ^{2/d}) as ϵ → 0 [Cla06], and this is asymptotically tight for a large class of manifolds, under some mild restrictions. The triangulation vertices are a \sqrt{ϵ}-net of M with respect to D_{II}. Here that ϵ-net construction and approximation of the manifold is extended to manifolds of higher codimension, but the approximation is not with respect to Hausdorff distance, but a weaker one, by a generalized cover comprising tangent flats. The existence of such a covering is then used to prove bounds for random projections.

We may write D_{X} for X ∈ {I, II, III}, and correspondingly μ_{X}, and so on, or drop the suffix when the ambiguity is harmless. Rather than write C(M, D_{X}, ϵ), we will generally write C_{X}(M, ϵ), or when the intention is clear, omit the subscript.

For small enough ϵ, μ(M) (referring to any of the three) is within some 2^{Θ(d)} of C(M, ϵ)ϵ^{d}, but this need not be true for large ϵ: for example, for a curve C in IR^{d}, consider the boundary C′ := ∂(C + B_{r})of the Minkowski sum C + B_{r}, where B_{r} is a d-dimensional ball of radius r centered at the origin, and r > 0. If r ≪ ϵ, then the points of an ϵ-net of C′ will be scattered along the length of C, and the length μ_{I}(C) ≈ ϵC_{I}(C′, ϵ), but the surface area μ_{I}(C′) is proportional to μ_{I}(C)r^{d−1}. (Note that the measures μ_{I} are d-dimensional for the d-manifold C′, but 1-dimensional for the 1-manifold C.) A related fact here is that for a point a ∈ C′ and the set B(a, ϵ) of points p ∈ C′ with D_{I}(p, a) ≤ ϵ, the surface area μ_{I}(B(a, ϵ)) ≈ r^{d−1}ϵ ≪ ϵ^{d}: a ball of such a radius ϵ in C′) has much smaller measure than a ball in IR^{d} of the same radius.

To avoid the need for reference to “small enough ϵ,” which could also be viewed as not counting lower-order asymptotic terms that depend on M, while keeping to the philosophy of accounting for all dependence on M, let ψ_{X}(M, ϵ) be the “fudge factor” relating C(M, ϵ) and μ(M)/ϵ^{d}:

ψ(M, ϵ) := [\frac{C(M, ϵ)}{μ(M)/ϵ^{d}} ]^{1/d} .

Thus ψ(M, ϵ) = O(1) as ϵ → 0. Results will be expressed in terms of μ(M), ϵ, and ψ(M, ϵ), instead of simply in terms of C(M, ϵ), so that the asymptotic dependence will be clearer, but the non-asymptotic, large ϵ situation will still be accounted for.

For convenience of calculation, we will often assume that ψ(M, ϵ) is nonincreasing as ϵ → 0. (Alternatively, the quantity ψ̂(M, ϵ) := sup_{ϵ′≤ϵ} ψ(M, ϵ) could be used, which by construction is nonincreasing as ϵ → 0.)

As defined, this factor simply translates from the net size C(M, ϵ) to the asymptotically equivalent μ(M)/ϵ^{d}, but it is possible to relate C(M, ϵ) to some known quantities nonasymptotically, under mild assumptions. Such a relation for C(M, ϵ) then implies a relation for ψ(M, ϵ).

Roughly, the size of an ϵ-net depends on what fraction of the manifold an average point will cover, and the latter is the correlation integral of the manifold. More formally, suppose for an ϵ-net N ⊂ M that the Voronoi regions V_{a} ⊂ M of a ∈ N all have about the same measure μ(V_{a}) ≈ μ(M)/|N|. Suppose also that balls of radius ϵ centered at points in V_{a} have about the same measure on average as B(a, ϵ), that is, μ(B(a, ϵ)) ≈ ∫_{V_{a}} μ(B(b, ϵ))dμ(b)/μ(V_{a}). The latter condition is implied by Ahlfors regularity, that balls of the same size have about the same measure, but plainly is weaker. Under these assumptions,

μ(M) ≤ ∑_{a∈N} μ(B(a, ϵ))

≈ ∑_{a∈N} μ(B(a, ϵ))μ(V_{a})|N|/μ(M)

≈ |N| ∑_{a∈N} ∫_{V_{a}} μ(B(b, ϵ))dμ(b)/μ(M)

= \frac{|N|}{μ(M)} ∫_{M} μ(B(b, ϵ))dμ(b),

that is, for some β ≥ 0,

\frac{1}{|N|} ≤_{β} \frac{1}{μ(M)^{2}} ∫_{M} μ(B(b, ϵ))dμ(b).

A similar relation with ∫_{M} μ(B(b, ϵ/2))dμ(b) holds in the other direction, using μ(M) ≥ ∑_{a∈N} μ(B(a, ϵ/2)).

That is, under some reasonable “smoothness” conditions, C(M, ϵ) can be naturally expressed within 2^{Θ(d)} of ∫_{M} μ(B(b, γ))dμ(b)/μ(M)^{2}, the correlation integral, which is the probability that two points randomly chosen from M according to μ will be closer than γ. (The normalization by μ(M)^{2} is needed to obtain a probability.) Here γ = ϵ/2 and γ = ϵ provide bounds for C(M, ϵ) and so for ψ(M, ϵ). The correlation integral thus encodes the situation of manifolds that are d-dimensional but are roughly lower-dimensional, as in the above example. Such manifolds have a small injectivity radius, and the correlation integral reflects that. Bounds could also be expressed in terms of the injectivity radius itself, but that may be unduly pessimistic.

The correlation dimension characterizes the asymptotic behavior of the correlation integral as ϵ → 0; the random projection technique has been proposed as a method for speeding up the estimation of the the correlation dimension [HWB07].

3 Sets of Bounded Box Dimension

The lemma below considers approximate isometries of subsets of the unit sphere that have bounded box dimension, or more generally subsets that have generalized ϵ-covers of size 1/ϵ^{d+o(1)} as ϵ → 0.

Lemma 3.1. Let S ⊂ 𝕊^{m} have a family N(S, ϵ) of generalized ϵ-covers of size C(S, ϵ), with respect to the Euclidean metric. Suppose for convenience that

C(S, ϵ′) ≤ C(S, ϵ)(ϵ/ϵ′)^{d}

for ϵ′ ≤ ϵ. Then S is ϵ-isometrized with probability at least 1 − δ by a k-map where

k = O(ϵ^{−2}c_{JL}log((exp(d) + f_{N})C(S, ϵ)/δ)),

as ϵ → 0, with absolute asymptotic constants. Here f_{N} must be an upper bound on the failure multiplier for isometrizing any member of any N(S, ϵ), and also of the square root of the failure multiplier needed for isometrizing F − F′, for F, F′ ∈ N(S, ϵ).

For finite sets, this result is uninteresting: for small enough ϵ, the promised k-map has k ≥ |S|, and so the result is trivially true.

The lemma is more interesting for an infinite set S: then for finite S′ ⊂ S with d/ log |S′| sufficiently small, the results here are better than those for JL as applied directly to S′.

When the family N(S, ϵ) is a family of (nongeneralized) ϵ-covers, then the condition C(S, ϵ) = 1/ϵ^{d+o(1)} is the definition of S having box dimension d. Here the monotonicity assumption C(S, ϵ′) ≤ C(S, ϵ)(ϵ/ϵ′)^{d} for ϵ′ ≤ ϵ is simply a strong form of the box dimension condition, assumed in the setting of generalized ϵ-covers. The monotonicity assumption could be removed by phrasing the results in terms of Ĉ(S, ϵ) := sup_{ϵ′≤ϵ} C(S, ϵ′)(ϵ′)^{d}/ϵ^{d}, which has Ĉ(S, ϵ)ϵ^{d} monotone nonincreasing as ϵ → 0.

In the applications here of this lemma, the generalized covers are always collections of d-flats or 2d-flats, so f_{N} is always implied by subspace JL, Lemma 1.3 on page 3.

As mentioned in the introduction, this proof is a slight extension of one by Agarwal et al. [AHPY07], which in turn is inspired by ideas of Indyk and Naor [IN07].

Proof. Let N_{i} be a sequence of ϵ_{i}-covers of S, for i = 0, …, ∞, where ϵ_{i} → 0 as i → ∞, but otherwise to be determined. For a given point a ∈ S, let u_{i}(a) denote the closest point in any member of N_{i} to a, so that u_{i}(a) → a as i → ∞. Since

a = u_{0}(a) + ∑_{i≥0} u_{i+1}(a) − u_{i}(a),

we have, for linear projection P,

Pa = Pu_{0}(a) + ∑_{i≥0} Pu_{i+1}(a) − Pu_{i}(a),

and so

(5)  ∥Pa∥ ≤ ∥Pu_{0}(a)∥ + ∑_{i≥0}∥P(u_{i+1}(a) − u_{i}(a))∥,

remarking that this includes the trivial case where the sum diverges to infinity. We will consider the probabilities δ′ and δ_{i} that for some β and β_{i} to be chosen, a k-map P β-isometrizes N_{0}, and also (β_{i}−1)-isometrizes the sets in the collection N_{i} − N_{i+1}, which are

N_{i} − N_{i+1} = {F − F′ | F ∈ N_{i}, F′ ∈ N_{i+1}},

as this was defined in Section 2 on page 8. Under the assumption of these isometries,

∥P(u_{i+1}(a) − u_{i}(a))∥ ≤ β_{i}∥u_{i+1}(a) − u_{i}(a)∥
≤ β_{i}(∥u_{i+1}(a) − a∥ + ∥u_{i}(a) − a∥)
≤ β_{i}(ϵ_{i+1} + ϵ_{i}),

which implies by (5) on the preceding page

(6)  ∥Pa∥ ≤ 1 + β + ∑_{i≥0} β_{i}(ϵ_{i+1} + ϵ_{i}).

Now choose β := ϵ/2, β_{i} := 4^{i+1}, and ϵ_{i} := ϵ/8^{i}/18 for i ≥ 0. Assuming that k can be chosen so that a k-map P satisfies these conditions,

∥Pa∥ ≤ 1 + ϵ/2 + ∑_{i≥0} \frac{4^{i+1}}{18} (ϵ/8^{i+1} + ϵ/8^{i})

= 1 + ϵ/2 + ϵ\frac{1}{18} ∑_{i≥0}(1/2^{i+1} + 4/2^{i})

= 1 + ϵ(1/2 + \frac{1}{18}(1 + 8))

= 1 + ϵ.

It remains to bound the probability of failure. Suppose

k ≥ K log(f̂_{N}C(S, ϵ)/δ)c_{JL}/ϵ^{2}

for a value K to be determined, and where f̂_{N} := exp(d) + f_{N}. Then from the definition of “failure multiplier,” and the union bound, the probability δ′, that the k-map P fails to β-isometrize N_{0}, satisfies

δ′ ≤ C(S, ϵ_{0})f̂_{N} exp(−k(ϵ/2)^{2}/c_{JL})
≤ C(S, ϵ)18^{d}f̂_{N}(δ/f̂_{N}C(S, ϵ))^{K/4},
≤ 18^{d}δ^{K/4}(f̂_{N}C(S, ϵ))^{1−K/4},

which for K > 4(1 + ln 18), f̂_{N}C(S, ϵ) > 2 exp(d), and δ < 1/2 is less than δ/2. Also

δ_{i} ≤ C(S, ϵ_{i})C(S, ϵ_{i+1})f̂_{N}^{2} exp(−k(4^{i+1} − 1)^{2}/c_{JL})
≤ C(S, ϵ_{i})C(S, ϵ_{i+1})f̂_{N}^{2}(f̂_{N}C(S, ϵ)/δ)^{−K((4^{i+1}−1)/ϵ)^{2}}
≤ 18^{2}δ^{K((4^{i+1}−1)/ϵ)^{2}}8^{d(2i+1)}(f̂_{N}C(S, ϵ))^{2−K((4^{i+1}−1)/ϵ)^{2}}

which satisfies δ/2 ≥ ∑_{i} δ_{i} under the same conditions on K, f̂_{N}C(S, ϵ), and δ, and with also ϵ ≤ 2. (Regarding ϵ, recall that S is a collection of unit vectors, so any given point is a 2-net.) Thus a k-map P fails the needed conditions with probability at most δ′ + δ/2 ≤ δ.

A lower bound on ∥Pa∥, with similar failure probability, can be proved in a similar way, and the lemma then follows with some adjustment of constants. □

4 Manifolds

For a given manifold M, consider the following subset of U(M − M):

U_{λ}(M − M) := \{\frac{a − b}{∥a − b∥} | a, b ∈ M, ∥a − b∥ > λ\} ,

the chords of M that are longer than λ, scaled to have unit length. As discussed above, if a linear map is an approximate isometry for U(M−M), then it embeds M. If U(M − M) has bounded box dimension, then the above theorem implies an embedding of M. Thus, we would like to know the sizes of (generalized) ϵ-covers of U(M − M). An ϵ^{2}-cover for M implies an ϵ-cover for U_{4ϵ}(M − M), as shown in Lemma 4.1. When points a, a′ ∈ M are close together, on the other hand, \frac{a′−a}{∥a′−a∥} approaches a unit tangent vector to M at a, and so for sufficiently small λ, an ϵ-cover for U(M − M) \ U_{λ}(M − M) can be obtained from a cover for the tangent spaces of M. Together, these facts will be used to show that Lemma 3.1 on page 14 can be applied to U(M − M) to show that k-maps are embeddings, with high probability.

4.1 Long Chords

Lemma 4.1. For a set S ⊂ IR^{m}, and given ϵ, γ > 0, if N is a generalized ϵγcover of S with respect to Euclidean distance, then U(N − N) is a generalized ϵ-cover for U_{4γ}(S − S).

If the number of members of N is bounded by C(S, ϵγ), then the number of members of U(N − N) is bounded by C(S, ϵγ)^{2}.

Proof. Suppose N is a generalized ϵγ-cover of S, and a, a′ ∈ S have b ∈ F_{a} ∈ N and b′ ∈ F_{a′} ∈ N, respectively, closest in N. Then since ∥a − b∥ ≤ ϵγ, and similarly ∥a′ − b′∥ ≤ ϵγ, we have ∥(a − a′) − (b − b′)∥ ≤ 2ϵγ, and so also ∥b−b′∥−∥a−a′∥ is smaller than 2ϵγ in magnitude. Using also that ∥a−a′∥ > 4γ,

∥\frac{a − a′}{∥a − a′∥} − \frac{b − b′}{∥b − b′∥}∥

= ∥\frac{(a − a′) − (b − b′)}{∥a − a′∥} + \frac{(b − b′)(∥b − b′∥ − ∥a − a′∥)}{∥a − a′∥∥b − b′∥}∥

≤ ∥\frac{(a − a′) − (b − b′)}{∥a − a′∥}∥ + ∥\frac{(b − b′)(∥b − b′∥ − ∥a − a′∥)}{∥a − a′∥∥b − b′∥}∥

≤ \frac{2ϵγ}{4γ} + \frac{2ϵγ}{4γ}

≤ ϵ,

and the lemma follows, since \frac{b−b′}{∥b−b′∥} ∈ U(F_{a} − F_{a′}) ∈ U(N − N). □

This lemma can be applied to a generalized covering of M by a collection of tangent flats of M, using Lemma 4.1 on the previous page and Lemma 2.2 on page 12.

Lemma 4.2. Let M be a compact differentiable manifold, and let γ, ϵ > 0, and ϵ̂:= min\{ω(M), \sqrt{ϵγ}/2\}. Then for an absolute constant β > 0, there is a generalized βϵ-cover for 𝕌_{γ}(M − M), comprising at most C_{II}(M, ϵ̂)^{2} (2d)-flats.

Proof. A ϵ̂-cover N of M with respect to the D_{II} metric has size C_{II}(M, ϵ̂), and by definition, for any b ∈ M, there is a ∈ N such that D_{II}(a, b) ≤ ϵ̂. Since ϵ̂ ≤ ω(M), it follows by Lemma 2.2 on page 12 that for such a and b, D_{E}(b, a+T_{a}) ≤_{β} ϵ̂^{2}, for some absolute constant β; that is, N′ := {a+T_{a} | a ∈ N} is a generalized βϵγ/4-cover of M. By Lemma 4.1 on the preceding page, U(N′ − N′) is a generalized βϵ-cover of 𝕌_{γ}(M − M). □

4.2 Very Short Chords

As the distance ∥a − b∥ between a, b ∈ M goes to zero, the vector a − b looks more and more like a tangent vector to M at a (or b). This suggests that to approximate short chords a−b, it is necessary, at the minimum, to approximate the unit tangent vectors to M. The size of an ϵ-net for these vectors can be bounded using the measure of the image of M under the Gauss map, which maps a point a ∈ M to its d-dimensional tangent subspace T_{a}, a member of the Grassmann manifold G_{d,m}.

Lemma 4.3. There is a generalized ϵ-cover for the set of unit tangent vectors to the smooth manifold M ⊂ IR^{m}, of size C_{III}(M, ϵ). Each member of the cover is a d-dimensional linear subspace of IR^{m}.

Proof. Let N be an ϵ-cover of M, with respect to the metric D_{III}. Then by Lemma 2.1 on page 10, for any b ∈ M, there is some a ∈ N so that for any unit v′ ∈ T_{b}, there is unit v ∈ T_{a} such that ∥v − v′∥ ≤ D_{III}(a, b) ≤ ϵ. Thus N′ := {T_{a} | a ∈ N} is a generalized ϵ-cover for all unit tangent vectors of M. □

4.3 Embedding All Chords

The above has shown that all long chords and all very short chords can be approximated (and hence embedded) economically. It remains to consider chords of intermediate length. The main question is, which chords are close to tangent vectors? The local curvature gives one answer.

Lemma 4.4. For a, b ∈ M, if there is a curve C ⊂ M between a and b whose total curvature μ_{III}(C) is no more than ϵ, then the tangent to C at b has angle no more than ϵ with a − b.

Proof. From the bound on the total curvature of C, the tangent v_{a} to C at a has angle at most ϵ with the tangent v_{b} to C at b. The angle of a − b to v_{b} is maximized if the turning from v_{b} occurs near to b; that is, if a − b is close to parallel to v_{a}. So the angle of a − b is at most the angle of v_{a} to v_{b}, which is at most ϵ. □

For any given target total curvature κ > 0, there is a distance threshold L so that that for a, b ∈ M, if ∥a − b∥ < L, then there is a curve C connecting a and b with μ_{III}(C) ≤ κ. The threshold L thus gives one way to separate “short enough” chords, that can be approximated using tangent vectors, from “long enough” chords, that can be approximated using U(N − N) for a γ-cover N.

4.3.1 Planar and Low-Torsion Connectivity

The threshold value L is partly a function of the reach ρ(M) of M, the shortest distance such that some point of IR^{m} has two distinct points of M as closest points in M. The reach is also related to the maximum curvature of M, which could be used to bound L. However, it is also possible to show that there is a tangent vector parallel to a − b, under conditions that do not depend on maximum curvature of M, or its reach. The following lemma is an example; it involves a planar curve in M, defined here as a curve that is contained in M and also in a plane (a 2-flat).

Lemma 4.5. Suppose points a, b ∈ M are connected by a planar curve C ⊂ M. Then there is some point c ∈ C such that the tangent space T_{c} at c contains a vector parallel to a − b.

Proof. Orient the plane containing the given curve C so that a − b is contained in the horizontal axis, and consider the maximum and minimum vertical coordinates of C. One of these must be nonzero, by the smoothness of M (and hence of the curve C), and so there must be a horizontal tangent vector to C, at some point c ∈ M. This tangent vector is in T_{c}, where c ∈ M, and is parallel to a − b, and so is the promised vector. □

Thus if there is a distance λ such that all chords of M shorter than λ are connected by a planar curve, then an ϵ-net for the tangent vectors of M is also an ϵ-net for all chords of M shorter than λ.

Such a planar curve connectivity condition holds when the neighborhood of a is a (pure) quadric surface. This condition does not rely on the shortness of a − b, except for b to be in that quadric neighborhood, nor does it rely on the distance to other parts of M, or on the local flatness of M.

Lemma 4.6. Suppose d-manifold M has the form

M = {a ∈ IR^{m} | a = ϕ(x), x ∈ IR^{d}} ,

for a mapping ϕ : IR^{d} → IR^{m}, where for all i = 1 … m, the i’th coordinate ϕ_{i}(x) is a quadratic function

ϕ_{i}(x) = z_{i} + x^{T} g_{i} + \frac{1}{2}x^{T} H_{i}x,

for z_{i} ∈ IR, g_{i} ∈ IR^{d}, and d × d symmetric matrix H_{i}. Then every chord a − b for a, b ∈ M is parallel to a vector v tangent to M.

Proof. Given a, b ∈ M, let x := ϕ^{−1}(a) and y := ϕ^{−1}(b), the curve C := {ϕ(αx + (1 − α)y) | α ∈ [0, 1]} has coordinates

ϕ_{i}(y + α(x − y)) = [z_{i} + y^{T} g_{i} + y^{T} H_{i}y/2]
+ α(x − y)^{T} (g_{i} + H_{i}y) + α^{2}(x − y)^{T} H_{i}(x − y)/2
=: ẑ_{i} + αĝ_{i} + α^{2}h_{i}

for suitable values ẑ_{i}, ĝ_{i}, and h_{i}, that are coordinates of ẑ, ĝ, h ∈ IR^{m}. That is, the curve C can be expressed as {ẑ + αĝ + α^{2}h | α ∈ [0, 1]}. This curve is contained in the plane that contains ẑ, ĝ, and h, and so is planar. Thus there is a point c ∈ C so that the tangent vector to C at c is parallel to a − b. (In fact, that point c is ϕ((x + y)/2).) □

As noted in Theorem 1.6 on page 7, bounds for embedding can be simplified for a pure quadric surface: there is a bound for the projection dimension k that depends only on the total absolute curvature μ_{III}(M), since all chords can be approximated tangent vectors. It’s also worth mentioning that a pure quadric surface sits in a flat of dimension O(d^{2}), and so a projection dimension k = O(d^{2}/ϵ^{2}) suffices to ϵ-embed it, with high probability [Sar06, AHPY07].

Turning to a more approximate setting: if there is a curve connecting a and b that is nearly planar, then the curve has a tangent vector nearly parallel to a − b. To prove this, a characterization of “nearly planar” is needed, starting with this lemma relating the angle between the osculating planes at two nearby points on a curve with the torsion and curvature at those points.

Lemma 4.7. Given a curve C = {ϕ(x) | x ∈ [0 … μ_{I}(C)]} with a unit-speed parameterization ϕ, the Grassmannian arc length between the osculating planes at two points ϕ(x) and ϕ(x + δ) is at most δτ/κ(1 + O(δ)) as δ → 0, where τ is the torsion τ at ϕ(x) and κ is the curvature at ϕ(x).

(In the lemma and below, μ_{I}(C)) denotes the length of C, that is, its 1dimensional measure and not its d-dimensional measure.)

Proof. Please see Section A on page 26 □

Motivated by this lemma, for a curve C define the total torsion ratio τ̂(C) to be the integral over C of ratio of the torsion to the curvature. From the above lemma, the Grassmannian arc length between the osculating planes at points w, w′ ∈ C is at most τ̂(C).

Lemma 4.8. For a d-manifold M, suppose a, b ∈ M are connected by a curve C ⊂ M such that the total torsion ratio τ̂(C) ≤ ϵ^{2}∥a − b∥/μ_{I}(C). Then there is a tangent vector t to C that is within angle 3ϵ of a − b, for ϵ smaller than an absolute constant.

Proof. For a point w ∈ C, let h(w) be the osculating plane (through the origin) that, by definition contains the tangent vector to C at w, and also contains the acceleration vector to C at w. Here, as above, a unit-speed parametrization of C is assumed, so that the tangent and acceleration vectors at each point of C are orthogonal. Let P_{w} : IR^{m} → h(c) be the projection onto h(w).

We will need a fact about the projections P_{w}: by hypothesis, τ̂(C) ≤ ϵ^{2}∥a − b∥/μ_{I}(C) ≤ ϵ^{2}, and so by Lemma 4.7 on the preceding page, the Grassmannian distance from h(w) to h(b) is at most ϵ^{2}. As discussed in Section 2 on page 8, that Grassmannian distance bounds the projection 2-norm distance between P_{w} and P_{b}; as applied to any vector y, this implies that

(7)  ∥P_{w}y − P_{b}y∥ ≤ ϵ^{2}.

The idea of the proof is to apply Lemma 4.5 on page 19 to P_{b}C, implying that there is some unit tangent vector v̂ of P_{b}C at some ĉ ∈ P_{b}C that is parallel to P_{b}(a − b), and to show (i) that the angle of P_{b}(a − b) to a − b is no more than 2ϵ, and also (ii) that the angle of v̂ to the tangent vector v of C at c := P_{b}^{−1}(ĉ) is O(ϵ^{2}). The combination of these two claims implies the result, for small enough ϵ. (The choice of P_{b} as a projection was somewhat arbitrary: any P_{w} for w ∈ C would do.)

For claim (ii): we apply (7) to point c ∈ C and its unit tangent vector v; this implies that ∥P_{c}v − P_{b}v∥ ≤ ϵ^{2}. Since v is the tangent vector to C at c, P_{c}v = v, and so ∥v − P_{b}v∥ ≤ ϵ^{2}. Also P_{b}v is parallel to the tangent vector v̂ to P_{b}C at ĉ, by the linearity of the projection, and its length is of 1 − O(ϵ^{2}). So the angle of v to v̂ is O(ϵ^{2}).

For claim (i), let n := a − b − P_{b}(a − b) be the component of a − b normal to h(b). Since n is normal to h(b), and the tangent to C at b is in h(b), motion along C at b has no component in the direction of n. Moreover, applying (7) to vector n, we have that at point b ∈ C, and at any point w ∈ C, ∥P_{w}n − P_{b}n∥ = ∥P_{w}n∥ ≤ ∥n∥τ̂(C), or ∥P_{w}n/∥n∥∥ ≤ τ̂(C). Thus, in walking along C from b to a, the travel in the direction of n is at most τ̂(C), per unit distance traveled. The length of C is μ_{I}(C), and C travels ∥n∥ in the direction of n in going from b to a. It follows, using the lemma hypothesis, that

∥n∥ ≤ τ̂(C)μ_{I}(C) ≤ \frac{ϵ^{2}∥a − b∥}{μ_{I}(C)}μ_{I}(C) = ϵ^{2}∥a − b∥.

Letting θ denote the angle between a − b and its projection P_{b}(a − b) onto h(b), it follows that

cos θ = \frac{(a − b) · (a − b − n)}{∥a − b∥∥a − b − n∥} ≥ \frac{(a − b)^{2} − n · (a − b)}{(a − b)^{2}} ≥ 1 − ϵ^{2},

and so θ ≤ 2ϵ for ϵ small enough.

This completes the proof of claim (i), and so with (ii) and the argument above, the lemma follows. □

4.4 The Main Result

It is now possible to prove the main result of this paper, tying together the bounds for isometrizing long chords and short chords. To do this, we need the quantity τ(M, ϵ); as defined just before Theorem 1.5, this is the largest Euclidean distance τ such that ∥a − b∥ ≤ τ implies that there is a curve C ⊂ M connecting a and b so that either the total curvature of C is less than ϵ, or the total torsion ratio τ̂(C) ≤ ϵ^{2}∥a − b∥/μ_{I}(C). The motivation for this definition, and its immediate consequence, is that for a, b ∈ M with ∥a−b∥ ≤ τ, the vector a − b must be within angle O(ϵ) of a tangent vector to a; this holds either via Lemma 4.4 on page 19 or Lemma 4.8 on the preceding page.

Theorem 1.6, restated. A connected, compact, orientable, differentiable manifold M is ϵ-embedded with probability at least 1 − δ by a k-map with

k = O(L(d, ϵ, δ)) + O(ϵ^{−2}(log(μ_{II}ψ_{II}^{d}(1/τ^{d} + 1/ω^{d}) + μ_{III}ψ_{III}^{d}))

as ϵ → 0, with absolute asymptotic constants, under the assumption that ψ_{X}(M, ϵ) is increasing in ϵ for X ∈ {II, III}. The dependence of some quantities on M and ϵ is omitted for brevity. Here as before

L(d, ϵ, δ) := ϵ^{−2}(d log(1/ϵ) + log(1/δ)).

If τ is not needed, that is, τ(M, ϵ) = diam(M), then the term depending on μ_{II}(M) is not needed. If only geodesic distances on M need be approximately preserved, a k-map with

k = O(ϵ^{−2}(log(1/δ) + log(μ_{II}ψ_{II}^{d}(1/τ^{d} + 1/ω^{d}) + μ_{III}ψ_{III}^{d}/ϵ^{d}))

suffices. Analogous statements hold with “I” replacing “II” in the above, where ω(M) can be omitted.

Proof. We show that U(M − M) has generalized ϵ-covers of an appropriate size, so that Lemma 3.1 on page 14 can be usefully applied. To construct such covers, we consider covers for the long chords, in U_{τ(M,ϵ)}(M − M), and also for the remaining short chords. (As in the theorem statement, dependencies on M and ϵ may be omitted.)

Lemma 4.3 on page 18 says that there is a generalized ϵ-cover for the unit tangent vectors of M, of size C_{III}(M, ϵ). For a, b ∈ M, if ∥a − b∥ ≤ τ, then as discussed just before the theorem statement, there is some unit tangent vector v of angle O(ϵ) with a − b, or in other words ∥v − \frac{a−b}{∥a−b∥}∥ = O(ϵ). Thus there is a generalized O(ϵ)-cover of the short chords, of size C_{III}(M, ϵ), with absolute asymptotic constants, and the cover comprises d-dimensional linear subspaces.

Applying Lemma 4.2 on page 18 with γ = τ, there is a generalized O(ϵ)- cover of size C_{II}(M, ϵ̂)^{2} for the long chords, where ϵ̂:= min\{ω(M), \sqrt{ϵτ}/2\}, and the members of the cover are 2d-flats.

So U(M − M) has a generalized O(ϵ)-cover of size

O(C_{II}(M, ϵ̂)^{2}) + O(C_{III}(M, ϵ))
= O(μ_{II}ψ_{II}^{d}/ϵ̂^{d})^{2} + μ_{III}ψ_{III}^{d}/ϵ^{d}),

(8)

plugging in the definitions of the ψ_{X} functions.

This argument applies for any ϵ > 0, and by the theorem hypothesis, ψ_{X}(M, ϵ) is decreasing as ϵ → 0, for X ∈ {II, III}, implying the monotonicity assumption of Lemma 3.1 on page 14 for C(S, ϵ′) and ϵ′ ≤ ϵ, where S = U(M−M). Hence Lemma 3.1 on page 14 can be applied, with C(S, ϵ) bounded by (8), and with f_{N} taken as exp(4c_{JLs}d).

We have

k = O(ϵ^{−2}(log((exp(d) + f_{N})(O(μ_{II}ψ_{II}^{d}/ϵ̂^{d})^{2}
+ μ_{III}ψ_{III}^{d}/ϵ^{d})/δ)/c_{JL})
= O(L(d, ϵ, δ))
+ O(ϵ^{−2} log(μ_{II}ψ_{II}^{d}(1/τ^{d} + 1/ω^{d}) + μ_{III}ψ_{III}^{d})),

(9)

as ϵ → 0, with absolute asymptotic constants, as claimed. Neglecting the ψ_{X} = O(1) terms, this is

O(L(d, ϵ, δ)) + O(ϵ^{−2} log(μ_{II}(1/τ^{d} + 1/ω^{d}) + μ_{III})).

For preservation of geodesic distances, it is enough to ϵ-embed short chords, and also to (1/2)-embed long chords so that the projected version of the manifold is not self-intersecting. This implies the same cover with respect to D_{III}, but a smaller cover with respect to D_{II}, the latter having no dependence on ϵ. The appropriate simplification of (9) yields the claim in the theorem statement.

For replacement of D_{II} by D_{I}, an ϵ̂-cover of M with respect to D_{I} can be used instead of the generalized ϵ̂-cover by D_{II}, to obtain the cover of long chords. □

5 Concluding Remarks

A natural question here is the extension of these results to polyhedral manifolds, part of which might involve the generalization of the D_{X} distance measures.

While D_{III} and D_{I} have natural non-smooth analogs, this doesn’t seem to be true for D_{II}. Perhaps ϵ-nets in the hybrid metric D_{I+III} could be used; such a construction would generalize Dudley’s construction and isophotic triangulations [Cla06, Dud74, PSH^{+}04].

Another natural question regards lower bounds: do these results give a sharp characterization of the projection dimension? Unfortunately not: a curve of arbitrarily high curvature has a small projection dimension if it is planar. More generally, the bounds here are not monotone as a function of set inclusion: the bounds for a helix may be large, while those for a cylinder containing the helix are small. However, these situations are “special,” and non-generic, at least heuristically.

Acknowledgment I am grateful to the SOCG referees for their careful comments.

References

[AC06] N. Ailon and B. Chazelle. Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform. In Proc. 38th STOC, pages 557–563, 2006. 1

[AHPY07] P. K. Agarwal, S. Har-Peled, and H. Yu. Embeddings of surfaces, curves, and moving points in Euclidean space. In SOCG ’07: Proc. Symp. on Computational Geometry, 2007. 1, 1, 3, 4.3.1

[BW06] R. Baraniuk and M. Wakin. Random projections of smooth manifolds. to appear, Foundations of Computational Mathematics, 2006. 1, 1, 1.4, 1

[Cla06] K. L. Clarkson. Building triangulations using ϵ-nets. In STOC 2006: Proceedings of the Thirty-eighth Annual SIGACT Symposium, 2006. 1, 2.4, 5

[Dud74] R. M. Dudley. Metric entropy of some classes of sets with differentiable boundaries. J. Approximation Theory, 10:227–236, 1974. 5

[EAS99] A. Edelman, T. A. Arias, and S. T. Smith. The geometry of algorithms with orthogonality constraints. SIAM Journal on Matrix Analysis and Applications, 20(2):303–353, 1999. 2.2, A, B, B

[Gru93] P. M. Gruber. Asymptotic estimates for best and stepwise approximation of convex bodies I. Forum Math., 5:281–297, 1993. 1

[HWB07] C. Hegde, M. B. Wakin, and R. G. Baraniuk. Random projections for manifold learning. In Neural Information Processing Systems (NIPS), December 2007. 1, 2.4 [IM04] P. Indyk and J. Matoušek. Low-distortion embeddings of finite metric

spaces, pages 177–196. CRC Press, 2004. 1

[IN07] P. Indyk and A. Naor. Nearest neighbor preserving embeddings. ACM Trans. Algorithms, 3(3), 2007. 1, 1, 3

[Ind00] P. Indyk. Dimensionality reduction techniques for proximity problems. In Symposium on Discrete Algorithms, pages 371–378, 2000. 1

[JL84] W. B. Johnson and J. Lindenstrauss. Extensions of Lipschitz mapping into Hilbert space. Contemporary Mathematics, 26:189–206, 1984. 1, 1.1, 1.2

[Lin02] N. Linial. Finite metric spaces: combinatorics, geometry, and algorithms. In International Congress of Mathematicians III, pages 573–586, 2002. 1

[Mag02] A. Magen. Dimensionality reductions that preserve volumes and distance to affine spaces, and their algorithmic applications. To appear. Preliminary version in RANDOM 2002, 2002. 1

[PSH^{+}04] H. Pottmann, T. Steiner, M. Hofer, C. Haider, and A. Hanbury. The isophotic metric and its application to feature sensitive morphology on surfaces. In T. Pajdla and J. Matas, editors, Computer Vision — ECCV 2004, Part IV, volume 3024 of Lecture Notes in Computer Science, pages 560–572. Springer, 2004. 5

[Sar06] T. Sarlós. Improved approximation algorithms for large matrices via random projections. In FOCS2006: Proc. 47th Annual IEEE Symp. on Foundations of Computer Science, pages 143–152, 2006. 1, 1, 1.3, 1, 4.3.1

[Ste91] G. W. Stewart. Perturbation theory for the singular value decomposition. In R. Vaccaro, editor, SVD and Signal Processing, II: Algorithms, Analysis and Applications, pages 99–109. Elsevier, 1991. A, B

[Vem04] S. Vempala. The Random Projection Method, volume 65 of Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, 2004. 1

[Wey12] H. Weyl. Das asymptotische Verteilungsgesetz der Eigenwerte linearer partieller Differentialgleichungen (mit einer Anwendung auf der Theorie der Hohlraumstrahlung). Mathematische Annalen, 71:441– 479, 1912. A, B

A Grassmannian Arc Length Between Osculating Planes

Before a proof of Lemma 4.7 on page 20, here for convenience is a restatement of it.

Lemma 4.7 restatement Given a curve C = {ϕ(x) | x ∈ [0 … μ_{I}(C)]} with a unit-speed parameterization ϕ, the Grassmannian arc length between the osculating planes at two points ϕ(x) and ϕ(x + δ) is at most δτ/κ(1 + O(δ)) as δ → 0, where τ is the torsion τ at ϕ(x) and κ is the curvature at ϕ(x).

Proof. The tangent vectors ϕ′(x) to a unit speed curve have ∥ϕ′(x)∥ = 1 for all relevant x; this implies that the acceleration vector ϕ′′(x) is orthogonal to ϕ′(x). The osculating plane at x is the linear span of ϕ′(x) and ϕ′′(x), and so is the column space of the matrix Y_{1} := [^{ϕ′(x)} ^{ϕ′′(x)} ]. Without loss of generality, via Euclidean rotation we can assume ϕ′(x) = [1, 0, …, 0]^{T}, ϕ′′(x) = [0, κ, 0, …, 0]^{T}, and so

Y_{1} = [\begin{matrix}1 & 0 \\ 0 & κ \\ 0 & 0 \\ ⋮ & ⋮ \\ 0 & 0 \end{matrix}] ,

where κ = ∥ϕ′′(x)∥, the curvature at x. Equivalently, in these coordinates the osculating plane at ϕ(x) is the column space of the matrix Ŷ_{1} := [^{I} ^{0} ^{...0} ]^{T} with orthonormal columns, where I is here the 2 × 2 identity matrix. Turning to the osculating plane at ϕ(x + δ), for small δ > 0: the torsion at ϕ(x) is τ := ∥ϕ′′′(x) − g(x)∥, where g(x) is the projection of ϕ′′′(x) onto the osculating plane. Without loss of generality, assume that ϕ′′′(x)−g(x) = [0, 0, τ, 0, …, 0]^{T}. Letting κ_{1} and κ_{2} denote the components of ϕ′′′(x) in the osculating plane at ϕ(x), we have that the osculating plane at ϕ(x + δ) is the column space of

Y_{2} := [ϕ′(x + δ) ϕ′′(x + δ)] = [\begin{matrix}1 & δκ_{1} \\ δκ & κ + δκ_{2} \\ 0 & δτ \\ 0 & 0 \\ ⋮ & ⋮ \\ 0 & 0 \end{matrix}] (1 + O(δ)).

(The O(δ) is as δ → 0, here and in the remainder of the proof.) As discussed by Edelman et al.[EAS99], and in Section 2 on page 8, the cosines of the principal angles between the planes generated by Y_{1} and by Y_{2} are the singular values of Ŷ_{1}^{T} Ŷ_{2}, where Ŷ_{1} is given above and Ŷ_{2} is a matrix with orthonormal columns and the the same column space as Y_{2}.

To produce Ŷ_{2}, multiply the second column of Y_{2} by δ and subtract it from the first column, then multiply the first column by δκ_{1} and subtract it from the second, and then normalize each column. The result is that

X := Ŷ_{1}^{T} Ŷ_{2} = [\begin{matrix}1 & O(δ^{2}) \\ O(δ^{2}) & \frac{(κ+δκ_{2})}{\sqrt{(κ+δκ_{2})^{2}+(δτ)^{2}}} \end{matrix} ] (1 + O(δ)).

Weyl [Wey12, Ste91] gave a bound on the perturbation of the singular values of a matrix due to the perturbation of its entries. Weyl’s bound implies that the singular values of X are within ∥X − D∥_{F} = O(δ^{2}) of the singular values of the diagonal matrix D with the same diagonal entries as X. That is, the singular values of X are 1 + O(δ^{2}) and

\frac{(κ + δκ_{2}))}{\sqrt{(κ + δκ_{2})^{2} + (δτ)^{2}}} (1 + O(δ)) = \frac{1 + O(δ)}{\sqrt{1 + (δτ)^{2}/(κ + δκ_{2})^{2}}}

= (1 − \frac{(δτ)^{2}}{2κ^{2}} )(1 + O(δ)).

These are the cosines of the principal angles between the osculating planes, so those angles are O(δ^{2}) and δτ/κ(1 + O(δ)). The Euclidean norm of the vector comprising these angles is δτ/κ(1 + O(δ)), and that norm is the Grassmannian arc length between the planes. □

B Explicit Description of D_{III}

The fundamental forms, and other aspects of manifolds, are often discussed in an intrinsic, coordinate-free, terminology, which is motivated by the fact that many of these concepts need not depend on a particular choice of coordinate system, and can be defined for manifolds that are not embedded submanifolds of IR^{m}. However, this paper is concerned only with embedded submanifolds, and so as in [EAS99], the following discussion uses the extrinsic coordinates of IR^{m}. An advantage of this approach is that little background is needed beyond linear algebra and Taylor’s theorem.

Recalling the discussion of Section 2 on page 8 and in particular the Taylor expansion (2) on page 11 of a coordinate chart ϕ(x) at a ∈ M: if the Taylor expansion is differentiated, we obtain an expression for the derivative matrix G(x) of ϕ at x near the origin:

G(x) ≈ [\begin{matrix}I \\ 0 \end{matrix}] + [ H_{1}x ; H_{2}x ; ⋮ ; H_{m}x] = G + H(x),

where this defines the matrix H(x).

Given the d-subspace T_{0} that is the linear span of the columns of G, and the d-subspace T_{ϕ(x)} that is the linear span of the columns of G + H(x), as shown below, the squared arc length in the Grassmann manifold G_{d,m} between T_{0} and T_{ϕ(x)} is

(1+O(∥x∥)) ∑_{d<i≤n} x^{T} H_{i}^{2}x

= (1 + O(∥x∥)x^{T} [ ∑_{d<i≤n} H_{i}^{2}] x

= (1 + O(∥x∥)q_{III}(x; a),

where q_{III}(x; a) := x^{T} [∑_{d<i≤n} H_{i}^{2}] x, the third fundamental form at a, evalu-

ated at the tangent vector x. (Here H_{i}^{2} := H_{i}^{T} H_{i} = H_{i}H_{i}, remembering that each H_{i} is a Hessian matrix and hence symmetric.) For example, if d = 1, then x and each H_{i} are scalars, and the vector [^{0} ^{H_{3}} ^{···} ^{H_{m}}]^{T} is the normal component of the acceleration, whose norm is the normal curvature. For a hypersurface, that is, where the codimension is one, the function x^{T} H_{m}^{2}x is the third fundamental form at a, evaluated at x. In general, the third fundamental form gives a measure of the turning of the tangent space from a to T_{ϕ(x)}, and the Riemannian metric D_{III} induced by this form gives a measure of winding angle.

Claim B.1. The squared Grassmannian arc length between the subspace spanned by the columns of G and the subspace spanned by the columns of G + H(x) is (1 + ∥x∥_{∞})∥H̄(x)∥_{F}^{2} , where H̄(x) is the (m − d) × d matrix that is the lower m − d rows of H(x).

Proof. As discussed by, for example, Edelman et al. [EAS99], if the principal angles between two subspaces generated by the columns of orthonormal matrices Y_{1} and Y_{2} are θ_{i}, i = 1 … d, then the values cos(θ_{i}) are the singular values of Y_{1}^{T} Y_{2}. (Here orthonormal means that the columns are orthogonal to each other,

and all have unit Euclidean norm.) Since G^{T} is [\begin{matrix}I \\ 0 \end{matrix}], it is orthonormal, and

multiplication by it simply selects the upper d×d submatrix of G+H(x). Since the entries of H(x) are O(∥x∥_{∞}) as ∥x∥_{∞} → 0, the columns of G + H(x) are nearly orthonormal, but not quite. We can do elementary column operations and scaling on those columns, to obtain an orthonormal matrix, and not affect the subspace the columns generate. We will do such operations, and at the same time obtain a matrix whose upper square submatrix has very small off-diagonal elements. As a result, the singular values of that upper square submatrix, selected by G^{T}, will be provably close to those diagonal entries.

Let B := G+H(x), and let B′ denote the upper square submatrix of B. For i = 1 … d, use column operations to zero out all but the diagonal entries of the upper square submatrix B′ of B. Then scale the columns so that the diagonal entries of B′ are equal to one. Then, use Gram-Schmidt orthogonalization to make the columns of B orthonormal: that is, for i = 1 … d, subtract from column b_{i} the vector b_{j}(b_{j}^{T} b_{i}), for all j < i, and then normalize b_{i}.

The effects of these operations on the entries of B can be bounded. Let α := ∥x∥_{∞}. The entries of G+H(x) are all O(α), as α → 0, except the diagonal entries (due to G), which are 1 + O(α). The elimination operations involve multiplication by a term that is O(α), and so entries that are not eventually zero are perturbed by O(α^{2}). A similar claim holds for the Gram-Schmidt orthogonalization.

During the orthogonalization step, the off-diagonal entries of B′ become nonzero. However, because they were zero before the step, the dot products used for the orthogonalization are O(α^{2}), and so the off-diagonal entries of B′ are O(α^{2}), as are the perturbations to the diagonal entries.

The above operations are repeated. Since the off-diagonal entries of B′ are O(α^{2}), the Gram-Schmidt orthogonalizations are done with vectors that are orthogonal, up to a perturbation of O(α^{2}) due to the elimination step. Hence their dot products are O(α^{4}), and the nonzero entries of B′ are O(α^{4}).

The diagonal entries of B′ are 1/\sqrt{1 + w_{i}^{2}(1 + O(α))}, where w_{i} is the (m−d)- vector comprising the lower m − d entries of G + H(x). Now we can appeal to the bound of Weyl [Wey12, Ste91] on the perturbation of the singular values due to a matrix perturbation. Weyl’s bound implies that the singular values of D, the diagonal matrix whose entries are the diagonal entries of B′, are within ∥B′ − D∥_{F} = O(α^{4}) of those of B′. Thus the singular values of G^{T} B are

1/\sqrt{1 + w_{i}^{2}(1 + O(α))} + O(α^{4}) = 1/\sqrt{1 + w_{i}^{2}} + O(α^{3}).

As discussed above, these are the values of cos θ_{i}, where the θ_{i} are the principal angles between the subspaces generated by the columns of G and of G + H(x).

Since cos θ_{i} = 1/\sqrt{1 + w_{i}^{2}} +O(α^{3}), sin^{2} θ_{i} = w_{i}^{2} +O(α^{3}), and so ∑_{i} sin^{2} θ_{i} = ∑_{i} w_{i}^{2} = ∥H̄(x)∥_{F}^{2} , which is the squared “Projection F-norm” between two points in the Grassmannian, and asymptotically equal to the other definitions of squared distance on the Grassmannian, including arc length, as discussed by Edelman et al. [EAS99]. The claim follows. □