## New Research In

### Physical Sciences

### Social Sciences

#### Featured Portals

#### Articles by Topic

### Biological Sciences

#### Featured Portals

#### Articles by Topic

- Agricultural Sciences
- Anthropology
- Applied Biological Sciences
- Biochemistry
- Biophysics and Computational Biology
- Cell Biology
- Developmental Biology
- Ecology
- Environmental Sciences
- Evolution
- Genetics
- Immunology and Inflammation
- Medical Sciences
- Microbiology
- Neuroscience
- Pharmacology
- Physiology
- Plant Biology
- Population Biology
- Psychological and Cognitive Sciences
- Sustainability Science
- Systems Biology

# Manifold parametrizations by eigenfunctions of the Laplacian and heat kernels

Communicated by Ronald R. Coifman, Yale University, New Haven, CT, October 29, 2007 (received for review September 3, 2007)

## Abstract

We use heat kernels or eigenfunctions of the Laplacian to construct local coordinates on large classes of Euclidean domains and Riemannian manifolds (not necessarily smooth, e.g., with 𝒞^{α} metric). These coordinates are bi-Lipschitz on large neighborhoods of the domain or manifold, with constants controlling the distortion and the size of the neighborhoods that depend only on natural geometric properties of the domain or manifold. The proof of these results relies on novel estimates, from above and below, for the heat kernel and its gradient, as well as for the eigenfunctions of the Laplacian and their gradient, that hold in the non-smooth category, and are stable with respect to perturbations within this category. Finally, these coordinate systems are intrinsic and efficiently computable, and are of value in applications.

In many recent applications, one attempts to find local parametrizations of data sets. A recurrent idea is to approximate a high dimensional data set, or portions of it, by a manifold of low dimension. A variety of algorithms for this task have been proposed (1⇓⇓⇓⇓⇓⇓–8). Unfortunately, such techniques seldomly come with guarantees on their capabilities of indeed finding local parametrization (but see, for example, refs. 8 and 9) or on quantitative statements on the quality of such parametrizations. Examples of such disparate applications include document analysis, face recognition, clustering, machine learning (10⇓⇓–13), nonlinear image denoising and segmentation (11), processing of articulated images (8), and mapping of protein energy landscapes (14). It has been observed in many cases that the eigenfunctions of a suitable graph Laplacian on a data set provide robust local coordinate systems and are efficient in dimensional reduction (1, 4, 5). The purpose of this paper is to provide a partial explanation for this phenomenon by proving an analogous statement for manifolds as well as introducing other coordinate systems via heat kernels, with even stronger guarantees. Here, we should point out the 1994 paper of Bérard *et al.* (15) where a weighted infinite sequence of eigenfunctions is shown to provide a global coordinate system. (Points in the manifold are mapped to ℓ_{2}.) To our knowledge, this was the first result of this type in Riemannian geometry. If a given data set has a piece that is statistically well approximated by a low dimensional manifold, it is then plausible that the graph eigenfunctions are well approximated by the Laplace eigenfunctions of the manifold. One of our results is that, with the normalization that the volume of a *d*-dimensional manifold ℳ equals one, any suitably embedded ball *B*_{r} (*z*) in ℳ has the property that one can find (exactly) *d* eigenfunctions that are a “robust”coordinate system on *B*_{cr} (*z*) (for a constant *c* depending on elementary properties of ℳ). In addition, these eigenfunctions, which depend on *z* and *r*, “blow up” the ball *B*_{cr} (*z*) to diameter at least one. In other words, one can find *d* eigenfunctions that act as a “microscope” on *B*_{cr} (*z*) and “magnify” it up to size ∼1. Another of our results is as follows. We introduce simple “heat coordinate” systems on manifolds. Roughly speaking (and in the language of the previous paragraph), these are *d* choices of manifold heat kernels that form a robust coordinate system on *B*_{cr} (*z*). We call this method “heat triangulation” in analogy with triangulation as practiced in surveying, cartography, navigation, and modern GPS. Indeed, our method is a simple translation of these classical triangulation methods.

The embeddings we propose can be computed efficiently and therefore, together with the strong guarantees we prove, are expected to be useful in a variety of applications, from di-mensionality reduction to data set compression and navigation.

Given these results, it is plausible to guess that analogous results should hold for a local piece of a data set if that piece has in some sense a “local dimension” approximately *d.* There are certain difficulties with this philosophy. The first is that graph eigenfunctions are global objects and any definition of “local dimension” must change from point to point in the data set. A second difficulty is that our manifold results depend on classical estimates for eigenfunctions. This smoothness is often lacking in graph eigenfunctions.

For data sets, *heat triangulation* is a much more stable object than eigenfunction coordinates because

heat kernels are local objects;

if a manifold ℳ is approximated by discrete sets

*X*, the corresponding graph heat kernels converge rather nicely to the manifold heat kernel (4, 5);one has good statistical control on smoothness of the heat kernel, simply because one can easily examine it and because one can use the Hilbert space {

*f*∈*L*^{2}: ∇*f*∈*L*^{2}};our results that use eigenfunctions rely in a crucial manner on Weyl's lemma, whereas heat kernel estimates do not.

The philosophy used in this paper is as follows.

##### Step 1.

Find suitable points *y*_{j}, 1 ≤ *j* ≤ *d* and a time *t* so that the mapping given by heat kernels
is a good local coordinate system on *B*(*z, cr*). (This is heat triangulation.)

##### Step 2.

Use Weyl's lemma to find suitable eigenfunctions ϕ_{ij} so that (with *K*_{j}(*x*) = *K*_{t}(*x, y*_{j})) one has ∇ϕ_{ij} (*x*) ≈ *c*_{j}∇*K*_{j} (*x*), *x* ∈ *B*(*z, cr*) for an appropriate constant *c.*

## Results

### Euclidean Domains.

We first present the case of Euclidean do-mains. Although our results in this setting follow from the more general results for manifolds discussed in the next section, the case of Euclidean domains is of independent interest, and the exposition of the theorem is simpler.

We consider the heat equation in Ω, a finite volume domain in ℝ^{d}, with either Dirichlet or Neumann boundary conditions:
Here, *v* is the outer normal on ∂Ω. Independently of the boundary conditions, we will denote by Δ the Laplacian on Ω. For the purpose of this paper, in both the Dirichlet and Neumann case, we restrict our study to domains where the spectrum is discrete and the corresponding heat kernel can be written as
where the {ϕ_{j}} form an orthonormal basis of eigenfunctions of Δ, with eigenvalues 0 ≤ λ_{0} ≤ ⋯ ≤ λ_{j} ≤ …. We also require that the following Weyl's estimate holds, i.e., there is a constant *C*_{Weyl,Ω} such that for any *T* > 0
(This condition is always satisfied in the Dirichlet case, where in fact *C*_{Weyl,Ω} can be chosen independent of Ω.) It should however be noted that these conditions are not always true and the Neumann case is especially problematic (16, 17).

### Theorem 1. Embedding via Eigenfunctions, for Euclidean Domains.

*Let* Ω *be a domain in* ℝ^{d} *satisfying all the conditions above, rescaled so that* |Ω| = 1. *There are constants c*_{1}, …, *c*_{6} > 0 *that depend only on d and C*_{Weyl,Ω}, *such that the following hold. For any z* ∈ Ω, *let R*_{z} ≤ dist (*z*, ∂Ω). *Then there exist i*_{1}, …, *i*_{d} *and constants c*_{6} *R*_{z}^{d/2} ≤ γ_{1} = γ_{1} (*z*), …, γ_{d} = γ_{d}(*z*) ≤ 1 *such that*

*(a) the map**satisfies, for any x*_{1},*x*_{2}∈*B*(*z, c*_{1}*R*_{z}),*(b) the associated eigenvalues satisfy*

##### Remark 1.

The dependence on the constant *C*_{Weyl,Ω} is only needed in the Neumann case.

### Manifolds with 𝒞^{α} Metric.

The results above can be extended to certain classes of manifolds. To formulate a result corresponding to *Theorem 1*, we must first carefully define the manifold analogue of dist (*z*, ∂Ω). Let ℳ be a smooth, *d*-dimensional compact manifold, possibly with boundary. Suppose we are given a metric tensor *g* on ℳ is 𝒞^{α} for some α > 0. For any *z*_{0} ∈ ℳ, let (*U, u*) be a coordinate chart such that *z*_{0} ∈ *U* and

(

*i*)*g*^{il}(*u*(*z*_{0})) = δ^{il};(

*ii*) for any*x*∈*U*, and any ξ, ν ∈ ℝ^{d},

We let *r*_{ℳ} (*z*_{0}) = sup{*r* > 0 : *B*_{r} (*u*(*z*_{0})) ⊆ *u*(*U*)}. Observe that, when *g* is at least 𝒞^{2}, *r*_{ℳ} can be taken to be the inradius, with local coordinate chart given by the exponential map at *z.* We denote by ∥*g*∥_{α⋀1} the maximum over all *i, j* of the α ⋀ 1-Hölder norm of *g ^{ij}* in the chart (

*U, u*). The natural volume measure

*d*μ on the manifold is given, in any local chart, by

**0.6**guarantee that det

*g*is uniformly bounded below from 0. Let Δ

_{ℳ}be the Laplace Beltrami operator on ℳ In a local chart, we have where (

*g*

^{ij}) is the inverse of

*g*. Conditions

_{ij}**0.6**are the usual uniform ellipticity conditions for the operator

**0.7**. With Dirichlet or Neumann boundary conditions, Δ

_{ℳ}is self-adjoint on

*L*

^{2}(ℳ, μ). We will assume that the spectrum is discrete, denote by 0 ≤ λ

_{0}≤ ⋯ ≤ λ

_{j}≤ its eigenvalues and by {ϕ

_{j}} the corresponding orthonormal basis of eigenfunctions, and write Eqs.

**0.1**and

**0.2**with Ω replaced by ℳ.

### Theorem 2.

*Let* (ℳ, *g*), *z* ∈ ℳ *and* (*U, u*) *be as above. Also, assume* |ℳ| = 1. *There are constants c*_{1}, …, *c*_{6} > 0, *depending on d, c*_{min}, *c*_{max}, ∥*g*∥_{α⋀1}, α ⋀ 1, *and C*_{Weyl,ℳ}, *such that the following hold. Let R*_{z} = *r*_{ℳ} (*z*). *Then there exist i*_{1}, …, *i*_{d} *and constants c*_{6}*R*_{z}^{d/2} ≤ γ_{1} = γ_{1} (*z*), …, γ_{d} = γ_{d} (*z*) ≤ 1 *such that*

*(a) the map**such that for any x*_{1},*x*_{2}∈*B*(*z, c*_{1}*R*_{z})*(b) the associated eigenvalues satisfy*

##### Remark.

In both *Theorem 1* and *Theorem 2*, the constants γ_{j} are given by
where *c* is some fixed constant, depending on *d*, *c*_{min}, *c*_{max}, ∥*g*∥_{α⋀1}, α ⋀ 1, and *C*_{Weyl}.

##### Remark 2.

The constant *C*_{Weyl,ℳ} is only needed in the Neumann case.

##### Remark 3.

Most of the proof is done on one local chart containing *z* which we choose (one which contains a large enough ball around *z*). An inspection of the proof shows that we use only the norm ∥*g*∥_{α⋀1} of the *g* restricted to this chart. In particular, the theorem holds also for *R*_{z} ≤ *r*_{ℳ} (*z*).

##### Remark 4.

When rescaling *Theorem 2*, it is important to note that if *f* is a Hölder function with ∥*f*∥_{𝒞α⋀1} = *A* and *f*_{r} (*z*) = *f*(*r*^{−1} *z*), then ∥*f*_{r}∥_{𝒞α⋀1} = *Ar*^{α⋀1}. Since we will have *r* < 1, *f*_{r} satisfies a better Hölder estimate then *f*, i.e., ∥*f*_{r}∥_{𝒞α⋀1} = *Ar*^{α⋀1} ≤ *A* = ∥*f*∥_{𝒞α⋀1}.

##### Remark 5.

We do not know, in both *Theorem 1* and *Theorem 2*, whether it is possible to choose eigenfunctions such that γ_{1} = … = γ_{d}.

Another result is true. One may replace the *d* chosen eigenfunctions above by *d* chosen heat kernels, i.e., {*K*_{t}(*z, y*_{i})}_{i=1,…,d}. In fact, such heat kernels arise naturally in the main steps of the proofs of *Theorem 1* and *Theorem 2.* This leads to an embedding map with even stronger guarantees:

### Theorem 3. Heat Triangulation Theorem.

*Let* (ℳ, *g*), *z* ∈ ℳ and (*U, u*) *be as above, where we now allow* |ℳ| = +∞. *Let R*_{z} ≤ min{1, *r*_{ℳ}(*z*)}. *Let p*_{1}, …, *p*_{d} *be d linearly independent directions. There are constants c*_{1}, …, *c*_{6} > 0, *depending on d, c*_{min}, *c*_{max}, ∥*g*∥_{α⋀1}, α ⋀ 1, *and the smallest and largest eigenvalues of the Gramian matrix* (*p*_{i}, *p*_{j})_{i,j=1,…,d}, *such that the following holds. Let y*_{i} *be so that y*_{i} − *z is in the direction p*_{i}, *with c*_{4}*R*_{z} ≤ *d*_{ℳ} (*y*_{i}, *z*) ≤ *c*_{5}*R*_{z} *for each i* = 1, …, *d and let t*_{z} = *c*_{6}*R*_{z}^{2}. *The map* Φ : *B*_{c1Rz} (*z*) → ℝ^{d}, *defined by*
*satisfies, for any x*_{1}, *x*_{2} ∈ *B*_{c1Rz} (*z*),

This holds for the manifold and Euclidean case alike and depends only on estimates for the heat kernel and its gradient.

##### Remark 6.

One may replace the (global) heat kernel above with a local heat kernel, i.e., the heat kernel for the ball *B* (*z, R*_{z}) with the metric induced by the manifold and Dirichlet boundary conditions. In fact, this is a key idea in the proof of all of the above theorems.

##### Remark 7.

All theorems hold for more general boundary condi-tions. This is especially true for the *Heat Triangulation Theorem*, which does not even depend on the existence of a spectral expansion for the heat kernel.

##### Example 1.

It is a simple matter to verify this theorem for the case where the manifold in ℝ^{d}. For example, if *d* = 2, *R*_{z} = 1, and *z* = 0, *y*_{1} = (−1, 0) and *y*_{2} = (0, −1). Then if *K*_{t} (*x, y*) is the Euclidean heat kernel,
is a (nice) biLipschitz map on *B*_{1/2} ((0, 0)). (The result for arbitrary radii then follows from a scaling argument.) This is because on can simply evaluate the heat kernel *K*_{t} (*x, y*) = [1/(4π*t*)]*e*^{−(|x−y|2)}/4*t*. In *B*_{1/2} ((0, 0)),

### Notation.

In what follows, we will write *f* (*x*) ≲_{c1,…,cn} *g*(*x*) if there exists a constant *C* depending only on *c*_{1}, …, *c*_{n}, and not on *f, g*, or *x*, such that *f*(*x*) ≤ *Cg* (*x*) for all *x* (in a specified domain). We will write *f*(*x*) ∼_{c1,…,cn} *g*(*x*) if both *f*(*x*) ≲_{c1,…,cn} *g*(*x*) and *g*(*x*) ≲_{c1,…,cn} *f*(*x*). We will write *a* ∼_{C1}^{C2} *b* for *a, b* vectors, if *a*_{i} ∼_{C1}^{C2} *b*_{i} for all *i.*

## The Proofs

The proofs in the Euclidean and manifold case are similar. In this section, we present the main steps of the proof. A full pre-sentation is given in ref. 2. Some remarks about the manifold case:

(a) As mentioned in

*Remark 3*, we will often restrict to working on a single (fixed) chart in local coordinates. When we discuss moving in a direction*p*, we mean in the local coordinates.(b) Let us say a few words about how the dependence on ∥

*g*∥_{α⋀1}comes into play. Generally speaking, in all places except one (which we will mention momentarily), the α ⋀ 1-Hölder condition is used to get local bi-Lipschitz bounds on the perturbation of the metric (resp. the ellipticity constants) from the Euclidean metric (resp. the Laplacian). The place where one really uses the Hölder condition is an estimate on how much the gradient of a (global) eigenfunction changes in a ball.(c) We will use Brownian motion arguments (on the manifold). To have existence and uniqueness, one needs smoothness assumptions on the metric (say, 𝒞

^{2}). Therefore, we will first prove the theorem in the manifold case in the 𝒞^{2}metric category, and then use perturbation estimates to obtain the result for*g*^{ij}∈ 𝒞^{α}. To this end, we will often have dependence on the 𝒞^{α}norm of the coordinates of the*g*even though we will be (for a specific lemma or proposition) assuming the^{ij}*g*has 𝒞^{2}entries.(d) We will use estimates from ref. 18. The theorems in ref. 18 are stated only for the case of

*d*≥ 3. Our theorems are true also for the case*d*= 2 (and trivially,*d*= 1). This can beseen indirectly by considering ℳ̃: = ℳ × 𝕋 and noting that the eigenfunctions of ℳ̃ and the heat kernel of ℳ̃ both factor.

The idea of the proof of *Theorem 1* and *2* is as follows. We start by fixing a direction *p*_{1} at *z.* We would like to find an eigenfunction ϕ_{i1} such that |∂_{p1}ϕ_{i1}≳ *R*_{z}^{−1} on *B*_{c1Rz} (*z*). To achieve this, we start by showing that the heat kernel has large gradient in an annulus of inner and outer radius ∼ *R*_{z}^{−1} around *y*_{1} (*y*_{1} chosen such that *z* is in this annulus, in direction *p*_{1}). We then show that the heat kernel and its gradient can be approximated on this annulus by as the partial sum of **0.1** over eigenfunctions ϕ_{λ} which satisfy both λ ∼ *R*_{z}^{−2} and *R*_{z}^{−d/2} ∥ϕ_{λ}∥_{L2(Bc1Rz} _{(z))} ≳ 1. By the pigeon-hole principle, at least one such eigenfunction, let it be ϕ_{i1}, has a large partial derivative in the direction *p*_{1}. We then consider ∇ϕ_{i1} and pick *p*_{2} ⊥∇ϕ_{i1} and by induction we select ϕ_{i1}, …, ϕ_{id}, making sure that at each stage we can find ϕ_{ik}, not previously chosen, satisfying |∂_{pk} ϕ_{ik}| ∼ *R*_{z}^{−1} on *B*_{c1Rz} (*z*). We finally show that the Φ : = (ϕ_{i1}, …, ϕ_{id}) satisfies the desired properties.

##### Step 1. Estimates on the heat kernel and its gradient.

Let *K* be the Dirichlet or Neumann heat kernel on Ω or ℳ, corresponding to one of the Laplacian operators considered above associated with *g.* We have the spectral expansion

When working on a manifold, we can assume in what follows that we fix a local chart containing *B*_{Rz} (*z*).

### Assumption A.1.

*Let the constants* δ_{0}, δ_{1} > 0 *depend on d, c*_{min}, *c*_{max}, ∥*g*∥_{α⋀1}, α ⋀ 1. *We consider z, w* ∈ Ω *satisfying* (δ_{1}/2) *R*_{z} < *t*^{1/2} < δ_{1}*R*_{z} *and* |*z* − *w*| < δ_{0}*R*_{z}.

### Proposition 4.

*Under Assumption* A.1, *let g* ∈ 𝒞^{α}, δ_{0} *sufficiently small, and* δ_{1} *is sufficiently small depending on* δ_{0}. *Then there are constants C*_{1}, *C*_{2}, *C′*_{1}, *C′*_{2}, *C*_{9} > 0, *that depend on d*, δ_{0}, δ_{1}, *c*_{min}, *c*_{max}, ∥*g*∥_{α⋀1}, α ⋀ 1} *and C′*_{1}, *C′*_{2}, *C*_{9} *dependent also on C*_{Weyl}, *such that the following hold:*

*(i) the heat kernel satisfies**(ii) if*(1/2)δ_{0}*R*_{z}< |*z*−*w*|,*p is a unit vector in the direction of z*−*w, and q is arbitrary unit vector, then**where C*_{9}→ 0*as*δ_{1}→ 0*(with*δ_{0}*fixed);**(iii) if in addition g*∈ 𝒞^{ij}^{2}, (1/2)δ_{0}*R*_{z}< |*z*−*w*|,*and q is as above, then for s*≤*t*,*(iv) C*_{1},*C*_{2}*both tend to a single function of*{*d, c*_{min},*c*_{max}, δ_{0},*C*_{Weyl}},*as*δ_{1}*tends to*0*with*δ_{0}*fixed;**(v) if g*∈ 𝒞^{2},*then also C′*_{1},*C′*_{2},*C*_{9}*can be chosen independently of C*_{Weyl}.*Furthermore, the above estimates also hold for*|ℳ| ≤ + ∞.

At this point we can side track and choose heat kernels {*K*_{t} (·, *y*_{i})}_{i=1,…,d}, with *t* ∼ *R*_{z}^{2}, that provide a local coordinate chart with the properties claimed in *Theorem 3.*

##### Proof of Theorem 3.

We start with the case *g* ∈ 𝒞^{2}. Let us consider the Jacobian *J̃* (*x*), for *x* ∈ *B*_{c1Rz} (*z*), of the map
By **0.14** we have |*J̃ _{ij}* (

*x*) −

*C′*

_{2}〈

*p*

_{i}, (

*x*−

*y*

_{j})/∥

*x*−

*y*

_{j}∥〉

*R*

_{z}

^{−1}| ≤

*C*

_{9}

*R*

_{z}

^{−1}, with

*C′*

_{2}independent of

*C*

_{Weyl}. As dictated by

*Proposition 4*, by choosing δ

_{0}, δ

_{1}appropriately (and, correspondingly,

*c*

_{1}and

*c*

_{6}), we can make the constant

*C*

_{9}smaller than any chosen ϵ, for all entries, and for all

*x*at distance no greater than

*c*

_{1}

*R*

_{z}from

*z*, where we use

*t*=

*t*

_{z}=

*c*

_{6}

*R*

_{z}

^{2}for Φ̃. Therefore, for

*c*

_{1}small enough compared to

*c*

_{4}we can write

*R*

_{z}

*J̃*(

*x*) =

*G*

_{d}+

*E*(

*x*), where

*G*

_{d}is the Gramian matrix 〈

*p*

_{i},

*p*

_{j}〉 (indepedent of

*x*), and |

*E*(

_{ij}*x*)| < ϵ, for

*x*∈

*B*

_{c1Rz}(

*z*). This implies that

*R*

_{z}

^{−1}(σ

_{min}−

*C*

_{d}ϵ) ∥υ∥ ≤ ∥

*J̃*(

*x*)υ∥ ≤

*R*

_{z}

^{−1}(σ

_{max}+

*C*

_{d}ϵ) ∥υ∥, with

*C*

_{d}depending linearly on

*d*, where σ

_{max}and σ

_{min}are the largest and, respectively, smallest eigenvalues of

*G*

_{d}. At this point, we choose ϵ small enough, so that the above bounds imply that the Jacobian is essentially constant in

*B*

_{c1Rz}(

*z*), and by integrating along a path from

*x*

_{2}to

*x*

_{2}in

*B*

_{c1Rz}(

*z*), we obtain the Theorem (Φ and Φ̃ differ only by scalar multiplication). We note that ϵ ∼ 1/

*d*suffices. To get the result when

*g*is only 𝒞

^{α}we use perturbation techniques for the heat kernel (2).

We proceed towards the proof of *Theorem 1* and *2.* The following steps aim at replacing appropriately chosen heat kernels by a set of eigenfunctions, by extracting the “leading terms”in their spectral expansion.

##### Step 2. Heat kernel and eigenfunctions.

Let Ave_{R}^{z} (*f*) = (* *_{BR(z)} |*f*|^{2})^{1/2}. We record the following (2):

### Proposition 5.

*Assume g ^{ij}* ∈ 𝒞

^{α}.

*There exists b*

_{1}< 1,

*that depends on d, c*

_{min},

*c*

_{max}, ∥

*g*∥

_{α⋀1}, α ⋀ 1

*such that the following holds. For an eigenfunction*ϕ

_{j}

*of*Δ

_{ℳ},

*corresponding to the eigenvalue*λ

_{j},

*and R*≤

*R*

_{z},

*the following estimates hold. For w*∈

*B*

_{b1R}(

*z*)

*and x, y*∈

*B*

_{b1R}(

*z*),

*with constants depending only on d, c*

_{max},

*c*

_{min}, ∥

*g*∥

^{ij}_{α⋀1},

*and P*

_{1}(

*x*) = (1 +

*x*)

^{(1/2)+β},

*P*

_{2}(

*x*) = (1 +

*x*)

^{(3/2)+β},

*P*

_{3}(

*x*) = (1 +

*x*)

^{(5/2)+β},

*with*β

*the smallest integer larger than or equal to*(

*d*−2)/4.

We start by restricting our attention to eigenfunctions do not have too high frequency. Let Λ_{L} (*A*) = {λ_{j} : λ_{j} ≤ *At*^{−1}} and Λ_{H} (*A′*) = {λ_{j} : λ_{j} > *A′**t*^{−1}} = Λ_{L} (*A′*)^{c}.

A first connection between the heat kernel and eigenfunc-tions is given by the following truncation Lemma.

### Lemma 1.

*Assume g* ∈ 𝒞^{2}. *Under Assumption A.1, for A* > 1 *large enough and A′* < 1 *small enough, depending on* δ_{0}, δ_{1}, *C*_{1}, *C*_{2}, *C′*_{1}, *C′*_{2} (*as in Proposition 4*), *there exist constants C*_{3}, *C*_{4} *(depending on A, A′ as well as {d, c*_{min}, *c*_{max}, ∥*g*∥_{α⋀1}, α ⋀ 1}) *such that*

*(i) The heat kernel is approximated by the truncated expansion**(ii) If*(1/2)δ_{0}*R*_{z}< |*z*−*w*|*and p is a unit vector parallel to z − w, then**(iii) C*_{3},*C*_{4}*both tend to*1*as A*→ ∞*and A′*→ 0.

This lemma implies that in the heat kernel expansion, we do not need to consider eigenfunctions corresponding to eigenval-ues larger than *At*^{−1}. However, in our search for eigenfunctions with the desired properties, we need to restrict our attention further, by discarding eigenfunctions that have too small a gradient around *z.* As a proxy for gradient, we use local energy. Recall Ave_{R}^{z} (*f*) = ( _{BR(z)} |*f*|^{2})^{1/2}, and let

The truncation *Lemma 1* can be strengthened into

### Lemma 2.

*Assume g* ∈ 𝒞^{2}. *Under Assumption A.1, for C*_{3}, *C*_{4} *close enough to* 1 *(as in Lemma 1), and c*_{0} *small enough (depending on d, c*_{min}, *c*_{max}, ∥*g*∥_{α⋀1}, α ⋀ 1, *and C*_{Weyl,ℳ}), *there exist constants C*_{5}, *C*_{6} *(depending only on C*_{3}, *C*_{4}, *c*_{0}, *and C*_{Weyl,ℳ}*) such that the heat kernel satisfies*
*and if* (1/2)δ_{0}*R*_{z} < |*z* − *w*|, *then, if* Λ := Λ_{L} (*A*) ∩ Λ_{H} (*A′*) ∩ Λ_{E} (*z, R*_{z}, δ_{0}, *c*_{0}),
*C*_{5}, *C*_{6} *tend to* 1 *as C*_{3}, *C*_{4} *tend to* 1 *and c*_{0} *tends to* 0.

##### Step 3.

Choosing appropriate eigenfunctions.

The set of eigenfunctions with eigenvalues in Λ (as in *Lemma 2*) is well suited for our purposes, in view of:

### Lemma 3.

*Assume g* ∈ 𝒞^{2}. *Under Assumption A.1*, *for* δ_{0} *small enough, there exists a constant C*_{7} *depending on* {*C*_{1}, *C*_{2}, *C′*_{1}, *C′*_{2}, *C*_{5}, δ_{1}} *and C*_{8} *depending on* {δ_{0}, *c*_{min}, *c*_{max}, ∥*g*∥_{α⋀1}, α ⋀ 1} *such that the following holds. For any direction p there exist j* ∈ Λ := Λ_{L} (*A*) ∩Λ_{H} (*A′*) ∩Λ_{E} (*z, R*_{z}, δ_{0}, *c*_{0}) *such that*
*and moreover, if* ∥*z* − *z′*∥ ≤ *b*_{1}*R*_{z}, *where b*_{1} *is a constant that depends on C*_{7}, *C*_{8}, *d, c*_{min}, *c*_{max}, ∥*g*∥_{α⋀1}, α ⋀ 1, *then*

This lemma yields an eigenfunction that serves our purpose in a given direction. From this point onwards we let, with abuse of notation, ϕ_{j}(*z′*) = (Ave_{½}^{z}δ_{0}R_{z}_{z} ϕ* _{j}*)

^{−1}· ϕ

_{j}(

*z′*). To complete the proof of the theorems, we need to cover

*d*linearly independent directions. Pick an arbitrary direction

*p*

_{1}. By

*Lemma 3*we can find

*j*

_{1}∈ Λ, (in particular

*j*

_{1}∼

*t*

^{−1}) such that |∂

_{pl}ϕ

_{jl}(

*z*)| ≥

*c*

_{0}

*R*

_{z}

^{−1}. Let

*p*

_{2}be a direction orthogonal to ∇ϕ

_{j1}(

*z*). We apply again

*Lemma 3*, and find

*j*

_{2}<

*At*

^{−1}so that |∂

_{p2}ϕ

_{j2}(

*z*)| ≥

*c*

_{0}

*R*

_{z}

^{−1}. Note that necessarily

*j*

_{2}≠

*j*

_{1}and

*p*

_{2}is linearly independent of

*p*

_{1}. In fact, by choice of

*p*

_{2}, ∂

_{p2}ϕ

_{j1}= 0. We proceed in this fashion. By induction, once we have chosen

*j*

_{1}, …,

*j*

_{k}(

*k*<

*d*), and the corresponding

*p*

_{1}, …,

*p*

_{k}, such that |∂

_{pl}ϕ

_{jl}(

*z*)| ≥

*c*

_{0}

*R*

_{z}

^{−1}, for

*l*= 1, …,

*k*, we pick

*p*

_{k+1}orthogonal to 〈{∇ϕ

_{jn}}

_{n=1,…,k}〉 and apply

*Lemma 3*, that yields

*j*

_{k+1}such that |∂

_{pk+1}ϕ

_{jk+1}(

*z*) | ≥

*c*

_{0}

*R*

_{z}

^{−1}.

We claim that the matrix *A*_{k+1} := (∂_{pn} ϕ_{jm})_{m,n=1,…,k+1} is lower triangular and {*p*_{1}, …, *p*_{k+1}} is linearly independent. Lower-triangularity of the matrix follows by induction and the choice of *p*_{k+1}. Assume *a* ∈ ℝ^{k+1} and Σ_{n=1}^{k+1} *a*_{n}*p*_{n} = 0, then 〈Σ_{n=1}^{k+1} *a*_{n}*p*_{n}, ∇ϕ_{jl}〉 = 0 for all *l* = 1, …, *k* + 1, i.e., *a* solves the linear system *A*_{k+1} *a* = 0. But *A*_{k+1} is lower triangular with all diagonal entries non-zero, hence *a* = 0.

For *l* ≤ *k*, we have 〈∇ϕ_{jl}, *p*_{k+1}〉 = 0 and, by *Lemma 3*, |〈∇ϕ_{jl}, *p*_{l}〉| ≳ *R*_{z}^{−1}. Now let Φ_{k} = (ϕ_{j1}, …, ϕ_{jk}) and Φ = Φ_{d}. We start by showing that ∥∇Φ|_{z} (*w* − *z*)∥ ≳_{d} 1/*R*_{z} ∥*w* − *z*∥. Indeed, suppose that ∥∇Φ_{k}|_{z} (*w* − *z*)∥ ≤ *c*/*R*_{z} ∥*w* − *z*∥, for all *k* = 1, …, *d.* For *c* small enough, this will lead to a contradiction. Let *w* − *z* = Σ_{l} *a*_{l}*p*_{l}. We have (using say *Lemma 3*)
By induction, |*a*_{k}| ≤ Σ_{l=1}^{k} *c*^{l} ∥*w* − *z*∥. For *c* small enough, |*a*_{i}| ≤ ∥*w* − *z*∥/*d*. This is a contradiction since ∥Σ_{i} *a*_{i}*p*_{i}∥ = ∥*w* − *z*∥ and ∥*p*_{i}∥ = 1. We also have, by *Proposition 5*,
Finally, by ensuring ∥*z* − *w*_{i}∥/*R*_{z} is smaller than a universal constant for *i* = 1, 2, we get from Eq. **0.16**
which proves the lower bound **0.5.** To prove the upper bound of **0.5,** we observe that from *Proposition 5* we have the upper bound |∂_{pl}ϕ_{il} (*z*)|≲ Ave_{Rz}^{z} (ϕ_{il}), and since ϕ_{il} is *L*^{2}-normalized, the right hand side can be as big as ∼ *R*_{z}^{−d/2}. Therefore, we can choose γ_{l} as in the statement of the theorem so as to satisfy the upper bound **0.5.** This completes the proof for the Euclidean case.

In the manifold case, we consider first the case *g* ∈ 𝒞^{2}, and thus let α ⋀ 1 = 1 in what follows. Let *R*_{z} be as in the theorem. We take *c*_{1} ≤ (1/2)δ_{0} chosen so that
for all *x* ∈ *B*_{2c1Rz} (*z*). For this *g*, the above is carried on in local coordinates. It is then left to prove that the Euclidean distance in the range of the coordinate map is equivalent to the geodesic distance on the manifold. For all *x, y* ∈ *B*_{c1}_{Rz} (*z*)
For the converse, let γ: [0, 1] → ℳ be the geodesic from *x* to *y*. γ is contained in *B*_{2dℳ(x,y)} (*x*) on the manifold, whose image in the local chart is contained in *B*_{2(1+∥g∥α⋀1)dℳ}_{(x,y)} (*x*). We have

Finally, when *g* ∈ 𝒞^{α} we will need:

### Lemma 4.

*Let J* > 0 *be given. If* ∥*g̃*_{n}^{il} − *g*^{il}∥_{L∞(BR(z))}→_{n} 0 *with* ∥*g̃*_{n}^{il}∥_{𝒞α} *uniformly bounded, then for j* < J
To conclude the proof of the theorem, let *J* = *c*_{5}*R*_{z}^{−2}, depending on *d*, (1/2)*c*_{min}, 2*c*_{max}, ∥*g*∥_{α⋀1}, α ⋀ 1. We may approximate *g* in 𝒞^{α} norm arbitrarily well by a 𝒞^{2} (ℳ) metric. By the above lemma, and our main theorem for the case of 𝒞^{2} metric, we obtain the theorem for the 𝒞^{α} case.

## Examples

##### Example 2. Mapping with eigenfunctions, non simply-connected domain.

We consider the planar, non-simply connected domain Ω in Fig. 1. We fix a point *z* ∈ Ω, as in the figure, and display two eigenfunctions whose existence is implied by *Theorem 1.*

##### Example 3. Localized eigenfunctions.

In this example, we show that the factors γ_{1}, …, γ_{d} in *Theorem 1* and *2* may in fact be required to be as small as *R*_{z}^{d/2}. We consider the “two-drums” domain in Fig. 2, consisting of a unit-size square drum, connected by a small aperture to a small square drum, with size τ/*N*, where τ is the golden ratio. The with of the connecting aperture is δτ/*N*, for small δ. For this domain, for small enough δ, and for *z* in the smaller square, it can be shown that all possible eigenfunctions that may get chosen in the theorem are localized in the smaller square This is essentially a consequence of the fact that the proper frequencies of the two drums, for δ = 0, are all irrational with respect to each other, and therefore eigenfunctions are perfectly localized on each drum. For δ small enough, a perturbation argument shows that the eigenfunctions will be essentially localized on each drum. But the eigenfunctions localized on the small drum, being normalized to *L*^{2} norm, will have *L*^{∞} norm as large as *R*_{z}^{−d/2}, and therefore the lower bound for the γ_{i}'s is sharp.

## Acknowledgments

We thank K. Burdzy, R. R. Coifman, P. Gressman, H. Smith, and A. D. Szlam for useful discussions during the preparation of the manuscript, as well as IPAM for hosting these discussions and more. P.W.J., M.M., and R.S. are grateful for partial support from, respectively, NSF DMS 0501300, NSF DMS 0650413 and ONR N0001407-1-0625, NSF DMS 0502747.

## Footnotes

- ↵
^{‡}To whom correspondence should be addressed. E-mail: mauro.maggioni{at}duke.edu

Author contributions: P.W.J., M.M., and R.S. designed research, performed research, analyzed data, and wrote the paper.

The authors declare no conflict of interest.

- Received September 3, 2007.

- © 2008 by The National Academy of Sciences of the USA

## References

- ↵.
- Coifman RR,
- Lafon S,
- Lee AB,
- Maggioni M,
- Nadler B,
- Warner F,
- Zucker SW

- ↵.
- Jones PW,
- Maggioni M,
- Schul R

- ↵.
- Roweis ST,
- Saul LK

- ↵.
- Belkin M,
- Niyogi P

- ↵
- ↵.
- Tenenbaum JB,
- de Silva V,
- Langford JC

- ↵.
- Zhang Z,
- Zha H

- ↵.
- Donoho DL,
- Grimes C

- ↵.
- Donoho DL,
- Grimes C

- ↵.
- Niyogi P,
- Matveeva I,
- Belkin M

- ↵.
- Szlam AD,
- Maggioni M,
- Coifman RR

- ↵.
- Mahadevan S,
- Maggioni M

- ↵
- ↵.
- Das P,
- Moll M,
- Stamati H,
- Kavraki LE,
- Clementi C

- ↵.
- Bérard P,
- Besson G,
- Gallot S

- ↵
- ↵
- ↵