Toward a spectral theory of cellular sheaves

Jakob Hansen; Robert Ghrist

doi:10.1007/s41468-019-00038-7

Toward a spectral theory of cellular sheaves

Hansen, Jakob; Ghrist, Robert 2019-08-30 00:00:00 This paper outlines a program in what one might call spectral sheaf theory—an exten- sion of spectral graph theory to cellular sheaves. By lifting the combinatorial graph Laplacian to the Hodge Laplacian on a cellular sheaf of vector spaces over a regular cell complex, one can relate spectral data to the sheaf cohomology and cell structure in a manner reminiscent of spectral graph theory. This work gives an exploratory intro- duction, and includes discussion of eigenvalue interlacing, sparsiﬁcation, effective resistance, synchronization, and sheaf approximation. These results and subsequent applications are prefaced by an introduction to cellular sheaves and Laplacians. Keywords Cohomology · Cellular sheaf theory · Spectral graph theory · Effective resistance · Eigenvalue interlacing Mathematics Subject Classiﬁcation MSC 55N30 · MSC 05C50 1 Introduction In spectral graph theory, one associates to a combinatorial graph additional algebraic structures in the form of square matrices whose spectral data is then investigated and related to the graph. These matrices come in several variants, most particularly degree and adjacency matrices, Laplacian matrices, and weighted or normalized versions thereof. In most cases, the size of the implicated matrix is based on the vertex set, while the structure of the matrix encodes data carried by the edges. Robert Ghrist ghrist@math.upenn.edu Jakob Hansen jhansen@math.upenn.edu Department of Mathematics, University of Pennsylvania, 209 S. 33rd St., Philadelphia, PA 19104-6395, USA Department of Electrical and Systems Engineering, University of Pennsylvania, 200 S. 33rd St., Philadelphia, PA 19104-6314, USA 123 316 J. Hansen , R. Ghrist To say that spectral graph theory is useful is an understatement. Spectral methods are key in such disparate ﬁelds as data analysis (Belkin and Niyogi 2003; Coifman and Lafon 2006), theoretical computer science (Hoory et al. 2006; Cvetcovic´ and Simic´ 2011), probability theory (Lyons and Peres 2016), control theory (Bullo 2018), numerical linear algebra (Spielman and Teng 2014), coding theory (Spielman 1996), and graph theory itself (Chung 1992; Brouwer and Haemers. 2012). Much of spectral graph theory focuses on the Laplacian, leveraging its unique com- bination of analytic, geometric, and probabilistic interpretations in the discrete setting. This is not the complete story. Many of the most well-known and well-used results on the spectrum of the graph Laplacian return features that are neither exclusively geometric nor even combinatorial in nature, but rather more qualitative. For example, it is among the ﬁrst facts of spectral graph theory that the multiplicity of the zero eigen- value of the graph Laplacian enumerates connected components of the graph, and the relative size of the smallest nonzero eigenvalue in a connected graph is a measure of approximate dis-connectivity. Such features are topological. There is another branch of mathematics in which Laplacians hold sway: Hodge theory. This is the slice of algebraic and differential geometry that uses Laplacians on (complex) Riemannian manifolds to characterize global features. The classical initial result is that one recovers the cohomology of the manifold as the kernel of the Laplacian on differential forms (Abraham et al. 1988). For example, the dimension of the kernel of the Laplacian on 0-forms (R-valued functions) is equal to the rank of H , the 0-th cohomology group (with coefﬁcients in R), whose dimension is the number of connected components. In spirit, then, Hodge theory categoriﬁes elements of spectral graph theory. Hodge theory, like much of algebraic topology, survives the discretization from Riemannian manifolds to (weighted) cell complexes (Eckmann 1945; Friedman 1998). The classical boundary operator for a cell complex and its formal adjoint combine to yield a generalization of the graph Laplacian which, like the Laplacian of Hodge theory, acts on higher dimensional objects (cellular cochains, as opposed to differential forms). The kernel of this discrete Laplacian is isomorphic to the cellular cohomology of the complex with coefﬁcients in the reals, generalizing the connectivity detection of the graph Laplacian in grading zero. As such, the spectral theory of the discrete Laplacian offers a geometric perspective on algebraic-topological features of higher- dimensional complexes. Laplacians of higher-dimensional complexes have been the subject of recent investigation (Parzanchevski 2013; Steenbergen 2013; Horak and Jost 2013). This is not the end. Our aim is a generalization of both spectral graph theory and discrete Hodge theory which ties in to recent developments in topological data analysis. The past two decades have witnessed a burst of activity in computing the homology of cell complexes (and sequences thereof) to extract robust global features, leading to the development of specialized tools, such as persistent homology, barcodes, and more, as descriptors for cell complexes (Carlsson 2012; Edelsbrunner and Harer 2010; Kaczynski et al. 2004; Otter et al. 2017). Topological data analysis is evolving rapidly. One particular direction of evolution concerns a change in perspective from working with cell complexes as topological spaces in and of themselves to focusing instead on data over a cell complex—viewing 123 Toward a spectral theory of cellular sheaves 317 the cell complex as a base on which data to be investigated resides. For example, one can consider scalar-valued data over cell complexes, as occurs in weighted networks and complexes; or sensor data, as occurs in target enumeration problems (Curry et al. 2012). Richer data involves vector spaces and linear transformations, as with recent work in cryo-EM (Hadani and Singer 2011) and synchronization problems (Bandeira 2015). Recent work in TDA points to a generalization of these and related data structures over topological spaces. This is the theory of sheaves. We will work exclusively with cellular sheaves (Curry 2014). Fix a (regular, locally ﬁnite) cell complex—a triangulated surface will sufﬁce for purposes of imagination. A cellular sheaf of vector spaces is, in essence, a data structure on this domain, assigning local data (in the form of vector spaces) to cells and compatibility relations (linear transformations) between cells of incident ascending dimension. These structure maps send data over vertices to data over incident edges, data over edges to data over incident 2-cells, etc. As a trivial example, the constant sheaf assigns a rank-one vector space to each cell and identity isomorphisms according to boundary faces. More interesting is the cellular analogue of a vector bundle: a cellular sheaf which assigns a ﬁxed vector space of dimension n to each cell and isomorphisms as linear transformations (with specializations to O(n) or SO(n) as desired). The data assigned to a cellular sheaf naturally arranges into a cochain complex graded by dimension of cells. As such, cellular sheaves possess a Laplacian that specializes to the graph Laplacian and the Hodge Laplacian for the constant sheaf. For cellular sheaves of real vector spaces, a spectral theory—an examination of the eigenvalues and eigenvectors of the sheaf Laplacian—is natural, motivated, and, to date, unexamined apart from a few special cases (see Sect. 3.6). This paper sketches an emerging spectral theory for cellular sheaves. Given the motivation as a generalization of spectral graph theory, we will often specialize to cellular sheaves over a 1-dimensional cell complex (that is, a graph, allowing when necessary multiple edges between a pair of vertices). This is mostly for the sake of simplicity and initial applications, as zero- and one-dimensional homological invari- ants are the most readily applicable. However, as the theory is general, we occasionally point to higher-dimensional side-quests. The plan of this paper is as follows. In Sect. 2, we cover the necessary topological and algebraic preliminaries, including deﬁnitions of cellular sheaves. Next, Sect. 3 gives deﬁnitions of the various matrices involved in the extension of spectral theory to cellular sheaves. Section 4 uses these to explore issues related to harmonic functions and cochains on sheaves. In Sect. 5, we extend various elementary results from spectral graph theory to cellular sheaves. The subsequent two sections treat more sophisticated topics, effective resistance (Sect. 6) and the Cheeger inequality (Sect. 7), for which we have some preliminary results. We conclude with outlines of potential applications for the theory in Sect. 8 and directions for future inquiry in Sect. 9. The results and applications we sketch are at the beginnings of the subject, and a great deal more in way of fundamental and applied work remains. This paper has been written in order to be readable without particular expertise in algebraic topology beyond the basic ideas of cellular homology and cohomology. Category-theoretic terminology is used sparingly and for concision. Given the well- earned reputation of sheaf theory as difﬁcult for the non-specialist, we have provided 123 318 J. Hansen , R. Ghrist an introductory section with terminology and core concepts, noting that much more is available in the literature (Bredon 1997; Kashiwara and Schapira 1990). Our recourse to the cellular theory greatly increases simplicity, readability, and applicability, while resonating with the spirit of spectral graph theory. There are abundant references available for the reader who requires more information on algebraic topology (Hatcher 2001), applications thereof (Edelsbrunner and Harer 2010;Ghrist 2014), and cellular sheaf theory (Curry 2014;Ghrist 2014). 2 Preliminaries 2.1 Cell complexes Deﬁnition 2.1 A regular cell complex is a topological space X with a partition into subspaces {X } satisfying the following conditions: α α∈P 1. For each x ∈ X, every sufﬁciently small neighborhood of x intersects ﬁnitely many X . 2. For all α, β, X ∩ X = ∅ only if X ⊆ X . α β β α 3. Every X is homeomorphic to R for some n . α α 4. For every α, there is a homeomorphism of a closed ball in R to X that maps the interior of the ball homeomorphically onto X . Condition (2) implies that the set P has a poset structure, given by β ≤ α iff X ⊆ X . This is known as the face poset of X. The regularity condition (4) implies β α that all topological information about X is encoded in the poset structure of P .For our purposes, we will identify a regular cell complex with its face poset, writing the incidence relation β α. The class of posets that arise in this way can be characterized combinatorially (Björner 1984). For our purposes, a morphism of cell complexes is a morphism of posets between their face incidence posets that arises from a continuous map between their associated topological spaces. In particular, morphisms of simplicial and cubical complexes will qualify as morphisms of regular cell complexes. The class of regular cell complexes includes simplicial complexes, cubical com- plexes, and so-called multigraphs (as 1-dimensional cell complexes). As nearly every space that can be characterized combinatorially can be represented as a regular cell complex, these will serve well as a default class of spaces over which to develop a combinatorial spectral theory of sheaves. We note that the spectral theory of complexes has heretofore been largely restricted to the study of simplicial complexes (Schaub et al. 2018). A number of our results will specialize to results about the spectra of Hodge Laplacians of regular cell complexes by restricting to the constant sheaf. A few notions associated to cell complexes will be useful. (k) Deﬁnition 2.2 The k-skeleton of a cell complex X, denoted X , is the subcomplex of X consisting of cells of dimension at most k. Deﬁnition 2.3 Let σ be a cell of a regular cell complex X. The star of σ , denoted st(σ ),isthe setofcells τ such that σ τ . 123 Toward a spectral theory of cellular sheaves 319 Topologically, st(σ ) is the smallest open collection of cells containing σ,arole we might denote as the “smallest cellular neighborhood” of σ . Stars serve an impor- tant purpose in giving combinatorial analogues of topological notions for maps. For instance, a morphism f : X → Y of cell complexes may be locally injective as deﬁned on the topological spaces. Topologically, the condition for local injectivity is simply that every point in X have a neighborhood on which f is injective. Translating this to cell complexes, we require that for every cell σ ∈ X, f is injective on st(σ ). Topological continuity ensures that the preimage of a star st(σ ) under a cell mor- phism f : X → Y is a union of stars; if f is locally injective, we see that it must be a disjoint union of stars. A locally injective map is, further, a covering map if on each −1 component of f (st(σ )), f is an isomorphism. That is, the ﬁber of a star consists of a disjoint union of copies of that star. 2.2 Cellular sheaves Let X be a regular cell complex. A cellular sheaf attaches data spaces to the cells of X together with relations that specify when assignments to these data spaces are consistent. Deﬁnition 2.4 A cellular sheaf of vector spaces on a regular cell complex X is an assignment of a vector space F (σ ) to each cell σ of X together with a linear transfor- mation F : F (σ ) → F (τ ) for each incident cell pair σ τ . These must satisfy σ τ both an identity relation F = id and the composition condition: σ σ ρ σ τ ⇒ F = F ◦ F . ρτ σ τ ρσ The vector space F (σ ) is called the stalk of F at σ . The maps F are called the σ τ restriction maps. For experts, this deﬁnition at ﬁrst seems only reminiscent of the notion of sheaves familiar to topologists. The depth of the relationship is explained in detail in Curry (2014), but the essence is this: the data of a cellular sheaf on X speciﬁes spaces of local sections on a cover of X given by open stars of cells. This translates in two different ways into a genuine sheaf on a topological space. One may either take the Alexandrov topology on the face incidence poset of the complex, or one may view the open stars of cells and their natural reﬁnements a basis for the topology of X. There then exists a natural completion of the data speciﬁed by the cellular sheaf to a constructible sheaf on X. One may compress the deﬁnition of a cellular sheaf to the following: If X is a regular cell complex with face incidence poset P , viewed as a category, a cellular sheaf is a functor F : P → Vect to the category of vector spaces over a ﬁeld k. X k Deﬁnition 2.5 Let F be a cellular sheaf on X.A global section x of F is a choice x ∈ F (σ ) for each cell σ of X such that x = F x for all σ τ . The space of σ τ σ τ σ global sections of F is denoted Γ(X ; F ). 123 320 J. Hansen , R. Ghrist Perhaps the simplest sheaf on any complex is the constant sheaf with stalk V, which we will denote V. This is the sheaf with all stalks equal to V and all restriction maps equal to the identity. 2.2.1 Cosheaves In many situations it is more natural to consider a dual construction to a cellular sheaf. A cellular cosheaf preserves stalk data but reverses the direction of the face poset, and with it, the restriction maps. Deﬁnition 2.6 A cellular cosheaf of vector spaces on a regular cell complex X is an assignment of a vector space F (σ ) to each cell σ of X together with linear maps F : F (τ ) → F (σ ) for each incident cell pair σ τ which satisﬁes the identity σ τ (F = id) and composition condition: σ σ ρ σ τ ⇒ F = F ◦ F . ρτ ρσ σ τ op More concisely, a cellular cosheaf is a functor P → Vect . The contravariant op functor Hom(•, k) : Vect → Vect gives every cellular sheaf F a dual cosheaf F whose stalks are Hom(F (σ ), k). 2.2.2 Homology and cohomology The cells of a regular cell complex have a natural grading by dimension. By regularity of the cell complex, this grading can be extracted from the face incidence poset as the height of a cell in the poset. This means that a cellular sheaf has a graded vector space of cochains C (X ; F ) = F (σ ). dim(σ )=k To develop this into a chain complex, we need a boundary operator and a notion of orientation—a signed incidence relation on P .Thisisamap [•:•]: P × P → X X X {0, ±1} satisfying the following conditions: 1. If [σ : τ ] = 0, then σ τ and there are no cells between σ and τ in the incidence poset. 2. For any σ τ , [σ : γ ][γ : τ]= 0. γ ∈P Given a signed incidence relation on P , there exist coboundary maps δ : k k+1 C (X ; F ) → C (X ; F ). These are given by the formula δ | = [σ : τ ]F , F (σ ) σ τ dim(τ )=k+1 or equivalently, (δ x ) = [σ : τ ]F (x ). τ σ τ σ dim(σ )=k 123 Toward a spectral theory of cellular sheaves 321 Here we use subscripts to denote the value of a cochain in a particular stalk; that is, x is the value of the cochain x in the stalk F (σ ). It is a simple consequence of the properties of the incidence relation and the com- k k−1 mutativity of the restriction maps that δ ◦ δ = 0, so these coboundary maps deﬁne a cochain complex and hence a cohomology theory for cellular sheaves. In particular, H (X ; F ) is naturally isomorphic to Γ(X ; F ), the space of global sections. An anal- ogous construction deﬁnes a homology theory for cosheaves. Cosheaf homology may be thought of as dual to sheaf cohomology in a Poincaré-like sense. That is, frequently the natural analogue of degree zero sheaf cohomology is degree n cosheaf homology. A deeper formal version of this fact, exploiting an equivalence of derived categories, may be found in Curry (2014), ch. 12. There is a relative version of cellular sheaf cohomology. Let A be a subcomplex of X. There is a natural subspace of C (X ; F ) consisting of cochains which vanish on stalks over cells in A. The coboundary of a cochain which vanishes on A also vanishes (k+1) (k) on A, since any cell in A has only cells in A on its boundary. We therefore get • • a subcomplex C (X , A; F ) of C (X ; F ). The cohomology of this subcomplex is the relative sheaf cohomology H (X , A; F ). The natural maps between these spaces of cochains constitute a short exact sequence of complexes • • • 0 → C (X , A; F ) → C (X ; F ) → C (A; F ) → 0, from which a long exact sequence for relative sheaf cohomology arises: 0 0 0 1 0 → H (X , A; F ) → H (X ; F ) → H (A; F ) → H (X , A; F ) → ··· 2.2.3 Sheaf morphisms Deﬁnition 2.7 If F and G are sheaves on a cell complex X, a sheaf morphism ϕ : F → G is a collection of maps ϕ : F (σ ) → G(σ ) for each cell σ of X, such that for any σ τ , ϕ ◦ F = G ◦ ϕ . Equivalently, all diagrams of the following form τ σ τ σ τ σ commute: F (σ ) G(σ ) F G σ τ σ τ F (τ ) G(τ ) This commutativity condition assures that a sheaf morphism ϕ : F → G induces maps k k k ϕ : C (X ; F ) → C (X ; G) which commute with the coboundary maps, resulting in k k k the induced maps on cohomology H ϕ : H (X ; F ) → H (X ; G). 2.2.4 Sheaf operations There are several standard operations that act on sheaves to produce new sheaves. Deﬁnition 2.8 (Direct sum)If F and G are sheaves on X, their direct sum F ⊕ G is a sheaf on X with (F ⊕ G)(σ ) = F (σ ) ⊕ G(σ ). The restriction maps are (F ⊕ G) = σ τ F ⊕ G . σ τ σ τ 123 322 J. Hansen , R. Ghrist Deﬁnition 2.9 (Tensor product)If F and G are sheaves on X, their tensor product F ⊗ G is a sheaf on X with (F ⊗ G)(σ ) = F (σ ) ⊗ G(σ ). The restriction maps are (F ⊗ G) = F ⊗ G . σ τ σ τ σ τ Deﬁnition 2.10 (Pullback)If f : X → Y is a morphism of cell complexes and F ∗ ∗ is a sheaf on Y,the pullback f F is a sheaf on X with f F (σ ) = F ( f (σ )) and ( f F ) = F . σ τ f (σ ) f (τ ) Deﬁnition 2.11 (Pushforward) The full deﬁnition of the pushforward of a cellular sheaf is somewhat more categorically involved than the previous constructions. If f : X → Y is a morphism of cell complexes and F is a sheaf on X,the pushforward f F is a sheaf on Y with stalks f F (σ ) given as the limit lim F (τ ).The ∗ ∗ σ f (τ ) restriction maps are induced by the restriction maps of F, since whenever σ σ ,the cone for the limit deﬁning f F (σ ) contains the cone for the limit deﬁning f F (σ ), ∗ ∗ inducing a unique map f F (σ ) → f F (σ ). ∗ ∗ In this paper, we will mainly work with pushforwards over locally injective cell maps, that is, those whose geometric realizations are locally injective (see Sect. 2.1). If f : X → Y is locally injective, every cell σ ∈ X maps to a cell of the same −1 dimension, and for every cell σ ∈ Y , f (st(σ )) is a disjoint union of subcomplexes, each of which maps injectively to Y . In this case, f F (σ ) −1 F (σ ), and σ ∈ f (σ ) ( f F ) = −1 F . This computational formula in fact holds σ τ σ τ (σ τ )∈ f (σ τ) −1 more generally, if the stars of cells in f (σ ) are disjoint. Those familiar with the deﬁnitions of pushforward and pullback for sheaves over topological spaces will note a reversal of fates when we deﬁne sheaves over cell complexes. Here the pullback is simple to deﬁne, while the pushforward is more involved. This complication arises because cellular sheaves are in a sense deﬁned pointwise rather than over open sets. 3 Deﬁnitions 3.1 Weighted cellular sheaves Let k = R or C. A weighted cellular sheaf is a cellular sheaf with values in k- vector spaces where the stalks have additionally been given an inner product structure. Adding the condition of completeness to the stalks, one may view this as a functor P → Hilb , where Hilb is the category whose objects are Hilbert spaces over k X k k and whose morphisms are (bounded) linear maps. The inner products on stalks of F extend by the orthogonal direct sum to inner products on C (X ; F ), making these Hilbert spaces as well. The canonical inner products on direct sums and subspaces of Hilbert spaces give the direct sum and tensor product of weighted cellular sheaves weighted structures. Similarly, the pullbacks and pushforwards (over locally injective maps) of a weighted sheaf have canonical weighted structures given by their computational formulae in Sect. 2.2.4. Every morphism T : V → W between Hilbert spaces admits an adjoint map T : W → V , determined by the property that for all v ∈ V ,w ∈ W , w, T v=T w, v. 123 Toward a spectral theory of cellular sheaves 323 ∗ ∗ One may readily check that (T ) = T . This fact gives the category Hilb a dagger structure, that is, a contravariant endofunctor † (here the adjoint operation ) which acts as the identity on objects and squares to the identity. In a dagger category, the notion of unitary isomorphisms makes sense: they are the invertible morphisms T † −1 such that T = T . The dagger structure of Hilb introduces some categorical subtleties into the study of weighted cellular sheaves. The space of global sections of a cellular sheaf is deﬁned in categorical terms as the limit of the functor X → Vect deﬁning the sheaf. This deﬁnes the space of global sections up to unique isomorphism. We might want a weighted space of global sections to be a sort of limit in Hilb which is deﬁned up to unique unitary isomorphism. This is the notion of dagger limit, recently studied in Heunen and Karvonen (2019). Unfortunately, this work showed that Hilb does not have all dagger limits; in particular, pullbacks over spans of noninjective maps do not exist. As a result, there is no single canonical way to deﬁne an inner product on the space of global sections of a cellular sheaf F. There are two approaches that seem most natural, however. One is to view the space of global sections of F as ker δ with the natural inner product given by inclusion into C (X ; F ). The other is to view global sections as lying in F (σ ). We will generally take the view that global sections are a subspace of C (X ; F ); that is, we will weight Γ(X ; F ) by its canonical isomorphism with H (X ; F ), as deﬁned in Sect. 3.2. The dagger structure on Hilb gives a slightly different way to construct a dual cosheaf from a weighted cellular sheaf F. Taking the adjoint of each restriction map reverses their directions and hence yields a cosheaf with the same stalks as the original sheaf. From a categorical perspective, this amounts to composing the functor F with the dagger endofunctor on Hilb . When stalks are ﬁnite dimensional, this dual cosheaf is isomorphic to the cosheaf F deﬁned in Sect. 2.2.1 via the dual vector spaces of stalks. In this situation, we have an isomorphism between the stalks of F and its dual cosheaf. This is reminiscent of the bisheaves recently introduced by MacPherson and Patel (2018). However, the structure maps F (σ ) → F (σ ) will rarely commute with the restriction and extension maps as required by the deﬁnition of the bisheaf—this only holds in general if all restriction maps are unitary. The bisheaf construction is meant to give a generalization of local systems, and as such ﬁts better with our discussion of discrete vector bundles in Sect. 3.5. 3.2 The sheaf Laplacian 0 1 Given a chain complex of Hilbert spaces C → C → ··· we can construct the ∗ 2 ∗ ∗ Hodge Laplacian Δ = (δ + δ ) = δ δ + δδ . This operator is naturally graded k k k k k ∗ k k−1 k−1 ∗ into components Δ : C → C , with Δ = (δ ) δ + δ (δ ) . This operator can be further separated into up- (coboundary) and down- (boundary) Laplacians k k ∗ k k k−1 k−1 ∗ Δ = (δ ) δ and Δ = δ (δ ) respectively. + − ∗ ⊥ A key observation is that on a ﬁnite-dimensional Hilbert space, ker δ = (im δ) . ∗ ∗ For if δ x = 0, then for all y,0 =δ x , y=x,δy, so that x ⊥ im δ. This allows us to express the kernels and images necessary to compute cohomology purely in terms of kernels. This is the content of the central theorem of discrete Hodge theory: 123 324 J. Hansen , R. Ghrist 0 1 Theorem 3.1 Let C → C → ··· be a chain complex of ﬁnite-dimensional Hilbert k k k • spaces, with Hodge Laplacians Δ . Then ker Δ H (C ). k • k k−1 Proof By deﬁnition, H (C ) = ker δ / im δ . In a ﬁnite dimensional Hilbert space, k k−1 k−1 k ker δ / im δ is isomorphic to the orthogonal complement of im δ in ker δ , k k−1 ⊥ k k−1 ∗ which we may write (ker δ ) ∩ (im δ ) = (ker δ ) ∩ (ker(δ ) ). So it sufﬁces to k k k−1 ∗ k k ∗ k k show that ker Δ = (ker δ ) ∩ (ker(δ ) ). Note that ker δ = ker(δ ) δ = ker Δ k k k k k and similarly for Δ . So we need to show that ker(Δ + Δ ) = ker Δ ∩ ker Δ , − + − + − k k k k ∗ which will be true if im Δ ∩im Δ = 0. But this is true because im Δ = im(δ ) = + − + k ⊥ k k−1 k (ker δ ) and im Δ = im δ ⊆ ker δ . The upshot of this theorem is that the kernel of Δ gives a set of canonical represen- k • tatives for elements of H (C ). This is commonly known as the space of harmonic k • cochains, denoted H (C ). In particular, the proof above implies that there is an k k k−1 k ∗ orthogonal decomposition C = H ⊕ im δ ⊕ im(δ ) . When the chain complex in question is the complex of cochains for a weighted cellular sheaf F, the Hodge construction produces the sheaf Laplacians. The Laplacian which is easiest to study and most immediately interesting is the degree-0 Laplacian, which is a generalization of the graph Laplacian. We can represent it as a symmetric block matrix with blocks indexed by the vertices of the complex. The entries on 0 ∗ the diagonal are Δ = F F and the entries on the off-diagonal are ve v,v ve ve 0 ∗ Δ =−F F , where e is the edge between v and u. Laplacians of other ve u,v ue degrees have similar block structures. The majority of results in combinatorial spectral theory have to do with up- Laplacians. We will frequently denote these L by analogy with spectral graph theory, where L typically denotes the (non-normalized) graph Laplacian. In particular, we will further elide the index k when k = 0, denoting the graph sheaf Laplacian by simply L. A subscript will be added when necessary to identify the sheaf, e.g. L or Δ . Weighted labeled graphs are in one-to-one correspondence with graph Laplacians. The analogous statement is not true of sheaves on a graph. For instance, the sheaves in Fig. 1 have coboundary maps with matrix representations ⎡ ⎤ ⎡ ⎤ 1 1 1 −1 √ √ 2 2 ⎣ ⎦ ⎣ ⎦ and , 3 3 2 2 which means that the Laplacian for each is equal to 2 −1 −12 However, these sheaves are not unitarily isomorphic, as can be seen immediately by checking the stalk dimensions. More pithily, one cannot hear the shape of a sheaf. One source of the lossiness in the sheaf Laplacian representation is that restriction maps may be the zero morphism, effectively allowing for edges that are only attached to one 123 Toward a spectral theory of cellular sheaves 325 Fig. 1 Two nonisomorphic sheaves with the same Laplacian vertex. More generally, restriction maps may fail to be full rank, which means that it is impossible to identify the dimensions of edge stalks from the Laplacian. 3.2.1 Harmonic cochains k k The elements of ker Δ = H are known as harmonic k-cochains. More generally, a k-cochain may be harmonic on a subcomplex: Deﬁnition 3.2 A k-cochain x of a sheaf F on a cell complex X is harmonic onaset S of k-cells if (Δ x )| = 0. When k = 0 and F is the constant sheaf (i.e., in spectral graph theory), this can be expressed as a local averaging property: For each v ∈ S, x = x , where ∼ v u u∼v indicates adjacency and d is the degree of the vertex v. 3.2.2 Identifying sheaf Laplacians Given a regular cell complex X and a choice of dimension for each stalk, one can identify the collection of matrices which arise as coboundary maps for a sheaf on X as those matrices satisfying a particular block sparsity pattern. This sparsity pattern controls the number of nonzero blocks in each row of the matrix. Restricting to δ , we get a matrix whose rows have at most two nonzero blocks. The space of matrices which arise as sheaf Laplacians is then the space of matrices which have a factorization L = δ δ, where δ is a matrix satisfying this block sparsity condition. Boman et al. studied this class of matrices when the blocks have size 1 ×1, calling them matrices of factor width two (Boman et al. 2005). They showed that this class coincides with the class of symmetric generalized diagonally dominant matrices, those matrices L for which there exists a positive diagonal matrix D such that DL D is diagonally dominant. Indeed, the fact that sheaves on graphs are not in general determined by their Laplacians is in part a consequence of the nonuniqueness of width-two factorizations. 123 326 J. Hansen , R. Ghrist 3.3 Approaching infinite-dimensional Laplacians The deﬁnitions given in this paper are adapted to the case of sheaves of ﬁnite dimen- sional Hilbert spaces over ﬁnite cell complexes. Relaxing these ﬁniteness constraints introduces new complications. The spaces of cochains naturally acquire inner products by taking the Hilbert space direct sum. These are not the same as taking the algebraic direct sum or product of stalks. However, there is a sequence of inclusions of complexes • 2 • • C (X ; F ) ⊆ L C (X ; F ) ⊆ C (X ; F ) inducing algebraic maps between the corresponding compactly supported, L , and standard sheaf cohomology theories. The theory of abstract complexes of possibly inﬁnite-dimensional Hilbert spaces has been developed in Brüning and Lesch (1992). This paper explains conditions for the spaces of harmonic cochains of a complex to be isomorphic with the algebraic cohomology of the complex. A particularly nice condition is that the complex have ﬁnitely generated cohomology, which implies that the total coboundary map is a Fredholm operator. More generally, if the images of the coboundary and its adjoint are closed, the spaces of harmonic cochains will be isomorphic to the cohomology. Further issues arise when we consider the coboundary maps δ . For spectral pur- poses, it is in general desirable for these to be bounded linear maps, for which we must make some further stipulations. Sufﬁcient conditions for coboundary maps to be bounded are as follows: Proposition 3.3 Let F be a sheaf of Hilbert spaces on a cell complex X. Suppose that there exists some M such that for every pair of cells σ τ with dim σ = k and dim τ = k + 1, F ≤ M . Further suppose that every k-cell in X has at most σ τ k d cofaces of dimension k + 1, and every (k + 1)-cell in X has at most d faces of k+1 dimension k. Then δ is a bounded linear operator. Proof We compute: ⎛ ⎞ k 2 k 2 ⎝ ⎠ δ x = (δ x ) ≤ F x τ σ τ σ dim τ =k+1 dim τ =k+1 σ τ ⎛ ⎞ 2 2 ⎝ ⎠ ≤ M x ≤ M d x k σ k+1 σ dim τ =k+1 σ τ dim τ =k+1 σ τ 2 2 2 k 2 2 k 2 = M d x ≤ M d d x = M d d x . k+1 σ k+1 σ k+1 k k k dim σ =k σ τ dim σ =k k k+1 k k ∗ k k k ∗ If δ is bounded, its associated Laplacians Δ = (δ ) δ and Δ = δ (δ ) + − are also bounded. As bounded self-adjoint operators, their spectral theory is relatively 123 Toward a spectral theory of cellular sheaves 327 unproblematic. Their spectra consist entirely of approximate eigenvalues, those λ for which there exists a sequence of unit vectors {x } such that Δ x − λx → 0. k k k If δ is not just bounded, but compact, the Laplacian spectral theory becomes even nicer. In this situation, the spectrum of Δ has no continuous part, and hence consists purely of eigenvalues. An appropriate decay condition on norms of restriction maps ensures compactness. Proposition 3.4 Let F be a sheaf of Hilbert spaces on a cell complex X. Suppose that for all σ τ with dim σ = k and dim τ = k + 1, the restriction map F for is σ τ compact, and further that F < ∞. Then δ is a compact linear operator. σ τ σ τ F Proof It is clear that δ cannot be compact if any one of its component restriction maps fails to be compact. Suppose ﬁrst that all restriction maps are ﬁnite rank, and ﬁx an ordering of (k + 1)-cells of X, deﬁning the orthogonal projection operators i k+1 k+1 P : C (X ; F ) → C (X ; F ) sending stalks over (k + 1) cells of index greater i k than i to zero. Then P δ is a ﬁnite-rank operator and i k k P δ − δ ≤ F , σ τ j >i σ τ which goes to zero as i →∞. In the case that the restriction maps are compact but not ﬁnite rank, pick an approximating sequence for each by ﬁnite rank maps and combine the two approximations. k k An important note is that when C (X ; F ) is inﬁnite dimensional and δ is compact with ﬁnite dimensional kernel, the eigenvalues of Δ will accumulate at zero. This means that there will be no smallest nontrivial eigenvalue for such Laplacians. Most of the difﬁculties considered here already arise in the study of spectra of inﬁnite graphs. The standard Laplacian associated to an inﬁnite graph is bounded but not compact, while a proper choice of weights decaying at inﬁnity makes it compact. The study of sheaves of arbitrary Hilbert spaces on not-necessarily-ﬁnite cell com- plexes is interesting, and indeed suggests itself in certain applications. However, for the initial development and exposition of the theory, we have elected to focus on the (still quite interesting) ﬁnite-dimensional case. This is sufﬁcient for most applications we have envisioned, and avoids the need for repeated qualiﬁcations and restrictions. For the balance of this paper, we will assume that all cell complexes are ﬁnite and all vector spaces are ﬁnite dimensional, giving where possible proofs that generalize in some way to the inﬁnite-dimensional setting. Most results that do not explicitly require a ﬁnite complex will extend quite directly to the case of sheaves with com- pact coboundary operators. Proofs not relying on the Courant-Fischer theorem will typically apply even to situations where coboundary operators are merely bounded, although their conclusions may be somewhat weakened. 3.4 The normalized Laplacian and weights Many results in spectral graph theory rely on a normalized version of the standard graph Laplacian, which is typically deﬁned in terms of a rescaling of the standard 123 328 J. Hansen , R. Ghrist Laplacian. Let D be the diagonal matrix whose nonzero entries are the degrees of ver- −1/2 −1/2 tices; then the normalized Laplacian is L = D LD . This deﬁnition preserves the Laplacian as a symmetric matrix, but it obscures the true meaning of the normal- ization. The normalized Laplacian is the standard Laplacian with a different choice of −1/2 −1/2 −1 weights for the vertices. The matrix D LD is similar to D L, which is self adjoint with respect to the inner product x , y= x Dy. In this interpretation, each vertex is weighted proportionally to its degree. Viewing the normalization process as a reweighting of cells leads to the natural deﬁnition of normalized Laplacians for simplicial complexes given by Horak and Jost (2013). Indeed, following Horak and Jost’s deﬁnition for simplicial complexes, we propose the following extension to sheaves. Deﬁnition 3.5 Let F be a weighted cellular sheaf deﬁned on a regular cell complex X.Wesay F is normalized if for every cell σ of X and every x , y ∈ F (σ ) ∩ (ker δ) , δx,δy=x , y. Lemma 3.6 Given a weighted sheaf F on a ﬁnite-dimensional cell complex X, it is always possible to reweight F to a normalized version. Proof Note that if X has dimension k, the normalization condition is trivially satisﬁed for all cells σ of dimension k. Thus, starting at cells of dimension k −1, we recursively redeﬁne the inner products on stalks. If σ is a cell of dimension k − 1, let Π be the orthogonal projection F (σ ) → F (σ )∩ker δ. Then deﬁne the normalized inner product N N •, • on F (σ ) to be given by x , y =δ(id −Π )x,δ(id −Π )y+Π x,Π y. σ σ σ σ σ σ It is clear that this reweighted sheaf satisﬁes the condition of Deﬁnition 3.5 for cells of dimension k and k − 1. We may then perform this operation on cells of progressively lower dimension to obtain a fully normalized sheaf. Note that there is an important change of perspective here: we do not normalize the Laplacian of a sheaf, but instead normalize the sheaf itself, or more speciﬁcally, the inner products associated with each stalk of the sheaf. If we apply this process to a sheaf F on a graph G, there is an immediate inter- pretation in terms of the original sheaf Laplacian. Let D be the block diagonal of the standard degree 0 sheaf Laplacian, and note that for x ⊥ ker L, x , Dx is the reweighted inner product on C (G; F ). In particular, the adjoint of δ with † T † respect to this inner product has the form D δ , where D is the Moore-Penrose pseudoinverse of D, so that the matrix form of the reweighted Laplacian with respect to this inner product is D L. Changing to the standard basis then gives †/2 †/2 L = D LD . 3.5 Discrete vector bundles A subclass of sheaves of particular interest are those where all restriction maps are invertible.These sheaves have been the subject of signiﬁcantly more study than the general case, since they extend to locally constant sheaves on the geometric realization of the cell complex. The Riemann-Hilbert correspondence describes an equivalence between locally constant sheaves (or cosheaves) on X, local systems on 123 Toward a spectral theory of cellular sheaves 329 X, vector bundles on X with a ﬂat connection, and representations of the funda- mental groupoid of X. (See, e.g., Davis and Kirk 2001, ch. 5 or Zein and Snoussi 2009 for a discussion of some aspects of this correspondence.) When we represent a local system by a cellular sheaf or cosheaf, we will call it a discrete vector bun- dle. One way to understand the space of 0-cochains of a discrete vector bundle is as representing a subspace of the sections of a geometric realization of the associated ﬂat vector bundle, deﬁned by linear interpolation over higher-dimensional cells. The coboundary map can be seen as a sort of discretization of the connection, whose ﬂatness is manifest in the fact that δ = 0. Discrete vector bundles have some subtleties when we study their Laplacians. The sheaf-cosheaf duality corresponding to a local system, given by taking inverses of restriction maps, is not in general the same as the duality induced by an inner product on stalks. Indeed, these duals are only the same when the restriction maps are unitary— their adjoints must be their inverses. The inner product on stalks of a cellular sheaf has two roles: it gives a rel- ative weight to vectors in each stalk, but via the restriction maps also gives a relative weight to cells in the complex. This second role complicates our inter- pretation of certain sorts of vector bundles. For instance, one might wish to deﬁne an O(n) discrete vector bundle on a graph to be a cellular sheaf of real vector spaces where all restriction maps are orthogonal. However, from the per- spective of the degree-0 Laplacian, a uniform scaling of the inner product on an edge does not change the orthogonality of the bundle, but instead in some sense changes the length of the edge, or perhaps the degree of emphasis we give to discrepancies over that edge. So a discrete O(n)-bundle should be one where the restriction maps on each cell are scalar multiples of orthonormal maps. That is, for each cell σ , we have a positive scalar α , such that for every σ τ,the restriction map F is an orthonormal map times α /α . One way to think of this τ σ σ τ is as a scaling of the inner product on each stalk of F. Frequently, especially when dealing with graphs, we set α = 1 when dim(σ ) = 0, but this is not necessary. (Indeed, when dealing with the normalized Laplacian of a graph, we have α = d .) The rationale for this particular deﬁnition is that in the absence of a basis, inner products are not absolutely deﬁned, but only in relation to maps in or out of a space. Scaling the inner product on a vector space is meaningless except in relation to a given collection of maps, which it transforms in a uniform way. As a special case of this deﬁnition, it will be useful to think about weighted ver- sions of the constant sheaf. These are isomorphic to the ‘true’ constant sheaf, but not unitarily so. Weighted constant sheaves on a graph are analogous to weighted graphs. The distinction between the true constant sheaf and weighted versions arises because it is often convenient to think of the sections of a cellular sheaf as a sub- space of C (X ; F ). As a result, we often only want our sections to be constant on 0-cells, allowing for variation up to a scalar multiple on higher-dimensional cells. This notion will be necessary in Sect. 8.6 when we discuss approximations of cellular sheaves. 123 330 J. Hansen , R. Ghrist 3.6 Comparison with previous constructions Friedman, in Friedman (2015), gave a deﬁnition of a sheaf on a graph, developed a homology theory, and suggested constructing sheaf Laplacians and adjacency matri- ces. The suggestion that one might develop a spectral theory of sheaves on graphs has remained until now merely a suggestion. The graph connection Laplacian, introduced by Singer and Wu in Singer and Wu (2012), is simply the sheaf Laplacian of an O(n)-vector bundle over a graph. This construction has attracted signiﬁcant interest from a spectral graph theory perspec- tive, including the development of a Cheeger-type inequality (Bandeira et al. 2013) and a study of random walks and sparsiﬁcation (Chung and Zhao 2012). Connection Laplacian methods have proven enlightening in the study of synchronization problems. Others have approached the study of vector bundles, and in particular line bundles, over graphs without reference to the connection Laplacian, studying analogues of spanning trees and the Kirchhoff theorems (Kenyon 2011; Catanzaro et al. 2013). Other work on discrete approximations to connection Laplacians of manifolds has analyzed similar matrices (Mantuano 2007). Gao, Brodski, and Mukherjee developed a formulation in which the graph connec- tion Laplacian is explicitly associated to a ﬂat vector bundle on the graph and arises from a twisted coboundary operator (Gao et al. 2016). This coboundary operator is not a sheaf coboundary map and has some difﬁculties in its deﬁnition. These arise from a lack of freedom to choose the basis for the space of sections over an edge of the graph. Further work by Gao uses a sheaf Laplacian-like construction to study noninvertible correspondences between probability distributions on surfaces (Gao 2016). Wu et al. (2018) have recently proposed a construction they call a weighted simpli- cial complex and studied its associated Laplacians. These are cellular cosheaves where all stalks are equal to a given vector space and restriction maps are scalar multiples of the identity. Their work discusses the cohomology and Hodge theory of weighted simplicial complexes, but does not touch on issues related to the Laplacian spectrum. 4 Harmonicity As a prelude to results about the spectra of sheaf Laplacians, we will discuss issues related to harmonic cochains on sheaves. While these do not immediately touch on the spectral properties of the Laplacian, they are closely bound with its algebraic properties. 4.1 Harmonic extension Proposition 4.1 Let X be a regular cell complex with a weighted cellular sheaf F. Let B ⊆ X be a subcomplex and let x | ∈ C (B; F ) be an F-valued k-cochain speciﬁed k k on B. If H (X , B; F ) = 0, then there exists a unique cochain x ∈ C (X ; F ) which restricts to x | on B and is harmonic on S = X \B. In our terminology, Friedman’s sheaves are cellular cosheaves. 123 Toward a spectral theory of cellular sheaves 331 Proof A matrix algebraic formulation sufﬁces. Representing Δ in block form as partitioned by B and S, the relevant equation is k k Δ (S, S)Δ (S, B) x | 0 F F = . k k Δ (B, S)Δ (B, B) x | y F F Since y is indeterminate, we can ignore the second row of the matrix, giving the k k k k ∗ k equation Δ (S, S)x | + Δ (S, B)x | = 0. We can write Δ (S, S) = (δ | ) δ | + S B S S F F F k−1 ∗ ∗ k−1 ∗ ((δ ) | ) (δ ) | , which is very close to the k-th Hodge Laplacian of the relative S S cochain complex k−1 k k+1 ··· → C (X , B; F ) → C (X , B; F ) → C (X , B; F ) → ··· . Indeed, we can exploit the fact that this is a subcomplex of C (X ; F ) to compute its Hodge Laplacian in terms of the coboundary maps of C (X ; F ). The coboundary map • • δ of C (X , B; F ) is simply the restriction of the coboundary map δ of C (X ; F ) to k+1 k k k k k the subcomplex: δ = π δ i , where π is the orthogonal projection C (X ; F ) → S S S S k k k k k k C (X , B; F ) and i the inclusion C (X , B; F ) → C (X ; F ). Note that π and i are S S S k−1 k k adjoints, and that i π is the identity on im δ . We may therefore write the Hodge S S S Laplacian of the relative complex as k k ∗ k k−1 k−1 ∗ Δ (X , B; F ) = (δ ) δ + δ (δ ) S S S S k k ∗ k+1 k+1 k k k k−1 k−1 k−1 k−1 ∗ k = π (δ ) i π δ i + π δ i π (δ ) i S S S S S S S S k k ∗ k k k k−1 k−1 k−1 k−1 ∗ k = π (δ ) δ i + π δ i π (δ ) i . S S S S S S Meanwhile, we can write the submatrix k k k ∗ k k k k−1 k−1 ∗ k Δ (S, S) = π (δ ) δ i + π δ (δ ) i . F S S S S k k k It is then immediate that ker(Δ (S, S)) ⊆ ker Δ (X , B; F ), so that Δ (S, S) is F F invertible if H (X , B; F ) = 0. If we restrict to up- or down-Laplacians, a harmonic extension always exists, even k ∗ k k ∗ k if it is not unique. This is because, for instance, im(δ | ) δ | ⊆ im(δ | ) δ | .In S B S S particular, this implies that harmonic extension is always possible for 0-cochains, with uniqueness if and only if H (X , B; F ) = 0. 4.2 Kron reduction Kron reduction is one of many names given to a process of simplifying graphs with respect to the properties of their Laplacian on a boundary. If G is a con- nected graph with a distinguished set of vertices B, which we consider as a sort of boundary of G, Proposition 4.1 shows that there is a harmonic extension map B V (G) E : R → R . It is then possible to construct a graph G on B such that for 123 332 J. Hansen , R. Ghrist every function x on the vertices of G ,wehave L x = π L E (x ), where π is G B G B V (G) B the orthogonal projection map R → R . Indeed, letting S = V (G)\B,wehave −1 E (x )| =−L (S, S) L (S, B)x,so S G G −1 L x = π L E (x ) = L (B, B)x − L (B, S)L (S, S) L (S, B)x . B G G G G G Therefore, −1 L = L (B, B) − L (B, S)L (S, S) L (S, B), G G G G G that is, L is the Schur complement of the (B, B) block of L . It is also the Laplacian G G of a graph on B: Theorem 4.2 (see (Dörﬂer and Bullo 2013)) If L is the Laplacian of a con- nected graph G, and B a subset of vertices of G, then L = L (B, B) − G G −1 L (B, S)L (S, S) L (S, B) is the Laplacian of a graph with vertex set B. G G G A physically-inspired way to understand this result (and a major use of Kron reduc- tion in practice) is to view it as reducing a network of resistors given by G to a smaller network with node set B that has the same electrical behavior on B as the original net- work. In this guise, Kron reduction is a high-powered version of the Y -Δ and star-mesh transforms familiar from circuit analysis. Further discussion of Kron reduction and its various implications and applications may be found in Dörﬂer and Bullo (2013). Can we perform Kron reduction on sheaves? That is, given a sheaf F on a graph G with a prescribed boundary B, can we ﬁnd a sheaf F on a graph with vertex set B only such that for every x ∈ C (B; F ) we have L x = π 0 L E (x ), where B F F C (B;F ) B B E (x ) is the harmonic extension of x to G? The answer is, in general, no. Suppose we want to remove the vertex v from our graph, i.e., B = G\{v}.Let D = F F = L . To eliminate the vertex v ve v,v ve ve v we apply the condition (L (x , E (x )))(v) = 0, and take a Schur complement, −1 replacing L(B, B) with L(B, B) − L(B,v)D L(v, B). This means that we add to ∗ −1 ∗ the entry L(w, w ) the map F F D F F , where e is the edge between ve w e we ve v and w, and e the edge between v and w . This does not in general translate to a change in the restriction maps for the edge between w and w . In general, Kron reduction is not possible for sheaves. In particular, if x ∈ C (G; F ) is a section of F, its restriction to B must be a section of F . Conversely, if x is not a section, its restriction to B cannot be a section of F . B B But we can construct sheaves with a space of sections on the boundary that cannot be replicated with a sheaf on the boundary vertices only. For instance, take the star graph with three boundary vertices, with stalks R over boundary vertices and edges, and R over the internal vertex. Take as the restriction maps from the central vertex restriction onto the ﬁrst and second components, and addition of the two components. See Fig. 2 for an illustration. Note that a global section of this sheaf is determined by its value on the central vertex. If we label the boundary vertices counterclockwise starting at the top, the space of global sections for F must have as a basis 123 Toward a spectral theory of cellular sheaves 333 Fig. 2 A sheaf illustrating the general impossibility of Kron reduction ⎡ ⎤ ⎡ ⎤ 1 1 ⎣ ⎦ ⎣ ⎦ x = 1 , x = 0 . 1 2 0 1 But there is no sheaf on a graph with vertex set B which has this space of global sections. To see this, note that if x is a section, the map from F (v ) to F (v ) must be the zero 1 1 3 map, and similarly for the map from F (v ) to F (v ). Similarly, if x is a section, the 2 3 2 maps F (v ) → F (v ) and F (v ) → F (v ) must be zero. But this already shows that 1 2 3 2 the vector 10 0 must be a section, giving F a three-dimensional space of sections. The problem is that the internal node allows for constraints between boundary nodes that cannot be expressed by purely pairwise interactions. This fact is a fundamental obstruction to Kron reduction for general sheaves. However, there is a sheaf Kron reduction for sheaves with vertex stalks of dimension at most 1. This follows from the identiﬁcation of the Laplacians of such sheaves as the matrices of factor width two in Sect. 3.2.2. Theorem 4.3 The class of matrices of factor width at most two is closed under taking Schur complements. Proof By Theorems 8 and 9 of Boman et al. (2005), a matrix L has factor width at most two if and only if it is symmetric and generalized weakly diagonally dominant with nonnegative diagonal, that is, there exists a positive diagonal matrix D such that DL D is weakly diagonally dominant. Equivalently, these are the symmetric positive semideﬁnite generalized weakly diagonally dominant matrices. The class of gener- alized weakly diagonally dominant matrices coincides with the class of H-matrices, which are shown to be closed under Schur complements in Johnson and Smith (2005). Similarly, the class of symmetric positive deﬁnite matrices is closed under Schur complements, so the intersection of the two classes is also closed. 123 334 J. Hansen , R. Ghrist 4.3 Maximum modulus theorem Harmonic 0-cochains of an O(n)-bundle satisfy a local averaging property which leads directly to a maximum modulus principle. Lemma 4.4 Let G be a graph with an O(n)-bundle F, with constant vertex weights α = 1 and arbitrary edge weights α (as deﬁned in Sect. 3.5).If x ∈ C (G; F ) is v e harmonic at a vertex v, then x = F F x , v we w ve v,we v=w 2 2 where d = F = α . v ve ve ve e Proof The block row of L corresponding to v has entries −F F off the diago- F we ve nal and F F = F id on the diagonal. The harmonicity ve ve F (v) ve ve ve condition is then d x − F F x = 0. v v we w ve v,we v=w Theorem 4.5 (Maximum modulus principle) Let G be a graph, and B be a thin subset of vertices of G; that is, G\B is connected, and every vertex in B is connected to a vertex not in B. Let F be an O(n)-bundle on G with a = 1 for all v ∈ G, and suppose x ∈ C (G; F ) is harmonic on G\B. Then if x attains its maximum stalkwise norm at a vertex in G\B, it has constant stalkwise norm. Proof Note that for a given edge e = v ∼ w, F and F are both α times an ve ue e ∗ 2 orthogonal map, so F F is α times an orthogonal map. Let v ∈ G\B and we ve suppose x ≥x for all w ∈ G. Then this holds in particular for neighbors of v, v w so that we have 1 1 ∗ ∗ x = F F x ≤ F F x v we w we w ve ve d d v v v,we v,we v=w v=w 1 1 2 2 = α x ≤ α x =x , w v v e e d d v v v,we ve v=w Equality holds throughout, which, combined with the assumption that x ≥x v w for all w, forces x =x for w ∼ v. We then apply the same argument to every v w vertex in G\B adjacent to v, and, after iterating, the region of constant stalkwise norm extends to all of G\B because this subgraph is connected. But since every vertex b ∈ B 123 Toward a spectral theory of cellular sheaves 335 is adjacent to some vertex w ∈ G\B, the same argument applied to the neighborhood of w forces x =x . So any harmonic function that attains its maximum modulus b w on G\B has constant modulus. Corollary 4.6 Let B be a thin subset of vertices of G, and F an O(n)-bundle on G as before. If x ∈ C (G; F ) is harmonic on G\B, then it attains its maximum modulus on B. The constant sheaf on a graph is an O(n)-bundle, so this result gives a maximum modulus principle for harmonic functions on the vertices of a graph. A slightly stronger result in this vein, involving maxima and minima of x, is discussed in Sunada (2008). The thinness condition for B is not strictly necessary for the corollary to hold—there are a number of potential weakenings of the condition. For instance, we might simply require that there exists some w ∈ B such that for every vertex v ∈ G\B there exists a path from v to w not passing through B. 5 Spectra of sheaf Laplacians The results in this section are straightforward generalizations and extensions of familiar results from spectral graph theory. Most are not particularly difﬁcult, but they illustrate the potential for lifting nontrivial notions from graphs and complexes to sheaves. It is useful to note a few basic facts about the spectra of Laplacians arising from Hodge theory. Proposition 5.1 The nonzero spectrum of Δ is the disjoint union of the nonzero spec- k k tra of Δ and Δ . + − Proof We take advantage of the Hodge decomposition, noting that C (X ; F ) = k k k ker Δ ⊕ im Δ ⊕ im Δ . This is an orthogonal decomposition, and = 0as well − + k k as Δ | k = 0. Further, since ker Δ = ker Δ ∩ ker Δ , both restrict to + − (im Δ ) k k zero on the kernel of Δ . We therefore see that Δ is the orthogonal direct sum k k k 0| k ⊕ Δ | k ⊕ Δ | k , and hence the spectrum of Δ is the union of the ker Δ + (im Δ ) − (im Δ ) + − spectra of these three operators. k+1 Proposition 5.2 The nonzero eigenvalues of Δ and Δ are the same. + − k+1 k k ∗ k k k ∗ Proof We have Δ = (δ ) δ and Δ = δ (δ ) . The eigendecompositions of + − these matrices are determined by the singular value decomposition of δ , and the nonzero eigenvalues are precisely the squares of the nonzero singular values of δ . One reason for the study of the normalized graph Laplacian is that its spectrum is bounded above by 2 (Chung 1992), and hence normalized Laplacian spectra of different graphs can be easily compared. A similar result holds for up-Laplacians of normalized simplicial complexes (Horak and Jost 2013): the eigenvalues of the degree- k up-Laplacian of a normalized simplicial complex are bounded above by k + 2. This fact extends to normalized sheaves on simplicial complexes. This result and others in this paper will rely on the Courant-Fischer theorem, which we state here for reference. 123 336 J. Hansen , R. Ghrist Deﬁnition 5.3 Let A be a self-adjoint operator on a Hilbert space V.If x ∈ V,the Rayleigh quotient corresponding to x and A is x , Ax R (x ) = . x , x Theorem 5.4 (Courant-Fischer) Let A beann × n Hermitian matrix with eigenvalues λ ≤ λ ≤ ··· ≤ λ . Then 1 2 n λ = min max R (x ) = max min R (x ). k A A dim V =k x ∈V dim V =n−k+1 x ∈V The proof is immediate once one uses the fact that A is unitarily equivalent to a diagonal matrix. Proposition 5.5 Suppose F is a normalized sheaf on a simplicial complex X. The eigenvalues of the degree k up-Laplacian L are bounded above by k + 2. Proof By the Courant-Fischer theorem, the largest eigenvalue of L is equal to k k x , L x δ x,δ x max = max k k k k x ∈C (X ;F ) x , x x ⊥ker δ δ x ,δ x σ σ dim σ =k [σ : τ ][σ : τ ]F x , F x σ τ σ σ τ σ dim τ =k+1 σ,σ τ = max . F x , F x x ⊥ker δ σ τ σ σ τ σ dim σ =k σ τ Note that for σ = σ , [σ : τ ][σ : τ ]F x , F x ≤F x F x σ τ σ σ τ σ σ τ σ σ τ σ 2 2 ≤ F x +F x σ τ σ τ σ by the Cauchy-Schwarz inequality. In particular, then, the term of the numerator cor- responding to each τ of dimension k + 1 is bounded above by 2 2 2 F x + F x +F x σ τ σ σ τ σ σ τ σ σ τ σ =σ τ = (k + 2) F x , σ τ σ σ τ by counting the number of times each term F x appears in the sum. Meanwhile, σ τ σ the denominator is equal to F x , so the Rayleigh quotient σ τ σ dim τ =k+1 σ τ is bounded above by k + 2. 123 Toward a spectral theory of cellular sheaves 337 5.1 Eigenvalue interlacing Deﬁnition 5.6 Let A, B be n × n matrices with real spectra. Let λ ≤ λ ≤ ··· ≤ λ 1 2 n be the eigenvalues of A and μ ≤ μ ≤ ··· ≤ μ be the eigenvalues of B.We 1 2 n say the eigenvalues of A are (p, q)-interlaced with the eigenvalues of B if for all k, λ ≤ μ ≤ λ .(We let λ = λ for k < 1 and λ = λ for k > n.) k− p k k+q k 1 k n The eigenvalues of low-rank perturbations of symmetric positive semideﬁnite matri- ces are related by interlacing. The following is a standard result: Theorem 5.7 Let A and B be positive semideﬁnite matrices, with rank B = t. Then the eigenvalues of A are (t , 0)-interlaced with the eigenvalues of A − B. Proof Let μ be the k-th largest eigenvalue of A − B and λ the k-th largest eigenvalue k k of A. By the Courant-Fischer theorem, we have y, Ay−y, By μ = min max dim Y =k y∈Y ,y=0 y, y y, Ay ≥ min max dim Y =k y∈Y ∩ker B,y=0 y, y y, Ay ≥ min max = λ k−t dim Y =k−t y∈Y ,y=0 y, y and y, Ay λ = min max dim Y =k y∈Y ,y=0 y, y y, Ay−y, By ≥ min max = μ . dim Y =k y∈Y ,y=0 y, y This result is immediately applicable to the spectra of sheaf Laplacians under the deletion of cells from their underlying complexes. The key part is the interpretation of the difference of the two Laplacians as the Laplacian of a third sheaf. Let F be a sheaf on X, and let C be an upward-closed set of cells of X, with Y = X \C.The inclusion map i : Y → X induces a restriction of F onto Y , the pullback sheaf i F. k k Consider the Hodge Laplacians Δ and Δ .If C contains cells of dimension k, F i F these matrices are different sizes, but we can derive a relationship by padding Δ i F with zeroes. Equivalently, this is the degree-k Laplacian of F with the restriction maps incident to cells in C set to zero. Proposition 5.8 Let G be the sheaf on X with the same stalks as F but with all restriction maps between cells not in C set to zero. The eigenvalues of Δ i F k k are (t , 0)-interlaced with the eigenvalues of Δ , where t = codim H (X ; G) = k k dim C (X ; F ) − dim H (X ; G). Such subtle moves are part and parcel of a sheaf-theoretic perspective. 123 338 J. Hansen , R. Ghrist Similar results can be derived for the up- and down-Laplacians. Specializing to graphs, interlacing is also possible for the normalized degree 0 sheaf Laplacian. The Rayleigh quotient for the normalized Laplacian L ∗ is i F −1/2 −1/2 x , D L ∗ D x y, L ∗ y y, L y−y, L y ∗ i F ∗ i F F G i F i F = = , x , x y, D ∗ y y, D y−y, D y i F F G −1/2 where we let y = D x. Then if {λ } are the ordered eigenvalues of L and {μ } ∗ k F k i F are the ordered eigenvalues of L ,wehave i F y, L y−y, L y F G μ = min max dim Y =k y∈Y ,y=0 y, D y−y, D y F G y, L y ≥ min max dim Y =k y, D y−y, D y y∈Y ∩H (X ;G),y=0 F G y, L y ≥ min max dim Y =k y, D y y∈Y ∩H (X ;G),y=0 y, L y ≥ min max = λ k−t dim Y =k−t y∈Y ,y=0 y, D y y, L y−y, L y F G μ = max min dim Y =n−k+1 y∈Y ,y=0 y, D y−y, D y F G y, L y ≤ max min dim Y =n−k+1 y, D y−y, D y y∈Y ∩H (X ;G),y=0 F G y, L y ≤ max min dim Y =n−k+1 y, D y y∈Y ∩H (X ;G),y=0 y, L y ≤ max min = λ k+t dim Y =n−k−t +1 y∈Y ,y=0 y, D y Therefore, the eigenvalues of the normalized Laplacians are (t , t )-interlaced. This generalizes interlacing results for normalized graph Laplacians. 5.2 Sheaf morphisms Proposition 5.9 Suppose ϕ : F → G is a morphism of weighted sheaves on a regular k+1 k k ∗ k k cell complex X. If ϕ is a unitary map, then L = (ϕ ) L ϕ . F G k+1 F G k F ∗ k+1 ∗ k+1 Proof The commutativity condition ϕ δ = δ ϕ implies that (δ ) (ϕ ) ϕ F k ∗ G ∗ G k k ∗ k k k+1 ∗ k+1 δ = (ϕ ) (δ ) δ ϕ = (ϕ ) L ϕ . Thus if (ϕ ) ϕ = id ,wehave k+1 C (X ;F ) k k ∗ k k k+1 L = (ϕ ) L ϕ . This condition holds if ϕ is unitary. F G An analogous result holds for the down-Laplacians of F, and these combine to a result for the full Hodge Laplacians. 123 Toward a spectral theory of cellular sheaves 339 5.3 Cell complex morphisms The following constructions are restricted to locally injective cellular morphisms, as discussed in Sect. 2.1. Recall that under these morphisms, cells map to cells of the same dimension and the preimage of the star of a cell is a disjoint union of subcomplexes, on each of which the map acts injectively. The sheaf Laplacian is invariant with respect to pushforwards over such maps: Proposition 5.10 Let X and Y be cell complexes, and let f : X → Y bealocally injective cellular morphism. If F is a sheaf on X, the kth coboundary Laplacian corresponding to f F on Y is the same (up to a unitary change of basis) as the kth coboundary Laplacian of F on X. Corollary 5.11 The sheaves F and f F are isospectral for the coboundary Laplacian. k k Proof There is a canonical isometry f : C (X , F ) → C (Y , f F ), which is given k ∗ on stalks by the obvious inclusion f : F (σ ) → f F ( f (σ )) = F (τ ). σ ∗ f (τ )= f (σ ) For σ σ , f commutes with the restriction map F and hence f commutes with σ σ σ k the coboundary map. But this implies that: k k ∗ k k ∗ ∗ k ∗ k ∗ k ∗ k L = (δ ) δ = (δ ) f f δ = f (δ ) δ f = f L f . (k+1) k k f F f F f F f F (k+1) f F k F F k F ∗ ∗ ∗ ∗ ∗ General locally injective maps behave nicely with sheaf pushforwards, and covering maps behave well with sheaf pullbacks. Recall that a covering map of cell complexes is a locally injective map f : C → X such that for every cell σ ∈ X, f is an −1 isomorphism on the disjoint components of f (st(σ )). Proposition 5.12 Let f : C → X be a covering map of cell complexes, with F a sheaf k k on X. Then for any k, the spectrum of L is contained in the spectrum of L . F f F k k ∗ Proof Consider the lifting map ϕ : C (X ; F ) → C (C ; f F ) given by x → x ◦ f . This map commutes with δ and δ . The commutativity with δ follows immediately from the proof of the contravariant functoriality of cochains. The commutativity with δ is more subtle, and relies on the fact that f is a covering map. k ∗ k+1 For y ∈ C (C ; f F ) and x ∈ C (X ; F ),wehave ∗ ∗ y,δ ϕx=δy,ϕx= [σ : τ ] f F (y ), (ϕx ) σ τ σ τ σ ,τ ∈P σ τ = [σ : τ ] F (y ), x σ τ σ τ −1 σ,τ ∈P X σ ∈ f (σ ) σ τ = [σ : τ ]F (ϕ y) , x σ τ σ τ σ,τ ∈P σ τ ∗ ∗ =δϕ y, x=y,ϕδ x . 123 340 J. Hansen , R. Ghrist k k k k k k ∗ ∗ Now, if L x = λx,wehave L ϕx = (δ ) δ ϕx = ϕ(δ ) δ x = ∗ ∗ ∗ F f F f F f F F F k k ϕL x = λϕx,so λ is an eigenvalue of L . F f F Even if f : Y → X is not quite a covering map, it is still possible to get some information about the spectrum of f F. For instance, for dimension-preserving cell maps with uniform ﬁber size we have a bound on the smallest nontrivial eigenvalue of the pullback: Proposition 5.13 Suppose f : Y → Xis a dimension-preserving map of regular −1 cell complexes such that for dim(σ ) = d, f (σ ) = is constant, and let F be a sheaf on X. If λ (F ) is the smallest nontrivial eigenvalue of L , then λ (F ) ≥ k k d ∗ λ ( f F ). d+1 Proof Let x be an eigenvector corresponding to λ (F ). Note that since every ﬁber is the same size, the lift ϕ preserves the inner product up to a scaling. That is, if y and z are d-cochains, ϕy,ϕz= y, z. This means that the pullback of x is orthogonal to the pullback of any cochain in the kernel of L . Therefore, we have δx,δx ϕδx,ϕδx δϕx,δϕx d d d λ (F ) = = = ≥ λ ( f F ). k k x , x ϕx,ϕx ϕx,ϕx d+1 d+1 d+1 5.4 Product complexes If X and Y are cell complexes, their product X × Y is a cell complex with cells σ × τ for σ ∈ X, τ ∈ Y , and incidence relations (σ × τ)(σ × τ ) whenever σ σ and τ τ . The dimension of σ × τ is dim(σ ) + dim(τ ). The complex X × Y possesses projection maps π and π onto X and Y . X Y Deﬁnition 5.14 If F and G are sheaves on X and Y , respectively, their product is the ∗ ∗ sheaf F G = π F ⊗ π G. Equivalently, we have (F G)(σ × τ) = F (σ ) ⊗ F (τ ) X Y and (F G) = F ⊗ G . σ ×τ σ ×τ σ σ τ τ Proposition 5.15 If L and L are the degree-0 Laplacians of F and G, the degree-0 F G Laplacian of F G is L = id 0 ⊗L + L ⊗ id 0 . F G G F C (X ;F ) C (Y ;G) Proof The vector space C (X × Y ; F G) has a natural decomposition into two subspaces: one generated by stalks of the form F (v) ⊗ G(e) for v avertexof X and e an edge of Y , and another generated by stalks of the opposite form F (e) ⊗ G(v).This induces an isomorphism 1 0 1 1 0 C (X × Y ; F G) = (C (X ; F ) ⊗ C (Y ; G)) ⊕ (C (X ; F ) ⊗ C (Y ; G)). Then the coboundary map of F G can be written as the block matrix id ⊗δ C (X ;F ) δ = . F G δ ⊗ id C (Y ;G) 123 Toward a spectral theory of cellular sheaves 341 ∗ ∗ ∗ A quick computation then gives L = δ δ = id ⊗δ δ + δ δ ⊗ F G F G G F C (X ;F ) F G G F id 0 = id 0 ⊗L + L ⊗ id 0 . G F C (Y ;G) C (X ;F ) C (Y ;G) Corollary 5.16 If the spectrum of L is {μ } and the spectrum of L is {λ } , then i i j j F G the spectrum of L is {μ + λ } . i j ij F G For higher degree Laplacians, this relationship becomes more complicated. For instance, the degree-1 up-Laplacian is computed as follows: ⎡ ⎤ id 0 ⊗δ 0 C (X ;F ) ⎢ ⎥ 0 0 δ = δ ⊗ id 1 id 1 ⊗δ . ⎣ ⎦ C (Y ;G) C (X ;F ) F G F G 0 δ ⊗ id C (Y ;G) 1 0 0 ∗ 0 id 0 ⊗L + L ⊗ id 1 (δ ) ⊗ δ C (X ;F ) C (Y ;G) 1 G F F G L = . F G 0 0 0 1 δ ⊗ (δ ) id 1 ⊗L + L ⊗ id 0 C (X ;F ) C (Y ;G) F G G F Because L is given by a block matrix in terms of various Laplacians and cobound- F G ary maps of F and G, computing its spectrum is more involved. When X and Y are graphs, this simpliﬁes signiﬁcantly and it is possible to compute the spectrum in terms of the spectra of F and G. Proposition 5.17 Suppose X and Y are graphs, with F and G sheaves on X and Y . 0 0 If v is an eigenvector of L with eigenvalue λ and v an eigenvector of L with F G F G λ 0 v ⊗ δ v F G μ G eigenvalue μ, then the vector v = is an eigenvector of L F G F G δ v ⊗ v F G λ F with eigenvalue λ + μ. Proof A computation. ⎡ ⎤ λ 0 0 0 ∗ 0 v ⊗ δ v L ⊗ id 1 (δ ) ⊗ δ F G μ G C (Y ;G) 1 F F G ⎣ ⎦ L v = F G F G 0 0 0 δ ⊗ (δ ) id 1 ⊗L 0 C (X ;F ) δ v ⊗ v F G G F G λ F ⎡ ⎤ ⎡ ⎤ λ 0 λ 0 + λv ⊗ δ v v ⊗ δ v F G F G μ λ G μ G ⎢ ⎥ ⎣ ⎦ = (λ + μ) ⎣ ⎦ λ μ 0 μ 0 + μδ v ⊗ v δ v ⊗ v F G F G μ λ F λ F A simpler way to obtain nearly the same result is to recall from Proposition 5.2 that 1 ∗ 1 1 1 ∗ (δ ) δ and δ (δ ) have the same spectrum up to the multiplicity of F G F G F G F G zero. But when X and Y are graphs, 1 1 ∗ 1 1 δ (δ ) = (Δ ) ⊗ id + id ⊗(Δ ) , 1 1 F G − C (Y ;G) C (X ;F ) − F G F G 123 342 J. Hansen , R. Ghrist 1 0 and since the nonzero eigenvalues of (Δ ) are the same as those of L , we obtain 1 0 a correspondence between eigenvalues of L and sums of eigenvalues of L and F G F L . However, for higher-dimensional complexes and higher-degree Laplacians, there appears to be no general simple formula giving the spectrum of F G in terms of the spectra of F and G. Indeed, we suspect that no such formula can exist, i.e., that the spectrum of F G is not in general determined by the spectra of F and G. 6 Eﬀective resistance Effective resistance is most naturally deﬁned for weighted cosheaves, but since every weighted sheaf has a canonical dual weighted cosheaf, the following deﬁnition applies to weighted sheaves as well. Deﬁnition 6.1 Let F be a cosheaf on a cell complex X, and let a, b ∈ ker(∂ ) be k F homologous k-cycles. The effective resistance R (a, b) is given by the solution to eff the optimization problem min c s.t. ∂ c = b − a. (6.1) k+1 c∈C (X ;F ) k+1 Proposition 6.2 Cosheaf effective resistance may be computed by the formula k † k ∗ R (a, b) =b − a,(L ) (b − a), where L is the up Laplacian ∂ ∂ . eff k+1 k+1 F F † † † ∗ Proof By a standard result about matrix pseudoinverses, (L ) = (∂ ) ∂ ,so k+1 k+1 † † † k † 2 b − a,(L ) (b − a)=∂ (b − a), ∂ (b − a)=∂ (b − a) .But if F k+1 k+1 k+1 b − a ∈ im ∂ , then ∂ (b − a) is the minimizer of the optimization problem (6.1). k+1 k+1 The condition that a and b be homologous becomes trivial if H (X ; F ) = 0. Note that if F is the constant cosheaf on a graph, a 0-cycle supported on a vertex v is homologous to a 0-cycle supported on a vertex w if their values are the same. This means that the deﬁnition of cosheaf effective resistance recovers the deﬁnition of graph effective resistance. For any cosheaf on a cell complex, we can get a measure of effective resistance over a (k +1)-cell σ by using the boundary map restricted to σ . Any choice of c ∈ F (σ ) gives an equivalence class of pairs of homologous k-cycles supported inside the boundary of σ . That is, we can decompose ∂c into the sum of two k-cycles in a number of equivalent ways. For instance, if σ is a 1-simplex with two distinct incident vertices, there is a natural decomposition of ∂c into a sum of two 0-cycles, one supported on each vertex. This gives a quadratic form on F (σ ): R (σ )(x ) =∂x , L ∂x . The choice eff of decomposition does not affect the quadratic form. Of course, by the inner product pairing, this quadratic form can be represented as a matrix (∂| ) L ∂| .In F (σ ) F (σ ) particular, this deﬁnes a matrix-valued effective resistance over an edge for a cosheaf on a graph. 123 Toward a spectral theory of cellular sheaves 343 6.1 Sparsification Graph effective resistance has also attracted attention due to its use in graph sparsiﬁ- cation. The goal when sparsifying a graph G is to ﬁnd a graph H with fewer edges that closely preserves properties of G. One important property we might wish to preserve is the size of boundaries of sets of vertices. If S is a set of vertices, we let |∂ S| be the sum of the weights of edges between S and its complement. We can compute this in terms of the Laplacian of G: |∂ S| = 1 L 1 , where 1 is the indicator vector on the G S S set S.If H well approximates G in this sense, we would like to have a relation like T T T (1 − )1 L 1 ≤ 1 L 1 ≤ (1 + )1 L 1 for every set S of vertices. Indeed, we G S H S G S S S S could strengthen this condition by requiring this to hold for all vectors in C (G; R), not just indicators of sets of vertices. The resulting relationship between the Laplacians of G and H is described by the Loewner order on positive semideﬁnite matrices. Deﬁnition 6.3 The Loewner order on the cone of symmetric positive deﬁnite matrices of size n × n is given by the relation A B if B − A is positive semideﬁnite. T T n Equivalently, A B if and only if x Ax ≤ x Bx for all x ∈ R . By the Courant-Fischer theorem, the relation A B has important implications for the eigenvalues and eigenvectors of these matrices. In particular, λ (B) ≥ λ (A) max max and λ (A) ≤ λ (B).If (1−)A B (1+)B, the eigenvalues and eigenvectors min min of B are constrained to be close to those of A. Thus, it is appropriate to call this relationship a spectral approximation of A by B. Spielman and Srivastava famously used effective resistances to construct spectral sparsiﬁers of graphs (Spielman and Srivastava 2008). This approach extends to sheaves on graphs: just as graph Laplacians can be spectrally approximated by Laplacians of sparse graphs, so too can sheaf Laplacians be spectrally approximated by Laplacians of sheaves on sparse complexes. Theorem 6.4 Let X be a regular cell complex of dimension d and F a cosheaf on X with dim C (X ; F ) = n. Given > 0 there exists a subcomplex X ⊆ X with the d−1 −2 same (d − 1)-skeleton and O( n log n) d-cells, together with a cosheaf F on X d−1 d−1 d−1 such that (1 − )L L (1 + )L . F F F d−1 Proof If ker L = 0, then an equivalent condition to the conclusion is 1 1 d−1 − d−1 d−1 − 2 2 λ ((L ) L (L ) ) ≤ 1 + max F F F and 1 1 d−1 − d−1 d−1 − 2 2 λ ((L ) L (L ) ) ≥ 1 − . min F F F d−1 d−1 If ker L is nontrivial, we use the pseudoinverse of L and restrict to the F F orthogonal complement of the kernel. This only offers notational difﬁculties, so in the following we will calculate as if the kernel were trivial. 123 344 J. Hansen , R. Ghrist Consider the restrictions of ∂ to each d-cell σ , and note that ∗ d−1 (∂ | )(∂ | ) = L . d σ d σ dim(σ )=d For each d-cell σ , we will choose σ to be in X with probability −2 p = min(1, 4 log(n) tr(R (σ ))). σ eff If σ is chosen to be in X , we choose its extension maps to be F = F . σ • σ • p Let A be independent Bernoulli random variables with E[A ]= p and let σ σ σ 1 1 1 d−1 d−1 − ∗ − 2 2 X = A (L ) (∂ | )(∂ | ) (L ) . Note that by construction X = σ σ d σ d σ σ p F F 1 1 d−1 − d−1 d−1 − 2 2 (L ) L (L ) and F F F 1 1 d−1 − d−1 d−1 − 2 2 E X = (L ) L (L ) = id σ C (X ;F ) d−1 F F F We wish to show that the eigenvalues of X are close to those of its expectation, for which we use a matrix Chernoff bound proven in Tropp (2012). This bound requires a bound on the norms of X : 1 1 1 d−1 d−1 − ∗ − 2 2 X ≤ (L ) (∂ | )(∂ | ) (L ) σ d σ d σ F F 1 1 1 d−1 − ∗ d−1 − 2 2 ≤ tr((L ) (∂ | )(∂ | ) (L ) ) d σ d σ F F 1 tr(R (σ )) eff ∗ d−1 † ≤ tr((∂| ) (L ) ∂ ) = . σ σ p p σ σ We can apriori subdivide any X with p = 1 into sufﬁciently many independent σ σ random variables so that their norms are as small as necessary. This does not affect the hypotheses of the concentration inequality, so we consider the case where p < 1, where X ≤ . Our matrix Chernoff bound then gives 4log n 1 1 −4 d−1 − d−1 d−1 − −2 −1 2 2 P λ ((L ) L (L ) ) ≤ 1 − ≤ n exp log n = n min F F F 1 1 −4 d−1 − d−1 d−1 − −2 −1/3 2 2 P λ ((L ) L (L ) ) ≥ 1 + ≤ n exp log n = n . max F F F When n is not trivially small there is therefore a high probability of L - approximating L . 123 Toward a spectral theory of cellular sheaves 345 We now check the expected number of d-cells in X .Thisis −2 p ≤ 4 log n tr(R (σ )), σ eff σ σ and ∗ d−1 −1 d−1 −1 ∗ tr(R (σ )) = tr((∂| ) (L ) ∂| ) = tr((L ) ∂ (∂| ) ) eff σ σ σ σ F F σ σ σ d−1 −1 ∗ d−1 −1 d−1 = tr (L ) ∂ (∂| ) = tr((L ) L ) ≤ n. σ σ F F F A standard Chernoff bound argument with the Bernoulli random variables determin- ing whether each cell is included then shows that the number of d-cells is concentrated −2 around its expectation and thus can be chosen to be O( n log n). The proof given here follows the outline of the proof for graphs given by Spielman in Spielman (2015). This newer proof simpliﬁes the original proof in Spielman and Srivastava (2008), which used a sampling of edges with replacement. Theorem 6.4 generalizes a number of theorems on sparsiﬁcation of graphs and simplicial complexes (Spielman and Teng 2011; Chung and Zhao 2012; Osting et al. 2017); however, it is not the most general sparsiﬁcation theorem. Indeed, the core argument does not rely on the cell complex structure, but only on the decomposition of the Laplacian into a sum of matrices, one corresponding to each cell. More general, and stronger, theorems about sparsifying sums of symmetric positive semideﬁnite matrices have been proven, such as the following from De Carli Silva et al. (2016): Theorem 6.5 (De Carli Silva et al. 2016) Let B ,..., B be symmetric, positive 1 m semideﬁnite matrices of size n × n and arbitrary rank. Set B := B . For any ∈ (0, 1), there is a deterministic algorithm to construct a vector y ∈ R with O(n/ ) nonzero entries such that y is nonnegative and B y B (1 + )B. i i i =1 3 2 The algorithm runs in O(mn / ) time. Moreover, the result continues to hold if the input matrices B ,..., B are Hermitian and positive semideﬁnite. 1 m The sheaf theoretic perspective, though not the most general or powerful possible, nevertheless maintains both a great deal of generality along with a geometric interpreta- tion of sparsiﬁcation in terms of an effective resistance. This geometric interpretation may then be pursued to develop efﬁcient methods for approximating the effective resistance and hence fast algorithms for sparsiﬁcation of cell complexes and cellular sheaves atop them. 123 346 J. Hansen , R. Ghrist 7 The Cheeger inequality 7.1 The Cheeger inequality for O(n)-bundles Recall from Sect. 3.5 the notion of an O(n)-bundle on a graph. Bandeira, Singer, and Spielman proved an analogue to the graph Cheeger inequality for O(n)-bundles (Ban- deira et al. 2013). Their goal was to give guarantees on the performance of a spectral method for ﬁnding an approximate section to a principal O(n)-bundle over a graph. For an O(n)-bundle on a graph with Laplacian L, degree matrix D and normalized −1/2 −1/2 Laplacian L = D LD , they deﬁned the frustration of a 0-cochain x to be x , Lx x , Lx η(x ) = = , x , Dx x , x and showed that any 0-cochain can be rounded to one with controlled frustration as follows. Given a 0-cochain x and a threshold κ ≥ 0, let x be the cochain whose value at a vertex v is x /x if x ≥ κ and is zero otherwise. For any such x there v v v exists a κ such that η(x ) ≤ 10η(x ). Taking the minimum over all 0-cochains x then implies that if λ (L) is the smallest eigenvalue of L, λ (L) ≤ min η(x ) ≤ 10λ (L). (7.1) 1 1 x =1or0 A natural question is whether this theorem extends to a more general class of sheaves on graphs. One reasonable candidate for extension is the class of sheaves on graphs where all restriction maps are partial isometries, i.e., maps which are unitary on the orthogonal complement of their kernels. One might view these as O(n)-bundles where the edge stalks have been reduced in dimension by an orthogonal projection. However, the cochain rounding approach does not work for these sheaves, as the following simple counterexample shows. Let G be a graph with two vertices and one edge, and let F (v ) = F (v ) = R and F (e) = R. Then let F =[10] and 1 2 v e √ 1 1 3 u F = . Then let x = and x = . Then η(x ) = 0, but η(x )> 0 v v v e 2 2 2 1 2 0 0 for any choice of u < 1. This means that there cannot exist any function f : R → R with f (0) = 0 such that η(x ) ≤ f (η(x )). This example does not immediately show that the Cheeger inequality (7.1)isfalse for this class of sheaves, since this sheaf does have a section of stalkwise norm 1, but it does offer a counterexample to the key lemma in the proof. Indeed, a more complicated family of counterexamples exists with sheaves that have no global sections. These counterexamples show that an approach based on variational principles and rounding is unlikely to prove an analogue of the results of Bandeira et al. for more general classes of sheaves. 123 Toward a spectral theory of cellular sheaves 347 7.2 Toward a structural Cheeger inequality Many extensions of the graph Cheeger inequality view it from the perspective of a constrained optimization problem over cochains. This is the origin of the Cheeger inequality for O(n)-bundles, and of the higher-dimensional Cheeger constants pro- posed by Gromov, Linial and Meshulam, and others (Linial and Meshulam 2006; Gromov 2010; Parzanchevski et al. 2016). However, a sheaf gives us more structure to work with than simply cochains. The traditional Cheeger inequality for graphs is frequently stated as a graph cutting problem: what is the optimal cut balancing the weight of edges removed with the sizes of the resulting partition? If we take the constant sheaf on a graph G, we can represent a cut of G by setting some restriction maps to 0, or, more violently, setting the edge stalks on the cut to be zero-dimensional. Thus, a potential analogue to the Cheeger constant for sheaves might be an optimal perturbation to the structure of the sheaf balancing the size of the perturbation with the size of the support of a new global section that the perturbation induces. For instance, we might measure the size of a perturbation of the sheaf’s restriction maps in terms of the square of the Frobenius norm · of the coboundary matrix. If we minimize δ − δ , a natural relaxation to the space of all matrices shows that F F this value is greater than λ (L ). 1 F 8 Toward applications The increase in abstraction and technical overhead implicit in lifting spectral graph theory to cellular sheaves is nontrivial. However, given the utility of spectral graph theory in so many areas, the generalization to sheaves would appear to be a good investment. As this work is an initial survey of the landscape, we quickly sketch a collection of potential applications. These sketches are brief enough to allow the curious to peruse, while providing experts with enough to construct details as needed. 8.1 Distributed consensus Graph Laplacians and adjacency matrices play an important role in the study and design of distributed dynamical systems. This begins with the observation that the continuous-time dynamical system on a set of real variables {x : v ∈ V (G)} indexed by the vertices of a graph G with Laplacian L, x˙ =−Lx , is local with respect to the graph structure: the only terms that inﬂuence x˙ are the x for w adjacent to v. Further, if the graph is connected, diagonalization of L shows that the ﬂow of this dynamical system converges to a consensus—the average of the initial condition. A similar observation holds for sheaves of ﬁnite-dimensional vector spaces on graphs: 123 348 J. Hansen , R. Ghrist Proposition 8.1 Let F be a sheaf on a cell complex X. The dynamical system x˙ = −Δ x has as its space of equilibria H (X ; F ), the space of harmonic k-cochains of F. The trajectory of this dynamical system initialized at x converges exponentially quickly to the orthogonal projection of x onto H (X ; F ). −t Δ Proof This is a linear dynamical system with ﬂows given by x (t ) = e x . Since k k Δ is self-adjoint, it has an orthogonal eigendecomposition Δ = V V , so that F F −t ∗ −t λ ﬂows are given by x (t ) = Ve V x = e v , x v .Thetermsofthissumfor 0 i 0 i λ > 0 converge exponentially to zero, while the terms with λ = 0 remain constant, i i so that the limit as t →∞ is v , x v . Since the v are orthonormal, i 0 i i v ∈H (X ;F ) this is an orthogonal projection onto H (X ; F ). In particular, for k = 0, this result implies that a distributed system can reach consensus on the nearest global section to an initial condition. 8.2 Flocking One well-known example of consensus on a sheaf comes from ﬂocking models (Jad- babaie et al. 2003; Tanner et al. 2003b). In a typical setting, a group of autonomous agents is tasked with arranging themselves into a stable formation. As a part of this, agents need a way to agree on a global frame of reference. Suppose one has a collection of autonomous agents in R , each of which has its own internal coordinate system with respect to which it measures the outside world. Each agent communicates with its neighbors, communication being encoded as a graph. Assume agents can calculate bearings to their neighbors in their own coordinate frames. The agents wish to agree on a single direction in a global, external frame, perhaps in order to travel in the same direction. However, the transformations between local frames are not known. To solve this, one constructs a sheaf on the neighborhood graph of these agents. The vertices have as stalks R , representing vectors in each agent’s individual coordinate frame. The edges have stalks R , used to compare bearings. Since the agents can measure the bearing to each neighbor, they can project vectors in their coordinate frame onto this bearing. Let b(v, w) be the unit vector in v’s frame pointing toward w. Then for the (oriented) edge e = v ∼ w, the restriction map F : R → R is ve given by b(v, w), •, while the restriction map F is −b(w, v), •. (The change we of sign is necessary because the bearing vectors are opposites in the global frame.) Any globally consistent direction for the swarm will be a section of this sheaf, and with a bit more information the agents can achieve consensus on a direction. This is merely one simple example of a sheaf for building consensus via Laplacian ﬂow. The literature on ﬂocking has various scenarios, including, e.g., the case in which the network communication graph changes over time (Tanner et al. 2003a). 8.3 Opinion dynamics Sheaf Laplacians provide a drop-in replacement for graph Laplacians when one wishes to constrain a distributed algorithm to a locally deﬁnable subspace of the global state 123 Toward a spectral theory of cellular sheaves 349 space. For example, the ﬂocking application in the previous example generalizes greatly to the setting of opinion dynamics on social networks. Consider the setting of a collection of agents, each of whom has an R-valued opinion on some matter (say, a measure of agreement or disagreement with a particular proposition). A social network among agents, modeled as a weighted graph, permits inﬂuence of opinions based on Laplacian dynamics: each member of the network continuously adjusts their opinion to be more similar to the average of their neighbors’ opinions, either in continuous or discrete time. The literature on opinion dynamics begins with this simple setting (DeGroot 1974; Lehrer 1975), and quickly grows to include a number of generalizations of graph Laplacians when there are multiple opinions or other features (Ye et al. 2018; Patterson and Bamieh 2010; Pirani and Sundaram 2014). Our perspective is that lifting the simple model to a sheaf automatically incorporates various novel features while maintaining the simplicity of a Laplacian ﬂow. The ﬁrst obvious generalization is that multiple opinions reside in higher- dimensional stalks. Each agent p has a vector space F (p) of opinions on some set of topics. These vector spaces need not have the same dimension across the network— there is no need to assume that every member of the network has an opinion on every topic. Between each pair (p, q) of participants adjacent in the social network, there is an edge e with a stalk F (e), which we might label a discourse space. Opinions in F (p) and F (q) are translated into the discourse space by the restriction maps F pe and F . qe The ﬂexibility of a sheaf permits a wonderful array of novel features. For instance, each pair of participants in the social network might only communicate about a handful of topics, and hence only inﬂuence each others’ opinions along certain directions. Other topics would therefore lie in the kernels of the restriction map to their shared discourse space. Some features which appear difﬁcult to model in the classical literature on opinion dynamics are easily programmed into a sheaf: what happens if certain agents lie about their opinion, and then only to certain individuals on certain topics? Is a “public” consensus (with privately-held or context-dependent personal opinions) still possible? This demonstrates the utility of sheaves not merely in having stalks which vary, but with varying and interesting restriction maps as well. 8.4 Distributed optimization Laplacian dynamics are useful not only for mere consensus, but also as a way to implement consistency constraints for other sorts of distributed algorithms. Particu- larly important among these are distributed optimization algorithms, where a network optimizes a sum of objective functions distributed across the nodes, with the Laplacian dynamics enforcing the constraint that local state be consistent across nodes. Fix a sheaf of ﬁnite-dimensional vector spaces over a graph G. For each node, v ∈ V (G), assume a cost function, say, a convex functional φ from the stalk of v to R. The problem of ﬁnding a global section x = (x ) which minimizes φ (x ) subject v v v to the constraint that x ∈ H (G; F ) is a relatively unexplored class of optimization 123 350 J. Hansen , R. Ghrist problems. Such problems are naturally distributed in nature, as the constraint (given in terms of the coboundary operator) is locally deﬁned. More generally, one can consider distributed optimization with homological con- straints on any cellular sheaf of vector spaces over a cell complex X. If the problem to be solved is the optimization of an objective function deﬁned on C (X ; F ) subject to the constraint that the optimum lie in H (X ; F ), then this is naturally distributed. One might call such problems homological programs, analogous to the manner in which linear constraints give rise to linear programs. The Laplacian evolution then plays a role in providing distributed algorithms to solve such optimization problems. 8.5 Communication compression Both discrete-time as well as continuous-time Laplacian evolution is useful. Consider the following modiﬁcation of the consensus problems previously discussed. Suppose one has a distributed system modeled by a graph G, where each node of G has state in R for some large D and the nodes are required to reach consensus. The Laplacian ﬂow on states may be discretized as x [t + 1]= (I − αL)x [t ]. (8.1) To implement this discrete-time evolution equation, at each time step, a node v must send its state x [t]∈ R to each of its neighbors, the cost of doing so scaling with state size D. It may be preferable instead to have each node send a lower-dimensional compression of its state to each neighbor, i.e., a projection of x [t ] onto a d D- dimensional subspace, with the subspace depending on the edge e. As with the continuous-time evolution, equilibria of (8.1) correspond to global sections of the sheaf. However, changing the stalks over edges and the correspond- ing restriction maps changes the sheaf and therefore, potentially, its global sections. The goal for reducing the communication complexity is therefore to program this compressed sheaf so as to preserve the zeroth cohomology H . Such a sheaf would comprise a certain approximation of the constant sheaf over the graph. 8.6 Sheaf approximation A sheaf of vector spaces can be thought of as a distributed system of linear trans- formations, and its cohomology H consists of equivalence classes of solutions to systems based on these constraints. From this perspective, questions of approximation — of sheaves and sheaf cohomology—take on especial relevance. The question of approximating global sections to a given sheaf has appeared in, e.g., Robinson (2017, 2018). Questions of approximating sheaves are equally interesting. Given the relative lack of investigation, the following deﬁnition is perhaps premature; nevertheless, it is well- motivated by problems of distributed consensus and by cognate notions of cellular approximation in algebraic topology. 123 Toward a spectral theory of cellular sheaves 351 Deﬁnition 8.2 Let X be a regular cell complex, and let G be a sheaf on X. We say that a sheaf F on X is a k-approximation to G if there exists a sheaf morphism a : G → F which is an isomorphism on stalks over cells of degree at most k, and which induces i i an isomorphism H (X ; G) → H (X ; F ) for all i ≤ k. If V is a vector space, we denote the constant sheaf with stalk V by V, and say that F is an approximation to the constant sheaf if F is an approximation to V. This deﬁnition is reminiscent of cellular approximation methods from algebraic topology. A space X may be k-approximated by a cell complex Y , via a morphism Y → X inducing an isomorphism on homotopy groups up to degree k.Herewe approximate a sheaf on a cell complex by one with the same cohomology in degrees up to k. In particular, a 0-approximation to F has the same vertex stalks and the same space of global sections as F. Proposition 8.3 If F is a 0-approximation to V, then it is isomorphic to a sheaf with vertex stalks V where for each edge e joining vertices v and w, the restriction maps F : V → F (e) and F : V → F (e) are equal. ve we Proof Note that because a : V → F is an isomorphism on vertex stalks, F is clearly isomorphic to a sheaf with vertex stalks V. For every edge e = (v, w) we have the diagram id VV id ve V F (e) id F we id VV and the only way it can commute is if F = F = a . ve we e The proof of this proposition shows that specifying an approximation to V is the same as specifying a morphism a : V → F (e) for each edge e of G. Further, in order to produce an approximation to V,the a must assemble to a map a : C (G; V) → C (G; F ) = F (e) such that ker(a ◦ δ ) = ker δ . This holds if ker a is V V e∈E contained in a complement to im δ; equivalently, the projection map π : C (G; V) → H (G; V) must be an isomorphism when restricted to ker a. This suggests a way to construct an approximation to the constant sheaf. Choose a subspace K of V(e) for each edge e of G and deﬁne a to be the projection map e e 1 1 V → V/K .If K has the same dimension in H (G; V) as in C (G; V), then e e e∈E a = a deﬁnes the edge maps giving an approximation to V. (The vertex maps e∈E may be taken to be the identity.) The question of when a collection {K } produces an approximation to the constant sheaf appears quite subtle, and will be the subject of future work. This description of approximations to the constant sheaf has ignored the question of weights—that is, what inner products to put on the quotient spaces V/K —which will be crucial to the spectral behavior of their Laplacians and hence to the performance of distributed consensus algorithms based thereon. 123 352 J. Hansen , R. Ghrist To understand this relationship, consider again the discretization of the Laplacian ﬂow x [t + 1]= (I − αL )x [t ]. The matrix (I − αL ) has an eigenvalue of 1 with F F eigenspace equal to H (G; F ), with all other eigenvalues less than 1. The optimal convergence rate for this consensus algorithm is obtained at an α keeping the nontrivial eigenvalues as close to zero as possible. If λ is the largest eigenvalue of L and max F λ the smallest nontrivial eigenvalue of L , this is obtained at α = ,for a min F λ +λ max min λ −λ max min nontrivial spectral radius of r = . λ +λ max min The number of steps necessary to reach a level of disagreement of is thus pro- log portional to .Ona k-regular graph with d-dimensional edge stalks, the total log(r ) amount of communication each node must undertake at each step is proportional to log kd. Thus the total communication cost per node is proportional to kd .For the log(r ) log λ (G)−λ (G) max min constant sheaf R , the total cost per node is kD , where R = is log(R) λ (G)−λ (G) max min the corresponding spectral radius for consensus over L D.If d log(R) < 1, D log(r ) the total communication cost for consensus using the approximation to the constant sheaf will be lower than that for the constant sheaf. Preliminary investigation suggests it may be possible to construct approximations to the constant sheaf that achieve this threshold, but more work is necessary to develop methods for creating spectrally advantageous approximations to the constant sheaf. These could then be marshaled to improve the speed and efﬁciency of distributed algorithms that involve consensus, such as distributed optimization. 8.7 Synchronization The concept of synchronization in the context of problems with data on graphs is exempliﬁed in work by Singer on the angular alignment problem (Singer 2011). The concept was developed further by Bandeira in his dissertation (Bandeira 2015). The general idea is to recover information about some set of parameters from knowledge of their pairwise relationships. The general formulation, due to Bandeira, is as follows: Given a group G, a graph X, and a function f : G → R for each edge i ∼ j of X, ij −1 ﬁnd a function g : V (X ) → G minimizing f (g(i )g( j ) ). ij i ∼ j Often, the functions f are chosen such that they have a unique minimum at a given ij element g ∈ G. One may view this as originating from a G-principal bundle on a ij graph, with the group elements g deﬁning transition maps. The desired solution is a ij section of the bundle, determined up to a self-action of G, but may not exist if there is error in the measured g . As a result, we seek an error-minimizing solution, where ij the error is measured by the functions f . ij Sheaves on graphs offer a broader formulation: synchronization is the problem of ﬁnding a global section, or approximate global section, of an observed sheaf on a graph. By choosing sheaves valued in a suitable category, we can recover the group- theoretic formulation. There is something of a gap between the natural formulation 123 Toward a spectral theory of cellular sheaves 353 of many synchronization problems and a sheaf valued in vector spaces; bridging that gap for synchronization over O(d) is the goal of Bandeira et al. (2013). One of the initial motivating problems for the study of synchronization was the cryo-electron microscopy alignment problem. The goal is to understand the con- ﬁguration of a molecule, represented by a density function on R . Cryo-electron microscopy allows one to measure projections of random rotations of this function onto a ﬁxed two-dimensional plane. One approach to recovery involves inferring these unknown rotations from pairwise information. After taking the Fourier transform of the measured two-dimensional distributions, each pair of distributions will agree on a one-dimensional subspace, speciﬁcally, the invariant axis for the rotation relating the two orientations of the molecule. Suppose the ith measurement is taken from the molecule in an orientation ρ ∈ SO(3), so that the transformation between the orientation of measurement i and mea- −1 surement j is ρ = ρ ρ .If x is a vector in the base orientation frame of the ij j molecule, its representation in the frames for i and j are ρ x and ρ x, respectively. i j These two vectors have the same projection onto the invariant subspace of ρ . Since ij this invariant subspace is precisely the subspace on which the relevant two projections agree, we can check whether two vectors in the frames for measurements i and j agree by projecting them onto this subspace. A single constraint of this form does not ensure equality of vectors in the different frames. However, sufﬁciently many generic such constraints will. Combining all these pairwise constraints gives us a sheaf with the same form as the sheaf of autonomous agents discussed in Sect. 8.2. Note that the pairwise data here obtained is not in the form of invertible transformations, but weaker constraints. Thus, a major motivat- ing problem for synchronization has a natural expression in the language of cellular sheaves. The explicitly sheaf-theoretic formulation of the synchronization problem suggests a different solution approach. If a synchronization sheaf has a global section—as is the case when the data are internally consistent and uncorrupted by noise—ﬁnding that section is trivial. The traditional approach to synchronization takes these transition functions as they are, and seeks an approximate section to the sheaf. On the other hand, we might try to denoise the measured relationships themselves using the condition of cycle-consistency. That is, given an observed sheaf, ﬁnd the nearest sheaf supporting a global section. A structural Cheeger inequality as discussed in Sect. 7.2 would give spectral insights into this problem. Deeper understanding would come from study of an appropriate moduli space of cellular sheaves, which is a direction for future work. 8.8 Consistent clustering As suggested by Gao et al. (2016), the data of a sheaf on a graph is useful for more than recovering a global section. The problem of clustering objects where the similarity measure comes from an explicit matching or transformation gives extra information. If we stipulate that objects within a cluster should have consistent transformations along cycles, the problem of clustering becomes the problem of partitioning a graph into subgraphs, each of which supports the appropriate space of global sections. 123 354 J. Hansen , R. Ghrist Similar ideas arise in Gao (2016), which considers correspondences between surfaces produced using the soft Procrustes distance. These correspondences are maps between probability distributions on the vertex sets of discretized surfaces. When these surfaces are meshes with varying numbers of vertices, these maps are not invertible, but by construction they are represented by doubly stochas- tic matrices, and the analogue of the inverse for such a map is simply the transpose of its corresponding matrix. These sorts of geometric correspondences are natural to consider in the context of geometric morphometrics, the ﬁeld devoted to studying and classifying species based on their geometric proper- ties. Gao constructs a matrix he calls the graph horizontal Laplacian, together with normalized versions he uses to formulate a ﬁber bundle version of the diffusion maps algorithm for dimensionality reduction. The graph horizontal Laplacian is related to a map of graphs X → G, where the ﬁbers over vertices of G are discrete. A weighting on the edges of X induces a matrix-valued weighting on the edges of G. This produces a weighted adjacency matrix W of G, from which the graph horizontal Laplacian is H H generated by L = D − W , where D is the diagonal matrix necessary to make L have row sums equal to zero. This is in fact equivalent to the sheaf Laplacian of the pushforward of the weighted constant sheaf on X, and as a consequence of Proposition 5.10, is simply a block subdivision of the Laplacian of X. This sheaf on G can then be normalized to construct a diffusion map embedding of the vertices of G, as well as an embedding of the vertices of X. When applied to the surface correspondence problem, the eigenvectors of the resulting sheaf Laplacian serve to partition the surfaces into automatically determined landmarks or regions of interest. Approaching these notions of partitioning, partial sections, and noninvertible matchings from a sheaf-theoretic perspective offers new tools and clariﬁes the prob- lems in question, with potential for the spectral approach to yield insights. 9 Closing questions There are numerous interesting open questions in an emerging spectral sheaf theory. We highlight a few below, with comments. 9.1 Metrics on the space of cellular sheaves Interleaving-type constructions have been used to deﬁne metrics on the space of con- structible sheaves (Curry 2014, Chapter 15). However, these rely on explicit geometric information about the sheaves and their underlying spaces. Working with weighted cellular sheaves may make it possible to deﬁne useful distances that rely only on the combinatorial and algebraic structure of the sheaves. What are the most useful metrics on the space of sheaves? How do they interact with the sheaf Laplacians and their spectra? How does this shed light on a moduli space of cellular sheaves? 123 Toward a spectral theory of cellular sheaves 355 9.2 Developing a Cheeger inequality Following the discussion in Sect. 7.2, a structural Cheeger inequality for sheaves is connected to questions of a potential moduli space of sheaves. Such an inequality would describe how the spectral properties of a sheaf interact with its distance to the nearest sheaf with a nontrivial global section. Can a Cheeger inequality emerge from approximations to the constant sheaf, seeking 0-cochains of small coboundary which are constant on large sets of vertices? 9.3 Interactions with the derived category The standard way of understanding sheaf cohomology is through the derived category of complexes of sheaves (Gelfand and Manin 2003). We may replace a sheaf by an injective resolution and take the cohomology of the complex of sheaves. What is the relationship between a weighted sheaf and its injective resolutions, and how do the resulting Laplacians connect with the Hodge Laplacian deﬁned on the cochain com- plex? What results can be proven about their spectra? How do they interact with the standard sheaf operations? Is there a consistent way to add weights to the derived cate- gory of sheaves? We should not expect the answers to these questions to be unique due to the dagger categorical issues discussed in Sect. 3.1, but there may be constructions which are nevertheless appealing. 9.4 Random walks Chung and Zhao (2012) considered random walks on discrete O(n)-bundles, including a deﬁnition of a sort of PageRank algorithm. Is it possible to deﬁne random walks on more general sheaves of vector spaces, and to what extent are such related to the sheaf Laplacian and its spectral features? Is there an analogous PageRank algorithm for sheaves? 9.5 Cones and directedness How does one model directedness and asymmetric relations on sheaves? Sheaves of cones and sheaf cohomology taking values in categories of cones have proven useful in recent applications of sheaf theory to problems incorporating directedness (Ghrist and Krishnan 2017; Kashiwara and Schapira 2018). Such methods, though promising, may be noncommutative, using semigroups or semimodules to encode the directed- ness, which, in turn, pushes the boundaries of existing methods in sheaf theory and nonabelian sheaf cohomology. Funding This funding was supported by Ofﬁce of Naval Research (Grant Nos. FA8650-18-2-7840, N00014- 16-1-2010) Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 Interna- tional License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, 123 356 J. Hansen , R. Ghrist and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. References Abraham, R., Marsden, J.E., Ratiu, T.: Manifolds, Tensor Analysis, and Applications. Springer, New York (1988) Bandeira, A.: Convex relaxations for certain inverse problems on graphs. PhD thesis, Princeton University, (2015) Bandeira, A.S., Singer, A., Spielman, D.A.: A Cheeger inequality for the graph connection Laplacian. SIAM J. Matrix Anal. Appl. 34(4), 1611–1630 (2013) Belkin, M., Niyogi, P.: Laplacian Eigenmaps for dimensionality reduction and data representation. Neural Comput. 15, 1373–1396 (2003) Björner, A.: Posets, regular CW complexes and Bruhat order. Eur. J. Comb. 5(1), 7–16 (1984) Boman, E.G., Chen, D., Parekh, O., Toledo, S.: On factor width and symmetric H-matrices. Linear Algebra Appl. 405(1), 239–248 (2005) Bredon, G.E.: Sheaf Theory: Number 170 in Graduate Texts in Mathematics, 2nd edn. Springer, Berlin (1997) Brouwer, A.E., Haemers., W.H.: Spectra of Graphs. Universitext. Springer, Berlin (2012) Brüning, J., Lesch, M.: Hilbert complexes. J. Funct. Anal. 108(1), 88–132 (1992) Bullo, F.: Lectures on network systems. CreateSpace, (2018) Carlsson, G.: The shape of data, (2012) Catanzaro, M.J., Chernyak, V.Y., Klein, J.R.: On Kirchhoff’s theorems with coefﬁcients in a line bundle. Homol. Homotopy Appl. 15(2), 267–280 (2013) Chung, F.: Spectral Graph Theory. AMS, (1992) Chung, F., Zhao, W.: Ranking and sparsifying a connection graph. In: International Workshop on Algorithms and Models for the Web-Graph, Lecture Notes in Computer Science. Springer, (2012) Coifman, R.R., Lafon, S.: Diffusion maps. Appl. Comput. Harmon. Anal. 21(1), 5–30 (2006) Curry, J.: Sheaves, cosheaves, and applications. PhD thesis, University of Pennsylvania, (2014) Curry, J., Ghrist, R., Robinson, M.: Euler calculus with applications to signals and sensing. In: Proceedings of the Symposium in Applied Mathematics. AMS, (2012) Cvetcovic, ´ D., Simic, ´ S.: Graph spectra in computer science. Linear Algebra Appl. 434(6), 1545–1562 (2011) Davis, J., Kirk, P.: Lecture Notes in Algebraic Topology, volume 35 of Graduate Studies in Mathematics. American Mathematical Society, Providence, Rhode Island (2001) De Carli Silva, M.K., Harvey, N.J.A., Sato, C.M.: Sparse sums of positive semideﬁnite matrices. ACM Trans. Algorithms 12(1), 9:1–9:17 (2016) DeGroot, M.H.: Reaching a consensus. J. Am. Stat. Assoc. 69, 118–121 (1974) Dörﬂer, F., Bullo, F.: Kron reduction of graphs with applications to electrical networks. IEEE Trans. Circ. Syst. I: Regul P. 60(1), 150 (2013) Eckmann, B.: Harmonische funktionen und randwertaufgaben in einem komplex. Comment. Math. Helv. 17(1), 240–255 (1945) Edelsbrunner, H., Harer, J.: Computational Toplogy: An Introduction. American Mathematical Society, Providence (2010) Friedman, J.: Sheaves on graphs, their homological invariants, and a proof of the Hanna Neumann conjecture. Memoirs of the American Mathematical Society 233(1100), (2015) Friedman, J.: Computing Betti numbers via combinatorial Laplacians. Algorithmica 21(4), 331–346 (1998) Gao, T.: The Diffusion Geometry of Fibre Bundles. arXiv:1602.02330, (2016) Gao, T., Brodzki, J., Mukherjee, S.: The Geometry of Synchronization Problems and Learning Group Actions. arXiv:1610.09051, (2016) Gelfand, S.I., Manin, Y.I.: Methods of Homological Algebra, Springer Monographs in Mathematics, 2nd edn. Springer, Berlin (2003) Ghrist, R.: Elementary Applied Topology. CreateSpace, https://www.math.upenn.edu/ghrist/notes.html, (2014) 123 Toward a spectral theory of cellular sheaves 357 Ghrist, R., Krishnan, S.: Positive Alexander duality for pursuit and evasion. SIAM J. Appl. Algebra Geom. 1(1), 308–327 (2017) Gromov, M.: Singularities, expanders and topology of maps. Part 2: from combinatorics to topology via algebraic isoperimetry. Geom. Funct. Anal. 20, 416–526 (2010) Hadani, R., Singer, A.: Representation theoretic patterns in three-dimensional cryo-electron microscopy II—the class averaging problem. Found. Comput. Math. 11(5), 589–616 (2011) Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge (2001) Heunen, C., Karvonen, M.: Limits in dagger categories. Theory Appl. Categ. 34(18), 468–513 (2019) Hoory, S., Linial, N., Widgerson, A.: Expander graphs and their applications. Bull. Am. Math. Soc. 43(4), 439–561 (2006) Horak, D., Jost, J.: Spectra of combinatorial Laplace operators on simplicial complexes. Adv. Math. 244, 303–336 (2013) Jadbabaie, A., Lin, J., Morse, A.S.: Coordination of groups of mobile autonomous agents using nearest neighbor. IEEE Trans. Autom. Control 50(3), 2953–2958 (2003) Johnson, C.R., Smith, R.L.: Closure Properties. In The Schur Complement and Its Applications, number 4 in Numerical Methods and Algorithms, pp. 111–136. Springer, (2005) Kaczynski, T., Mischaikow, K., Mrozek, M.: Computational Homology, Applied Mathematical Sciences. Springer, New York (2004) Kashiwara, M., Schapira, P.: Sheaves on Manifolds. (1990) Kashiwara, M., Schapira, P.: Persistent homology and microlocal sheaf theory. arXiv:1705.00955, (2018) Kenyon, R.: Spanning forests and the vector bundle Laplacian. Ann. Prob. 39(5), 1983–2017 (2011) Lehrer, K.: Social consensus and rational agnoiology. Synthese 31, 141–160 (1975) Linial, N., Meshulam, R.: Homological connectivity of random 2-complexes. Combinatorica 26(4), 475– 487 (2006) Lyons, R., Peres, Y.: Probability on Trees and Networks. Number 42 in Cambridge series in statistical and probabilistic mathematics. Cambridge University Press, (2016) MacPherson, R., Patel, A.: Persistent Local Systems. (2018) Mantuano, T.: Discretization of vector bundles and rough Laplacian. Asian J. Math. 11(4), 671–698 (2007) Osting, B., Palande, S., Wang, B.: Towards spectral sparsiﬁcation of simplicial complexes based on gener- alized effective resistance. (2017) Otter, N., Porter, M.A., Tillmann, U., Grindrod, P., Harrington, H.A.: A roadmap for the computation of persistent homology. EPJ Data Sci. 6(1), 17 (2017) Parzanchevski, O.: High dimensional expanders. PhD thesis, Hebrew University of Jerusalem, (2013) Parzanchevski, O., Rosenthal, R., Tessler, R.J.: Isoperimetric inequalities in simplicial complexes. Combi- natorica 36(2), 195–227 (2016) Patterson, S., Bamieh, B.: Interaction-driven opinion dynamics in online social networks. In: Proceedings of the First Workshop on Social Media Analytics, SOMA ’10, pp. 98–105. ACM, (2010) Pirani, M., Sundaram, S.: Spectral properties of the grounded Laplacian matrix with applications to con- sensus in the presence of stubborn agents. In: Proceedings of the American Control Conference, pp. 2160–2165, (2014) Robinson, M.: Sheaves are the canonical data structure for sensor integration. Inf Fusion 36, 208–224 (2017) Robinson, M.: Assignments to sheaves of pseudometric spaces. arXiv:1805.08927, (2018) Schaub, M.T., Benson, A.R., Horn, P., Lippner, G., Jadbabaie, A.: Random Walks on Simplicial Complexes and the normalized Hodge Laplacian. arXiv:1807.05044 , (2018) Singer, A.: Angular synchronization by eigenvectors and semideﬁnite programming. Appl. Comput. Har- mon. Anal. 30, 20–36 (2011) Singer, A., Wu, H.-T.: Vector diffusion maps and the connection Laplacian. Commun. Pure Appl. Math. 65(8), 1067–1144 (2012) Spielman, D.A.: Linear-time encodable and decodable error-correcting codes. IEEE Trans. Inf. Theory 42(6), 1723–1731 (1996) Spielman, D.: Course Notes: Spectral Graph Theory. http://www.cs.yale.edu/homes/spielman/561/, (2015) Spielman, D.A., Srivastava, N.: Graph Sparsiﬁcation by Effective Resistances. arXiv:0803.0929 , (2008) Spielman, D., Teng, S.-H.: Spectral sparsiﬁcation of graphs. SIAM J. Comput. 40(4), 981–1025 (2011) Spielman, D.A., Teng, S.-H.: Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. SIAM J. Matrix Anal. Appl. 35(3), 835–885 (2014) Steenbergen, J.: Towards a spectral theory for simplicial complexes. PhD thesis, Duke University, (2013) Sunada, T.: Discrete geometric analysis. In: Proceedings of Symposia in Pure Mathematics, (2008) 123 358 J. Hansen , R. Ghrist Tanner, H.G., Jadbabaie, A., Pappas, G.J.: Stable ﬂocking of mobile agents, part I: dynamic topology. In: 42nd IEEE International Conference on Decision and Control (IEEE Cat. No.03CH37475), vol. 2, pp. 2016–2021, (2003a) Tanner, H.G., Jadbabaie, A., Pappas, G.J.: Stable ﬂocking of mobile agents, part I: ﬁxed topology. In: 42nd IEEE International Conference on Decision and Control (IEEE Cat. No.03CH37475), vol. 2, pp. 2010–2015, (2003b) Tropp, J.A.: User-friendly tail bounds for sums of random matrices. Found. Comput. Math. 12, 389–434 (2012) Wu, C., Ren, S., Wu, J., Xia, K.: Weighted (Co)homology and Weighted Laplacian. arXiv:1804.06990, (2018) Ye, M., Trinh, M.H., Lim, Y-H., Anderson, B.D.O., Ahn, H-S.: Continuous-time Opinion Dynamics on Multiple Interdependent Topics. CoRR, arXiv:1805.02836, (2018) Zein, F.E., Snoussi, J.: Local Systems and constructible sheaves. In: Bass, H., Oesterlé, J., Weinstein, A., Zein, F.E., Suciu, A.I., Tosun, M., Muhammed Uludag, ˘ A., Yuzvinsky, S. (eds.) Arrangements, Local Systems and Singularities, vol. 283, pp. 111–153. Birkhäuser Basel, Basel (2009) Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional afﬁliations. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Journal of Applied and Computational Topology Springer Journals http://www.deepdyve.com/lp/springer-journals/toward-a-spectral-theory-of-cellular-sheaves-ncpMzD5R0s

Loading next page...

Publisher: Springer Journals
Copyright: Copyright © 2019 by The Author(s)
Subject: Mathematics; Algebraic Topology; Computational Science and Engineering; Mathematical and Computational Biology
ISSN: 2367-1726
eISSN: 2367-1734
DOI: 10.1007/s41468-019-00038-7
Publisher site: See Article on Publisher Site

Abstract

This paper outlines a program in what one might call spectral sheaf theory—an exten- sion of spectral graph theory to cellular sheaves. By lifting the combinatorial graph Laplacian to the Hodge Laplacian on a cellular sheaf of vector spaces over a regular cell complex, one can relate spectral data to the sheaf cohomology and cell structure in a manner reminiscent of spectral graph theory. This work gives an exploratory intro- duction, and includes discussion of eigenvalue interlacing, sparsiﬁcation, effective resistance, synchronization, and sheaf approximation. These results and subsequent applications are prefaced by an introduction to cellular sheaves and Laplacians. Keywords Cohomology · Cellular sheaf theory · Spectral graph theory · Effective resistance · Eigenvalue interlacing Mathematics Subject Classiﬁcation MSC 55N30 · MSC 05C50 1 Introduction In spectral graph theory, one associates to a combinatorial graph additional algebraic structures in the form of square matrices whose spectral data is then investigated and related to the graph. These matrices come in several variants, most particularly degree and adjacency matrices, Laplacian matrices, and weighted or normalized versions thereof. In most cases, the size of the implicated matrix is based on the vertex set, while the structure of the matrix encodes data carried by the edges. Robert Ghrist ghrist@math.upenn.edu Jakob Hansen jhansen@math.upenn.edu Department of Mathematics, University of Pennsylvania, 209 S. 33rd St., Philadelphia, PA 19104-6395, USA Department of Electrical and Systems Engineering, University of Pennsylvania, 200 S. 33rd St., Philadelphia, PA 19104-6314, USA 123 316 J. Hansen , R. Ghrist To say that spectral graph theory is useful is an understatement. Spectral methods are key in such disparate ﬁelds as data analysis (Belkin and Niyogi 2003; Coifman and Lafon 2006), theoretical computer science (Hoory et al. 2006; Cvetcovic´ and Simic´ 2011), probability theory (Lyons and Peres 2016), control theory (Bullo 2018), numerical linear algebra (Spielman and Teng 2014), coding theory (Spielman 1996), and graph theory itself (Chung 1992; Brouwer and Haemers. 2012). Much of spectral graph theory focuses on the Laplacian, leveraging its unique com- bination of analytic, geometric, and probabilistic interpretations in the discrete setting. This is not the complete story. Many of the most well-known and well-used results on the spectrum of the graph Laplacian return features that are neither exclusively geometric nor even combinatorial in nature, but rather more qualitative. For example, it is among the ﬁrst facts of spectral graph theory that the multiplicity of the zero eigen- value of the graph Laplacian enumerates connected components of the graph, and the relative size of the smallest nonzero eigenvalue in a connected graph is a measure of approximate dis-connectivity. Such features are topological. There is another branch of mathematics in which Laplacians hold sway: Hodge theory. This is the slice of algebraic and differential geometry that uses Laplacians on (complex) Riemannian manifolds to characterize global features. The classical initial result is that one recovers the cohomology of the manifold as the kernel of the Laplacian on differential forms (Abraham et al. 1988). For example, the dimension of the kernel of the Laplacian on 0-forms (R-valued functions) is equal to the rank of H , the 0-th cohomology group (with coefﬁcients in R), whose dimension is the number of connected components. In spirit, then, Hodge theory categoriﬁes elements of spectral graph theory. Hodge theory, like much of algebraic topology, survives the discretization from Riemannian manifolds to (weighted) cell complexes (Eckmann 1945; Friedman 1998). The classical boundary operator for a cell complex and its formal adjoint combine to yield a generalization of the graph Laplacian which, like the Laplacian of Hodge theory, acts on higher dimensional objects (cellular cochains, as opposed to differential forms). The kernel of this discrete Laplacian is isomorphic to the cellular cohomology of the complex with coefﬁcients in the reals, generalizing the connectivity detection of the graph Laplacian in grading zero. As such, the spectral theory of the discrete Laplacian offers a geometric perspective on algebraic-topological features of higher- dimensional complexes. Laplacians of higher-dimensional complexes have been the subject of recent investigation (Parzanchevski 2013; Steenbergen 2013; Horak and Jost 2013). This is not the end. Our aim is a generalization of both spectral graph theory and discrete Hodge theory which ties in to recent developments in topological data analysis. The past two decades have witnessed a burst of activity in computing the homology of cell complexes (and sequences thereof) to extract robust global features, leading to the development of specialized tools, such as persistent homology, barcodes, and more, as descriptors for cell complexes (Carlsson 2012; Edelsbrunner and Harer 2010; Kaczynski et al. 2004; Otter et al. 2017). Topological data analysis is evolving rapidly. One particular direction of evolution concerns a change in perspective from working with cell complexes as topological spaces in and of themselves to focusing instead on data over a cell complex—viewing 123 Toward a spectral theory of cellular sheaves 317 the cell complex as a base on which data to be investigated resides. For example, one can consider scalar-valued data over cell complexes, as occurs in weighted networks and complexes; or sensor data, as occurs in target enumeration problems (Curry et al. 2012). Richer data involves vector spaces and linear transformations, as with recent work in cryo-EM (Hadani and Singer 2011) and synchronization problems (Bandeira 2015). Recent work in TDA points to a generalization of these and related data structures over topological spaces. This is the theory of sheaves. We will work exclusively with cellular sheaves (Curry 2014). Fix a (regular, locally ﬁnite) cell complex—a triangulated surface will sufﬁce for purposes of imagination. A cellular sheaf of vector spaces is, in essence, a data structure on this domain, assigning local data (in the form of vector spaces) to cells and compatibility relations (linear transformations) between cells of incident ascending dimension. These structure maps send data over vertices to data over incident edges, data over edges to data over incident 2-cells, etc. As a trivial example, the constant sheaf assigns a rank-one vector space to each cell and identity isomorphisms according to boundary faces. More interesting is the cellular analogue of a vector bundle: a cellular sheaf which assigns a ﬁxed vector space of dimension n to each cell and isomorphisms as linear transformations (with specializations to O(n) or SO(n) as desired). The data assigned to a cellular sheaf naturally arranges into a cochain complex graded by dimension of cells. As such, cellular sheaves possess a Laplacian that specializes to the graph Laplacian and the Hodge Laplacian for the constant sheaf. For cellular sheaves of real vector spaces, a spectral theory—an examination of the eigenvalues and eigenvectors of the sheaf Laplacian—is natural, motivated, and, to date, unexamined apart from a few special cases (see Sect. 3.6). This paper sketches an emerging spectral theory for cellular sheaves. Given the motivation as a generalization of spectral graph theory, we will often specialize to cellular sheaves over a 1-dimensional cell complex (that is, a graph, allowing when necessary multiple edges between a pair of vertices). This is mostly for the sake of simplicity and initial applications, as zero- and one-dimensional homological invari- ants are the most readily applicable. However, as the theory is general, we occasionally point to higher-dimensional side-quests. The plan of this paper is as follows. In Sect. 2, we cover the necessary topological and algebraic preliminaries, including deﬁnitions of cellular sheaves. Next, Sect. 3 gives deﬁnitions of the various matrices involved in the extension of spectral theory to cellular sheaves. Section 4 uses these to explore issues related to harmonic functions and cochains on sheaves. In Sect. 5, we extend various elementary results from spectral graph theory to cellular sheaves. The subsequent two sections treat more sophisticated topics, effective resistance (Sect. 6) and the Cheeger inequality (Sect. 7), for which we have some preliminary results. We conclude with outlines of potential applications for the theory in Sect. 8 and directions for future inquiry in Sect. 9. The results and applications we sketch are at the beginnings of the subject, and a great deal more in way of fundamental and applied work remains. This paper has been written in order to be readable without particular expertise in algebraic topology beyond the basic ideas of cellular homology and cohomology. Category-theoretic terminology is used sparingly and for concision. Given the well- earned reputation of sheaf theory as difﬁcult for the non-specialist, we have provided 123 318 J. Hansen , R. Ghrist an introductory section with terminology and core concepts, noting that much more is available in the literature (Bredon 1997; Kashiwara and Schapira 1990). Our recourse to the cellular theory greatly increases simplicity, readability, and applicability, while resonating with the spirit of spectral graph theory. There are abundant references available for the reader who requires more information on algebraic topology (Hatcher 2001), applications thereof (Edelsbrunner and Harer 2010;Ghrist 2014), and cellular sheaf theory (Curry 2014;Ghrist 2014). 2 Preliminaries 2.1 Cell complexes Deﬁnition 2.1 A regular cell complex is a topological space X with a partition into subspaces {X } satisfying the following conditions: α α∈P 1. For each x ∈ X, every sufﬁciently small neighborhood of x intersects ﬁnitely many X . 2. For all α, β, X ∩ X = ∅ only if X ⊆ X . α β β α 3. Every X is homeomorphic to R for some n . α α 4. For every α, there is a homeomorphism of a closed ball in R to X that maps the interior of the ball homeomorphically onto X . Condition (2) implies that the set P has a poset structure, given by β ≤ α iff X ⊆ X . This is known as the face poset of X. The regularity condition (4) implies β α that all topological information about X is encoded in the poset structure of P .For our purposes, we will identify a regular cell complex with its face poset, writing the incidence relation β α. The class of posets that arise in this way can be characterized combinatorially (Björner 1984). For our purposes, a morphism of cell complexes is a morphism of posets between their face incidence posets that arises from a continuous map between their associated topological spaces. In particular, morphisms of simplicial and cubical complexes will qualify as morphisms of regular cell complexes. The class of regular cell complexes includes simplicial complexes, cubical com- plexes, and so-called multigraphs (as 1-dimensional cell complexes). As nearly every space that can be characterized combinatorially can be represented as a regular cell complex, these will serve well as a default class of spaces over which to develop a combinatorial spectral theory of sheaves. We note that the spectral theory of complexes has heretofore been largely restricted to the study of simplicial complexes (Schaub et al. 2018). A number of our results will specialize to results about the spectra of Hodge Laplacians of regular cell complexes by restricting to the constant sheaf. A few notions associated to cell complexes will be useful. (k) Deﬁnition 2.2 The k-skeleton of a cell complex X, denoted X , is the subcomplex of X consisting of cells of dimension at most k. Deﬁnition 2.3 Let σ be a cell of a regular cell complex X. The star of σ , denoted st(σ ),isthe setofcells τ such that σ τ . 123 Toward a spectral theory of cellular sheaves 319 Topologically, st(σ ) is the smallest open collection of cells containing σ,arole we might denote as the “smallest cellular neighborhood” of σ . Stars serve an impor- tant purpose in giving combinatorial analogues of topological notions for maps. For instance, a morphism f : X → Y of cell complexes may be locally injective as deﬁned on the topological spaces. Topologically, the condition for local injectivity is simply that every point in X have a neighborhood on which f is injective. Translating this to cell complexes, we require that for every cell σ ∈ X, f is injective on st(σ ). Topological continuity ensures that the preimage of a star st(σ ) under a cell mor- phism f : X → Y is a union of stars; if f is locally injective, we see that it must be a disjoint union of stars. A locally injective map is, further, a covering map if on each −1 component of f (st(σ )), f is an isomorphism. That is, the ﬁber of a star consists of a disjoint union of copies of that star. 2.2 Cellular sheaves Let X be a regular cell complex. A cellular sheaf attaches data spaces to the cells of X together with relations that specify when assignments to these data spaces are consistent. Deﬁnition 2.4 A cellular sheaf of vector spaces on a regular cell complex X is an assignment of a vector space F (σ ) to each cell σ of X together with a linear transfor- mation F : F (σ ) → F (τ ) for each incident cell pair σ τ . These must satisfy σ τ both an identity relation F = id and the composition condition: σ σ ρ σ τ ⇒ F = F ◦ F . ρτ σ τ ρσ The vector space F (σ ) is called the stalk of F at σ . The maps F are called the σ τ restriction maps. For experts, this deﬁnition at ﬁrst seems only reminiscent of the notion of sheaves familiar to topologists. The depth of the relationship is explained in detail in Curry (2014), but the essence is this: the data of a cellular sheaf on X speciﬁes spaces of local sections on a cover of X given by open stars of cells. This translates in two different ways into a genuine sheaf on a topological space. One may either take the Alexandrov topology on the face incidence poset of the complex, or one may view the open stars of cells and their natural reﬁnements a basis for the topology of X. There then exists a natural completion of the data speciﬁed by the cellular sheaf to a constructible sheaf on X. One may compress the deﬁnition of a cellular sheaf to the following: If X is a regular cell complex with face incidence poset P , viewed as a category, a cellular sheaf is a functor F : P → Vect to the category of vector spaces over a ﬁeld k. X k Deﬁnition 2.5 Let F be a cellular sheaf on X.A global section x of F is a choice x ∈ F (σ ) for each cell σ of X such that x = F x for all σ τ . The space of σ τ σ τ σ global sections of F is denoted Γ(X ; F ). 123 320 J. Hansen , R. Ghrist Perhaps the simplest sheaf on any complex is the constant sheaf with stalk V, which we will denote V. This is the sheaf with all stalks equal to V and all restriction maps equal to the identity. 2.2.1 Cosheaves In many situations it is more natural to consider a dual construction to a cellular sheaf. A cellular cosheaf preserves stalk data but reverses the direction of the face poset, and with it, the restriction maps. Deﬁnition 2.6 A cellular cosheaf of vector spaces on a regular cell complex X is an assignment of a vector space F (σ ) to each cell σ of X together with linear maps F : F (τ ) → F (σ ) for each incident cell pair σ τ which satisﬁes the identity σ τ (F = id) and composition condition: σ σ ρ σ τ ⇒ F = F ◦ F . ρτ ρσ σ τ op More concisely, a cellular cosheaf is a functor P → Vect . The contravariant op functor Hom(•, k) : Vect → Vect gives every cellular sheaf F a dual cosheaf F whose stalks are Hom(F (σ ), k). 2.2.2 Homology and cohomology The cells of a regular cell complex have a natural grading by dimension. By regularity of the cell complex, this grading can be extracted from the face incidence poset as the height of a cell in the poset. This means that a cellular sheaf has a graded vector space of cochains C (X ; F ) = F (σ ). dim(σ )=k To develop this into a chain complex, we need a boundary operator and a notion of orientation—a signed incidence relation on P .Thisisamap [•:•]: P × P → X X X {0, ±1} satisfying the following conditions: 1. If [σ : τ ] = 0, then σ τ and there are no cells between σ and τ in the incidence poset. 2. For any σ τ , [σ : γ ][γ : τ]= 0. γ ∈P Given a signed incidence relation on P , there exist coboundary maps δ : k k+1 C (X ; F ) → C (X ; F ). These are given by the formula δ | = [σ : τ ]F , F (σ ) σ τ dim(τ )=k+1 or equivalently, (δ x ) = [σ : τ ]F (x ). τ σ τ σ dim(σ )=k 123 Toward a spectral theory of cellular sheaves 321 Here we use subscripts to denote the value of a cochain in a particular stalk; that is, x is the value of the cochain x in the stalk F (σ ). It is a simple consequence of the properties of the incidence relation and the com- k k−1 mutativity of the restriction maps that δ ◦ δ = 0, so these coboundary maps deﬁne a cochain complex and hence a cohomology theory for cellular sheaves. In particular, H (X ; F ) is naturally isomorphic to Γ(X ; F ), the space of global sections. An anal- ogous construction deﬁnes a homology theory for cosheaves. Cosheaf homology may be thought of as dual to sheaf cohomology in a Poincaré-like sense. That is, frequently the natural analogue of degree zero sheaf cohomology is degree n cosheaf homology. A deeper formal version of this fact, exploiting an equivalence of derived categories, may be found in Curry (2014), ch. 12. There is a relative version of cellular sheaf cohomology. Let A be a subcomplex of X. There is a natural subspace of C (X ; F ) consisting of cochains which vanish on stalks over cells in A. The coboundary of a cochain which vanishes on A also vanishes (k+1) (k) on A, since any cell in A has only cells in A on its boundary. We therefore get • • a subcomplex C (X , A; F ) of C (X ; F ). The cohomology of this subcomplex is the relative sheaf cohomology H (X , A; F ). The natural maps between these spaces of cochains constitute a short exact sequence of complexes • • • 0 → C (X , A; F ) → C (X ; F ) → C (A; F ) → 0, from which a long exact sequence for relative sheaf cohomology arises: 0 0 0 1 0 → H (X , A; F ) → H (X ; F ) → H (A; F ) → H (X , A; F ) → ··· 2.2.3 Sheaf morphisms Deﬁnition 2.7 If F and G are sheaves on a cell complex X, a sheaf morphism ϕ : F → G is a collection of maps ϕ : F (σ ) → G(σ ) for each cell σ of X, such that for any σ τ , ϕ ◦ F = G ◦ ϕ . Equivalently, all diagrams of the following form τ σ τ σ τ σ commute: F (σ ) G(σ ) F G σ τ σ τ F (τ ) G(τ ) This commutativity condition assures that a sheaf morphism ϕ : F → G induces maps k k k ϕ : C (X ; F ) → C (X ; G) which commute with the coboundary maps, resulting in k k k the induced maps on cohomology H ϕ : H (X ; F ) → H (X ; G). 2.2.4 Sheaf operations There are several standard operations that act on sheaves to produce new sheaves. Deﬁnition 2.8 (Direct sum)If F and G are sheaves on X, their direct sum F ⊕ G is a sheaf on X with (F ⊕ G)(σ ) = F (σ ) ⊕ G(σ ). The restriction maps are (F ⊕ G) = σ τ F ⊕ G . σ τ σ τ 123 322 J. Hansen , R. Ghrist Deﬁnition 2.9 (Tensor product)If F and G are sheaves on X, their tensor product F ⊗ G is a sheaf on X with (F ⊗ G)(σ ) = F (σ ) ⊗ G(σ ). The restriction maps are (F ⊗ G) = F ⊗ G . σ τ σ τ σ τ Deﬁnition 2.10 (Pullback)If f : X → Y is a morphism of cell complexes and F ∗ ∗ is a sheaf on Y,the pullback f F is a sheaf on X with f F (σ ) = F ( f (σ )) and ( f F ) = F . σ τ f (σ ) f (τ ) Deﬁnition 2.11 (Pushforward) The full deﬁnition of the pushforward of a cellular sheaf is somewhat more categorically involved than the previous constructions. If f : X → Y is a morphism of cell complexes and F is a sheaf on X,the pushforward f F is a sheaf on Y with stalks f F (σ ) given as the limit lim F (τ ).The ∗ ∗ σ f (τ ) restriction maps are induced by the restriction maps of F, since whenever σ σ ,the cone for the limit deﬁning f F (σ ) contains the cone for the limit deﬁning f F (σ ), ∗ ∗ inducing a unique map f F (σ ) → f F (σ ). ∗ ∗ In this paper, we will mainly work with pushforwards over locally injective cell maps, that is, those whose geometric realizations are locally injective (see Sect. 2.1). If f : X → Y is locally injective, every cell σ ∈ X maps to a cell of the same −1 dimension, and for every cell σ ∈ Y , f (st(σ )) is a disjoint union of subcomplexes, each of which maps injectively to Y . In this case, f F (σ ) −1 F (σ ), and σ ∈ f (σ ) ( f F ) = −1 F . This computational formula in fact holds σ τ σ τ (σ τ )∈ f (σ τ) −1 more generally, if the stars of cells in f (σ ) are disjoint. Those familiar with the deﬁnitions of pushforward and pullback for sheaves over topological spaces will note a reversal of fates when we deﬁne sheaves over cell complexes. Here the pullback is simple to deﬁne, while the pushforward is more involved. This complication arises because cellular sheaves are in a sense deﬁned pointwise rather than over open sets. 3 Deﬁnitions 3.1 Weighted cellular sheaves Let k = R or C. A weighted cellular sheaf is a cellular sheaf with values in k- vector spaces where the stalks have additionally been given an inner product structure. Adding the condition of completeness to the stalks, one may view this as a functor P → Hilb , where Hilb is the category whose objects are Hilbert spaces over k X k k and whose morphisms are (bounded) linear maps. The inner products on stalks of F extend by the orthogonal direct sum to inner products on C (X ; F ), making these Hilbert spaces as well. The canonical inner products on direct sums and subspaces of Hilbert spaces give the direct sum and tensor product of weighted cellular sheaves weighted structures. Similarly, the pullbacks and pushforwards (over locally injective maps) of a weighted sheaf have canonical weighted structures given by their computational formulae in Sect. 2.2.4. Every morphism T : V → W between Hilbert spaces admits an adjoint map T : W → V , determined by the property that for all v ∈ V ,w ∈ W , w, T v=T w, v. 123 Toward a spectral theory of cellular sheaves 323 ∗ ∗ One may readily check that (T ) = T . This fact gives the category Hilb a dagger structure, that is, a contravariant endofunctor † (here the adjoint operation ) which acts as the identity on objects and squares to the identity. In a dagger category, the notion of unitary isomorphisms makes sense: they are the invertible morphisms T † −1 such that T = T . The dagger structure of Hilb introduces some categorical subtleties into the study of weighted cellular sheaves. The space of global sections of a cellular sheaf is deﬁned in categorical terms as the limit of the functor X → Vect deﬁning the sheaf. This deﬁnes the space of global sections up to unique isomorphism. We might want a weighted space of global sections to be a sort of limit in Hilb which is deﬁned up to unique unitary isomorphism. This is the notion of dagger limit, recently studied in Heunen and Karvonen (2019). Unfortunately, this work showed that Hilb does not have all dagger limits; in particular, pullbacks over spans of noninjective maps do not exist. As a result, there is no single canonical way to deﬁne an inner product on the space of global sections of a cellular sheaf F. There are two approaches that seem most natural, however. One is to view the space of global sections of F as ker δ with the natural inner product given by inclusion into C (X ; F ). The other is to view global sections as lying in F (σ ). We will generally take the view that global sections are a subspace of C (X ; F ); that is, we will weight Γ(X ; F ) by its canonical isomorphism with H (X ; F ), as deﬁned in Sect. 3.2. The dagger structure on Hilb gives a slightly different way to construct a dual cosheaf from a weighted cellular sheaf F. Taking the adjoint of each restriction map reverses their directions and hence yields a cosheaf with the same stalks as the original sheaf. From a categorical perspective, this amounts to composing the functor F with the dagger endofunctor on Hilb . When stalks are ﬁnite dimensional, this dual cosheaf is isomorphic to the cosheaf F deﬁned in Sect. 2.2.1 via the dual vector spaces of stalks. In this situation, we have an isomorphism between the stalks of F and its dual cosheaf. This is reminiscent of the bisheaves recently introduced by MacPherson and Patel (2018). However, the structure maps F (σ ) → F (σ ) will rarely commute with the restriction and extension maps as required by the deﬁnition of the bisheaf—this only holds in general if all restriction maps are unitary. The bisheaf construction is meant to give a generalization of local systems, and as such ﬁts better with our discussion of discrete vector bundles in Sect. 3.5. 3.2 The sheaf Laplacian 0 1 Given a chain complex of Hilbert spaces C → C → ··· we can construct the ∗ 2 ∗ ∗ Hodge Laplacian Δ = (δ + δ ) = δ δ + δδ . This operator is naturally graded k k k k k ∗ k k−1 k−1 ∗ into components Δ : C → C , with Δ = (δ ) δ + δ (δ ) . This operator can be further separated into up- (coboundary) and down- (boundary) Laplacians k k ∗ k k k−1 k−1 ∗ Δ = (δ ) δ and Δ = δ (δ ) respectively. + − ∗ ⊥ A key observation is that on a ﬁnite-dimensional Hilbert space, ker δ = (im δ) . ∗ ∗ For if δ x = 0, then for all y,0 =δ x , y=x,δy, so that x ⊥ im δ. This allows us to express the kernels and images necessary to compute cohomology purely in terms of kernels. This is the content of the central theorem of discrete Hodge theory: 123 324 J. Hansen , R. Ghrist 0 1 Theorem 3.1 Let C → C → ··· be a chain complex of ﬁnite-dimensional Hilbert k k k • spaces, with Hodge Laplacians Δ . Then ker Δ H (C ). k • k k−1 Proof By deﬁnition, H (C ) = ker δ / im δ . In a ﬁnite dimensional Hilbert space, k k−1 k−1 k ker δ / im δ is isomorphic to the orthogonal complement of im δ in ker δ , k k−1 ⊥ k k−1 ∗ which we may write (ker δ ) ∩ (im δ ) = (ker δ ) ∩ (ker(δ ) ). So it sufﬁces to k k k−1 ∗ k k ∗ k k show that ker Δ = (ker δ ) ∩ (ker(δ ) ). Note that ker δ = ker(δ ) δ = ker Δ k k k k k and similarly for Δ . So we need to show that ker(Δ + Δ ) = ker Δ ∩ ker Δ , − + − + − k k k k ∗ which will be true if im Δ ∩im Δ = 0. But this is true because im Δ = im(δ ) = + − + k ⊥ k k−1 k (ker δ ) and im Δ = im δ ⊆ ker δ . The upshot of this theorem is that the kernel of Δ gives a set of canonical represen- k • tatives for elements of H (C ). This is commonly known as the space of harmonic k • cochains, denoted H (C ). In particular, the proof above implies that there is an k k k−1 k ∗ orthogonal decomposition C = H ⊕ im δ ⊕ im(δ ) . When the chain complex in question is the complex of cochains for a weighted cellular sheaf F, the Hodge construction produces the sheaf Laplacians. The Laplacian which is easiest to study and most immediately interesting is the degree-0 Laplacian, which is a generalization of the graph Laplacian. We can represent it as a symmetric block matrix with blocks indexed by the vertices of the complex. The entries on 0 ∗ the diagonal are Δ = F F and the entries on the off-diagonal are ve v,v ve ve 0 ∗ Δ =−F F , where e is the edge between v and u. Laplacians of other ve u,v ue degrees have similar block structures. The majority of results in combinatorial spectral theory have to do with up- Laplacians. We will frequently denote these L by analogy with spectral graph theory, where L typically denotes the (non-normalized) graph Laplacian. In particular, we will further elide the index k when k = 0, denoting the graph sheaf Laplacian by simply L. A subscript will be added when necessary to identify the sheaf, e.g. L or Δ . Weighted labeled graphs are in one-to-one correspondence with graph Laplacians. The analogous statement is not true of sheaves on a graph. For instance, the sheaves in Fig. 1 have coboundary maps with matrix representations ⎡ ⎤ ⎡ ⎤ 1 1 1 −1 √ √ 2 2 ⎣ ⎦ ⎣ ⎦ and , 3 3 2 2 which means that the Laplacian for each is equal to 2 −1 −12 However, these sheaves are not unitarily isomorphic, as can be seen immediately by checking the stalk dimensions. More pithily, one cannot hear the shape of a sheaf. One source of the lossiness in the sheaf Laplacian representation is that restriction maps may be the zero morphism, effectively allowing for edges that are only attached to one 123 Toward a spectral theory of cellular sheaves 325 Fig. 1 Two nonisomorphic sheaves with the same Laplacian vertex. More generally, restriction maps may fail to be full rank, which means that it is impossible to identify the dimensions of edge stalks from the Laplacian. 3.2.1 Harmonic cochains k k The elements of ker Δ = H are known as harmonic k-cochains. More generally, a k-cochain may be harmonic on a subcomplex: Deﬁnition 3.2 A k-cochain x of a sheaf F on a cell complex X is harmonic onaset S of k-cells if (Δ x )| = 0. When k = 0 and F is the constant sheaf (i.e., in spectral graph theory), this can be expressed as a local averaging property: For each v ∈ S, x = x , where ∼ v u u∼v indicates adjacency and d is the degree of the vertex v. 3.2.2 Identifying sheaf Laplacians Given a regular cell complex X and a choice of dimension for each stalk, one can identify the collection of matrices which arise as coboundary maps for a sheaf on X as those matrices satisfying a particular block sparsity pattern. This sparsity pattern controls the number of nonzero blocks in each row of the matrix. Restricting to δ , we get a matrix whose rows have at most two nonzero blocks. The space of matrices which arise as sheaf Laplacians is then the space of matrices which have a factorization L = δ δ, where δ is a matrix satisfying this block sparsity condition. Boman et al. studied this class of matrices when the blocks have size 1 ×1, calling them matrices of factor width two (Boman et al. 2005). They showed that this class coincides with the class of symmetric generalized diagonally dominant matrices, those matrices L for which there exists a positive diagonal matrix D such that DL D is diagonally dominant. Indeed, the fact that sheaves on graphs are not in general determined by their Laplacians is in part a consequence of the nonuniqueness of width-two factorizations. 123 326 J. Hansen , R. Ghrist 3.3 Approaching infinite-dimensional Laplacians The deﬁnitions given in this paper are adapted to the case of sheaves of ﬁnite dimen- sional Hilbert spaces over ﬁnite cell complexes. Relaxing these ﬁniteness constraints introduces new complications. The spaces of cochains naturally acquire inner products by taking the Hilbert space direct sum. These are not the same as taking the algebraic direct sum or product of stalks. However, there is a sequence of inclusions of complexes • 2 • • C (X ; F ) ⊆ L C (X ; F ) ⊆ C (X ; F ) inducing algebraic maps between the corresponding compactly supported, L , and standard sheaf cohomology theories. The theory of abstract complexes of possibly inﬁnite-dimensional Hilbert spaces has been developed in Brüning and Lesch (1992). This paper explains conditions for the spaces of harmonic cochains of a complex to be isomorphic with the algebraic cohomology of the complex. A particularly nice condition is that the complex have ﬁnitely generated cohomology, which implies that the total coboundary map is a Fredholm operator. More generally, if the images of the coboundary and its adjoint are closed, the spaces of harmonic cochains will be isomorphic to the cohomology. Further issues arise when we consider the coboundary maps δ . For spectral pur- poses, it is in general desirable for these to be bounded linear maps, for which we must make some further stipulations. Sufﬁcient conditions for coboundary maps to be bounded are as follows: Proposition 3.3 Let F be a sheaf of Hilbert spaces on a cell complex X. Suppose that there exists some M such that for every pair of cells σ τ with dim σ = k and dim τ = k + 1, F ≤ M . Further suppose that every k-cell in X has at most σ τ k d cofaces of dimension k + 1, and every (k + 1)-cell in X has at most d faces of k+1 dimension k. Then δ is a bounded linear operator. Proof We compute: ⎛ ⎞ k 2 k 2 ⎝ ⎠ δ x = (δ x ) ≤ F x τ σ τ σ dim τ =k+1 dim τ =k+1 σ τ ⎛ ⎞ 2 2 ⎝ ⎠ ≤ M x ≤ M d x k σ k+1 σ dim τ =k+1 σ τ dim τ =k+1 σ τ 2 2 2 k 2 2 k 2 = M d x ≤ M d d x = M d d x . k+1 σ k+1 σ k+1 k k k dim σ =k σ τ dim σ =k k k+1 k k ∗ k k k ∗ If δ is bounded, its associated Laplacians Δ = (δ ) δ and Δ = δ (δ ) + − are also bounded. As bounded self-adjoint operators, their spectral theory is relatively 123 Toward a spectral theory of cellular sheaves 327 unproblematic. Their spectra consist entirely of approximate eigenvalues, those λ for which there exists a sequence of unit vectors {x } such that Δ x − λx → 0. k k k If δ is not just bounded, but compact, the Laplacian spectral theory becomes even nicer. In this situation, the spectrum of Δ has no continuous part, and hence consists purely of eigenvalues. An appropriate decay condition on norms of restriction maps ensures compactness. Proposition 3.4 Let F be a sheaf of Hilbert spaces on a cell complex X. Suppose that for all σ τ with dim σ = k and dim τ = k + 1, the restriction map F for is σ τ compact, and further that F < ∞. Then δ is a compact linear operator. σ τ σ τ F Proof It is clear that δ cannot be compact if any one of its component restriction maps fails to be compact. Suppose ﬁrst that all restriction maps are ﬁnite rank, and ﬁx an ordering of (k + 1)-cells of X, deﬁning the orthogonal projection operators i k+1 k+1 P : C (X ; F ) → C (X ; F ) sending stalks over (k + 1) cells of index greater i k than i to zero. Then P δ is a ﬁnite-rank operator and i k k P δ − δ ≤ F , σ τ j >i σ τ which goes to zero as i →∞. In the case that the restriction maps are compact but not ﬁnite rank, pick an approximating sequence for each by ﬁnite rank maps and combine the two approximations. k k An important note is that when C (X ; F ) is inﬁnite dimensional and δ is compact with ﬁnite dimensional kernel, the eigenvalues of Δ will accumulate at zero. This means that there will be no smallest nontrivial eigenvalue for such Laplacians. Most of the difﬁculties considered here already arise in the study of spectra of inﬁnite graphs. The standard Laplacian associated to an inﬁnite graph is bounded but not compact, while a proper choice of weights decaying at inﬁnity makes it compact. The study of sheaves of arbitrary Hilbert spaces on not-necessarily-ﬁnite cell com- plexes is interesting, and indeed suggests itself in certain applications. However, for the initial development and exposition of the theory, we have elected to focus on the (still quite interesting) ﬁnite-dimensional case. This is sufﬁcient for most applications we have envisioned, and avoids the need for repeated qualiﬁcations and restrictions. For the balance of this paper, we will assume that all cell complexes are ﬁnite and all vector spaces are ﬁnite dimensional, giving where possible proofs that generalize in some way to the inﬁnite-dimensional setting. Most results that do not explicitly require a ﬁnite complex will extend quite directly to the case of sheaves with com- pact coboundary operators. Proofs not relying on the Courant-Fischer theorem will typically apply even to situations where coboundary operators are merely bounded, although their conclusions may be somewhat weakened. 3.4 The normalized Laplacian and weights Many results in spectral graph theory rely on a normalized version of the standard graph Laplacian, which is typically deﬁned in terms of a rescaling of the standard 123 328 J. Hansen , R. Ghrist Laplacian. Let D be the diagonal matrix whose nonzero entries are the degrees of ver- −1/2 −1/2 tices; then the normalized Laplacian is L = D LD . This deﬁnition preserves the Laplacian as a symmetric matrix, but it obscures the true meaning of the normal- ization. The normalized Laplacian is the standard Laplacian with a different choice of −1/2 −1/2 −1 weights for the vertices. The matrix D LD is similar to D L, which is self adjoint with respect to the inner product x , y= x Dy. In this interpretation, each vertex is weighted proportionally to its degree. Viewing the normalization process as a reweighting of cells leads to the natural deﬁnition of normalized Laplacians for simplicial complexes given by Horak and Jost (2013). Indeed, following Horak and Jost’s deﬁnition for simplicial complexes, we propose the following extension to sheaves. Deﬁnition 3.5 Let F be a weighted cellular sheaf deﬁned on a regular cell complex X.Wesay F is normalized if for every cell σ of X and every x , y ∈ F (σ ) ∩ (ker δ) , δx,δy=x , y. Lemma 3.6 Given a weighted sheaf F on a ﬁnite-dimensional cell complex X, it is always possible to reweight F to a normalized version. Proof Note that if X has dimension k, the normalization condition is trivially satisﬁed for all cells σ of dimension k. Thus, starting at cells of dimension k −1, we recursively redeﬁne the inner products on stalks. If σ is a cell of dimension k − 1, let Π be the orthogonal projection F (σ ) → F (σ )∩ker δ. Then deﬁne the normalized inner product N N •, • on F (σ ) to be given by x , y =δ(id −Π )x,δ(id −Π )y+Π x,Π y. σ σ σ σ σ σ It is clear that this reweighted sheaf satisﬁes the condition of Deﬁnition 3.5 for cells of dimension k and k − 1. We may then perform this operation on cells of progressively lower dimension to obtain a fully normalized sheaf. Note that there is an important change of perspective here: we do not normalize the Laplacian of a sheaf, but instead normalize the sheaf itself, or more speciﬁcally, the inner products associated with each stalk of the sheaf. If we apply this process to a sheaf F on a graph G, there is an immediate inter- pretation in terms of the original sheaf Laplacian. Let D be the block diagonal of the standard degree 0 sheaf Laplacian, and note that for x ⊥ ker L, x , Dx is the reweighted inner product on C (G; F ). In particular, the adjoint of δ with † T † respect to this inner product has the form D δ , where D is the Moore-Penrose pseudoinverse of D, so that the matrix form of the reweighted Laplacian with respect to this inner product is D L. Changing to the standard basis then gives †/2 †/2 L = D LD . 3.5 Discrete vector bundles A subclass of sheaves of particular interest are those where all restriction maps are invertible.These sheaves have been the subject of signiﬁcantly more study than the general case, since they extend to locally constant sheaves on the geometric realization of the cell complex. The Riemann-Hilbert correspondence describes an equivalence between locally constant sheaves (or cosheaves) on X, local systems on 123 Toward a spectral theory of cellular sheaves 329 X, vector bundles on X with a ﬂat connection, and representations of the funda- mental groupoid of X. (See, e.g., Davis and Kirk 2001, ch. 5 or Zein and Snoussi 2009 for a discussion of some aspects of this correspondence.) When we represent a local system by a cellular sheaf or cosheaf, we will call it a discrete vector bun- dle. One way to understand the space of 0-cochains of a discrete vector bundle is as representing a subspace of the sections of a geometric realization of the associated ﬂat vector bundle, deﬁned by linear interpolation over higher-dimensional cells. The coboundary map can be seen as a sort of discretization of the connection, whose ﬂatness is manifest in the fact that δ = 0. Discrete vector bundles have some subtleties when we study their Laplacians. The sheaf-cosheaf duality corresponding to a local system, given by taking inverses of restriction maps, is not in general the same as the duality induced by an inner product on stalks. Indeed, these duals are only the same when the restriction maps are unitary— their adjoints must be their inverses. The inner product on stalks of a cellular sheaf has two roles: it gives a rel- ative weight to vectors in each stalk, but via the restriction maps also gives a relative weight to cells in the complex. This second role complicates our inter- pretation of certain sorts of vector bundles. For instance, one might wish to deﬁne an O(n) discrete vector bundle on a graph to be a cellular sheaf of real vector spaces where all restriction maps are orthogonal. However, from the per- spective of the degree-0 Laplacian, a uniform scaling of the inner product on an edge does not change the orthogonality of the bundle, but instead in some sense changes the length of the edge, or perhaps the degree of emphasis we give to discrepancies over that edge. So a discrete O(n)-bundle should be one where the restriction maps on each cell are scalar multiples of orthonormal maps. That is, for each cell σ , we have a positive scalar α , such that for every σ τ,the restriction map F is an orthonormal map times α /α . One way to think of this τ σ σ τ is as a scaling of the inner product on each stalk of F. Frequently, especially when dealing with graphs, we set α = 1 when dim(σ ) = 0, but this is not necessary. (Indeed, when dealing with the normalized Laplacian of a graph, we have α = d .) The rationale for this particular deﬁnition is that in the absence of a basis, inner products are not absolutely deﬁned, but only in relation to maps in or out of a space. Scaling the inner product on a vector space is meaningless except in relation to a given collection of maps, which it transforms in a uniform way. As a special case of this deﬁnition, it will be useful to think about weighted ver- sions of the constant sheaf. These are isomorphic to the ‘true’ constant sheaf, but not unitarily so. Weighted constant sheaves on a graph are analogous to weighted graphs. The distinction between the true constant sheaf and weighted versions arises because it is often convenient to think of the sections of a cellular sheaf as a sub- space of C (X ; F ). As a result, we often only want our sections to be constant on 0-cells, allowing for variation up to a scalar multiple on higher-dimensional cells. This notion will be necessary in Sect. 8.6 when we discuss approximations of cellular sheaves. 123 330 J. Hansen , R. Ghrist 3.6 Comparison with previous constructions Friedman, in Friedman (2015), gave a deﬁnition of a sheaf on a graph, developed a homology theory, and suggested constructing sheaf Laplacians and adjacency matri- ces. The suggestion that one might develop a spectral theory of sheaves on graphs has remained until now merely a suggestion. The graph connection Laplacian, introduced by Singer and Wu in Singer and Wu (2012), is simply the sheaf Laplacian of an O(n)-vector bundle over a graph. This construction has attracted signiﬁcant interest from a spectral graph theory perspec- tive, including the development of a Cheeger-type inequality (Bandeira et al. 2013) and a study of random walks and sparsiﬁcation (Chung and Zhao 2012). Connection Laplacian methods have proven enlightening in the study of synchronization problems. Others have approached the study of vector bundles, and in particular line bundles, over graphs without reference to the connection Laplacian, studying analogues of spanning trees and the Kirchhoff theorems (Kenyon 2011; Catanzaro et al. 2013). Other work on discrete approximations to connection Laplacians of manifolds has analyzed similar matrices (Mantuano 2007). Gao, Brodski, and Mukherjee developed a formulation in which the graph connec- tion Laplacian is explicitly associated to a ﬂat vector bundle on the graph and arises from a twisted coboundary operator (Gao et al. 2016). This coboundary operator is not a sheaf coboundary map and has some difﬁculties in its deﬁnition. These arise from a lack of freedom to choose the basis for the space of sections over an edge of the graph. Further work by Gao uses a sheaf Laplacian-like construction to study noninvertible correspondences between probability distributions on surfaces (Gao 2016). Wu et al. (2018) have recently proposed a construction they call a weighted simpli- cial complex and studied its associated Laplacians. These are cellular cosheaves where all stalks are equal to a given vector space and restriction maps are scalar multiples of the identity. Their work discusses the cohomology and Hodge theory of weighted simplicial complexes, but does not touch on issues related to the Laplacian spectrum. 4 Harmonicity As a prelude to results about the spectra of sheaf Laplacians, we will discuss issues related to harmonic cochains on sheaves. While these do not immediately touch on the spectral properties of the Laplacian, they are closely bound with its algebraic properties. 4.1 Harmonic extension Proposition 4.1 Let X be a regular cell complex with a weighted cellular sheaf F. Let B ⊆ X be a subcomplex and let x | ∈ C (B; F ) be an F-valued k-cochain speciﬁed k k on B. If H (X , B; F ) = 0, then there exists a unique cochain x ∈ C (X ; F ) which restricts to x | on B and is harmonic on S = X \B. In our terminology, Friedman’s sheaves are cellular cosheaves. 123 Toward a spectral theory of cellular sheaves 331 Proof A matrix algebraic formulation sufﬁces. Representing Δ in block form as partitioned by B and S, the relevant equation is k k Δ (S, S)Δ (S, B) x | 0 F F = . k k Δ (B, S)Δ (B, B) x | y F F Since y is indeterminate, we can ignore the second row of the matrix, giving the k k k k ∗ k equation Δ (S, S)x | + Δ (S, B)x | = 0. We can write Δ (S, S) = (δ | ) δ | + S B S S F F F k−1 ∗ ∗ k−1 ∗ ((δ ) | ) (δ ) | , which is very close to the k-th Hodge Laplacian of the relative S S cochain complex k−1 k k+1 ··· → C (X , B; F ) → C (X , B; F ) → C (X , B; F ) → ··· . Indeed, we can exploit the fact that this is a subcomplex of C (X ; F ) to compute its Hodge Laplacian in terms of the coboundary maps of C (X ; F ). The coboundary map • • δ of C (X , B; F ) is simply the restriction of the coboundary map δ of C (X ; F ) to k+1 k k k k k the subcomplex: δ = π δ i , where π is the orthogonal projection C (X ; F ) → S S S S k k k k k k C (X , B; F ) and i the inclusion C (X , B; F ) → C (X ; F ). Note that π and i are S S S k−1 k k adjoints, and that i π is the identity on im δ . We may therefore write the Hodge S S S Laplacian of the relative complex as k k ∗ k k−1 k−1 ∗ Δ (X , B; F ) = (δ ) δ + δ (δ ) S S S S k k ∗ k+1 k+1 k k k k−1 k−1 k−1 k−1 ∗ k = π (δ ) i π δ i + π δ i π (δ ) i S S S S S S S S k k ∗ k k k k−1 k−1 k−1 k−1 ∗ k = π (δ ) δ i + π δ i π (δ ) i . S S S S S S Meanwhile, we can write the submatrix k k k ∗ k k k k−1 k−1 ∗ k Δ (S, S) = π (δ ) δ i + π δ (δ ) i . F S S S S k k k It is then immediate that ker(Δ (S, S)) ⊆ ker Δ (X , B; F ), so that Δ (S, S) is F F invertible if H (X , B; F ) = 0. If we restrict to up- or down-Laplacians, a harmonic extension always exists, even k ∗ k k ∗ k if it is not unique. This is because, for instance, im(δ | ) δ | ⊆ im(δ | ) δ | .In S B S S particular, this implies that harmonic extension is always possible for 0-cochains, with uniqueness if and only if H (X , B; F ) = 0. 4.2 Kron reduction Kron reduction is one of many names given to a process of simplifying graphs with respect to the properties of their Laplacian on a boundary. If G is a con- nected graph with a distinguished set of vertices B, which we consider as a sort of boundary of G, Proposition 4.1 shows that there is a harmonic extension map B V (G) E : R → R . It is then possible to construct a graph G on B such that for 123 332 J. Hansen , R. Ghrist every function x on the vertices of G ,wehave L x = π L E (x ), where π is G B G B V (G) B the orthogonal projection map R → R . Indeed, letting S = V (G)\B,wehave −1 E (x )| =−L (S, S) L (S, B)x,so S G G −1 L x = π L E (x ) = L (B, B)x − L (B, S)L (S, S) L (S, B)x . B G G G G G Therefore, −1 L = L (B, B) − L (B, S)L (S, S) L (S, B), G G G G G that is, L is the Schur complement of the (B, B) block of L . It is also the Laplacian G G of a graph on B: Theorem 4.2 (see (Dörﬂer and Bullo 2013)) If L is the Laplacian of a con- nected graph G, and B a subset of vertices of G, then L = L (B, B) − G G −1 L (B, S)L (S, S) L (S, B) is the Laplacian of a graph with vertex set B. G G G A physically-inspired way to understand this result (and a major use of Kron reduc- tion in practice) is to view it as reducing a network of resistors given by G to a smaller network with node set B that has the same electrical behavior on B as the original net- work. In this guise, Kron reduction is a high-powered version of the Y -Δ and star-mesh transforms familiar from circuit analysis. Further discussion of Kron reduction and its various implications and applications may be found in Dörﬂer and Bullo (2013). Can we perform Kron reduction on sheaves? That is, given a sheaf F on a graph G with a prescribed boundary B, can we ﬁnd a sheaf F on a graph with vertex set B only such that for every x ∈ C (B; F ) we have L x = π 0 L E (x ), where B F F C (B;F ) B B E (x ) is the harmonic extension of x to G? The answer is, in general, no. Suppose we want to remove the vertex v from our graph, i.e., B = G\{v}.Let D = F F = L . To eliminate the vertex v ve v,v ve ve v we apply the condition (L (x , E (x )))(v) = 0, and take a Schur complement, −1 replacing L(B, B) with L(B, B) − L(B,v)D L(v, B). This means that we add to ∗ −1 ∗ the entry L(w, w ) the map F F D F F , where e is the edge between ve w e we ve v and w, and e the edge between v and w . This does not in general translate to a change in the restriction maps for the edge between w and w . In general, Kron reduction is not possible for sheaves. In particular, if x ∈ C (G; F ) is a section of F, its restriction to B must be a section of F . Conversely, if x is not a section, its restriction to B cannot be a section of F . B B But we can construct sheaves with a space of sections on the boundary that cannot be replicated with a sheaf on the boundary vertices only. For instance, take the star graph with three boundary vertices, with stalks R over boundary vertices and edges, and R over the internal vertex. Take as the restriction maps from the central vertex restriction onto the ﬁrst and second components, and addition of the two components. See Fig. 2 for an illustration. Note that a global section of this sheaf is determined by its value on the central vertex. If we label the boundary vertices counterclockwise starting at the top, the space of global sections for F must have as a basis 123 Toward a spectral theory of cellular sheaves 333 Fig. 2 A sheaf illustrating the general impossibility of Kron reduction ⎡ ⎤ ⎡ ⎤ 1 1 ⎣ ⎦ ⎣ ⎦ x = 1 , x = 0 . 1 2 0 1 But there is no sheaf on a graph with vertex set B which has this space of global sections. To see this, note that if x is a section, the map from F (v ) to F (v ) must be the zero 1 1 3 map, and similarly for the map from F (v ) to F (v ). Similarly, if x is a section, the 2 3 2 maps F (v ) → F (v ) and F (v ) → F (v ) must be zero. But this already shows that 1 2 3 2 the vector 10 0 must be a section, giving F a three-dimensional space of sections. The problem is that the internal node allows for constraints between boundary nodes that cannot be expressed by purely pairwise interactions. This fact is a fundamental obstruction to Kron reduction for general sheaves. However, there is a sheaf Kron reduction for sheaves with vertex stalks of dimension at most 1. This follows from the identiﬁcation of the Laplacians of such sheaves as the matrices of factor width two in Sect. 3.2.2. Theorem 4.3 The class of matrices of factor width at most two is closed under taking Schur complements. Proof By Theorems 8 and 9 of Boman et al. (2005), a matrix L has factor width at most two if and only if it is symmetric and generalized weakly diagonally dominant with nonnegative diagonal, that is, there exists a positive diagonal matrix D such that DL D is weakly diagonally dominant. Equivalently, these are the symmetric positive semideﬁnite generalized weakly diagonally dominant matrices. The class of gener- alized weakly diagonally dominant matrices coincides with the class of H-matrices, which are shown to be closed under Schur complements in Johnson and Smith (2005). Similarly, the class of symmetric positive deﬁnite matrices is closed under Schur complements, so the intersection of the two classes is also closed. 123 334 J. Hansen , R. Ghrist 4.3 Maximum modulus theorem Harmonic 0-cochains of an O(n)-bundle satisfy a local averaging property which leads directly to a maximum modulus principle. Lemma 4.4 Let G be a graph with an O(n)-bundle F, with constant vertex weights α = 1 and arbitrary edge weights α (as deﬁned in Sect. 3.5).If x ∈ C (G; F ) is v e harmonic at a vertex v, then x = F F x , v we w ve v,we v=w 2 2 where d = F = α . v ve ve ve e Proof The block row of L corresponding to v has entries −F F off the diago- F we ve nal and F F = F id on the diagonal. The harmonicity ve ve F (v) ve ve ve condition is then d x − F F x = 0. v v we w ve v,we v=w Theorem 4.5 (Maximum modulus principle) Let G be a graph, and B be a thin subset of vertices of G; that is, G\B is connected, and every vertex in B is connected to a vertex not in B. Let F be an O(n)-bundle on G with a = 1 for all v ∈ G, and suppose x ∈ C (G; F ) is harmonic on G\B. Then if x attains its maximum stalkwise norm at a vertex in G\B, it has constant stalkwise norm. Proof Note that for a given edge e = v ∼ w, F and F are both α times an ve ue e ∗ 2 orthogonal map, so F F is α times an orthogonal map. Let v ∈ G\B and we ve suppose x ≥x for all w ∈ G. Then this holds in particular for neighbors of v, v w so that we have 1 1 ∗ ∗ x = F F x ≤ F F x v we w we w ve ve d d v v v,we v,we v=w v=w 1 1 2 2 = α x ≤ α x =x , w v v e e d d v v v,we ve v=w Equality holds throughout, which, combined with the assumption that x ≥x v w for all w, forces x =x for w ∼ v. We then apply the same argument to every v w vertex in G\B adjacent to v, and, after iterating, the region of constant stalkwise norm extends to all of G\B because this subgraph is connected. But since every vertex b ∈ B 123 Toward a spectral theory of cellular sheaves 335 is adjacent to some vertex w ∈ G\B, the same argument applied to the neighborhood of w forces x =x . So any harmonic function that attains its maximum modulus b w on G\B has constant modulus. Corollary 4.6 Let B be a thin subset of vertices of G, and F an O(n)-bundle on G as before. If x ∈ C (G; F ) is harmonic on G\B, then it attains its maximum modulus on B. The constant sheaf on a graph is an O(n)-bundle, so this result gives a maximum modulus principle for harmonic functions on the vertices of a graph. A slightly stronger result in this vein, involving maxima and minima of x, is discussed in Sunada (2008). The thinness condition for B is not strictly necessary for the corollary to hold—there are a number of potential weakenings of the condition. For instance, we might simply require that there exists some w ∈ B such that for every vertex v ∈ G\B there exists a path from v to w not passing through B. 5 Spectra of sheaf Laplacians The results in this section are straightforward generalizations and extensions of familiar results from spectral graph theory. Most are not particularly difﬁcult, but they illustrate the potential for lifting nontrivial notions from graphs and complexes to sheaves. It is useful to note a few basic facts about the spectra of Laplacians arising from Hodge theory. Proposition 5.1 The nonzero spectrum of Δ is the disjoint union of the nonzero spec- k k tra of Δ and Δ . + − Proof We take advantage of the Hodge decomposition, noting that C (X ; F ) = k k k ker Δ ⊕ im Δ ⊕ im Δ . This is an orthogonal decomposition, and = 0as well − + k k as Δ | k = 0. Further, since ker Δ = ker Δ ∩ ker Δ , both restrict to + − (im Δ ) k k zero on the kernel of Δ . We therefore see that Δ is the orthogonal direct sum k k k 0| k ⊕ Δ | k ⊕ Δ | k , and hence the spectrum of Δ is the union of the ker Δ + (im Δ ) − (im Δ ) + − spectra of these three operators. k+1 Proposition 5.2 The nonzero eigenvalues of Δ and Δ are the same. + − k+1 k k ∗ k k k ∗ Proof We have Δ = (δ ) δ and Δ = δ (δ ) . The eigendecompositions of + − these matrices are determined by the singular value decomposition of δ , and the nonzero eigenvalues are precisely the squares of the nonzero singular values of δ . One reason for the study of the normalized graph Laplacian is that its spectrum is bounded above by 2 (Chung 1992), and hence normalized Laplacian spectra of different graphs can be easily compared. A similar result holds for up-Laplacians of normalized simplicial complexes (Horak and Jost 2013): the eigenvalues of the degree- k up-Laplacian of a normalized simplicial complex are bounded above by k + 2. This fact extends to normalized sheaves on simplicial complexes. This result and others in this paper will rely on the Courant-Fischer theorem, which we state here for reference. 123 336 J. Hansen , R. Ghrist Deﬁnition 5.3 Let A be a self-adjoint operator on a Hilbert space V.If x ∈ V,the Rayleigh quotient corresponding to x and A is x , Ax R (x ) = . x , x Theorem 5.4 (Courant-Fischer) Let A beann × n Hermitian matrix with eigenvalues λ ≤ λ ≤ ··· ≤ λ . Then 1 2 n λ = min max R (x ) = max min R (x ). k A A dim V =k x ∈V dim V =n−k+1 x ∈V The proof is immediate once one uses the fact that A is unitarily equivalent to a diagonal matrix. Proposition 5.5 Suppose F is a normalized sheaf on a simplicial complex X. The eigenvalues of the degree k up-Laplacian L are bounded above by k + 2. Proof By the Courant-Fischer theorem, the largest eigenvalue of L is equal to k k x , L x δ x,δ x max = max k k k k x ∈C (X ;F ) x , x x ⊥ker δ δ x ,δ x σ σ dim σ =k [σ : τ ][σ : τ ]F x , F x σ τ σ σ τ σ dim τ =k+1 σ,σ τ = max . F x , F x x ⊥ker δ σ τ σ σ τ σ dim σ =k σ τ Note that for σ = σ , [σ : τ ][σ : τ ]F x , F x ≤F x F x σ τ σ σ τ σ σ τ σ σ τ σ 2 2 ≤ F x +F x σ τ σ τ σ by the Cauchy-Schwarz inequality. In particular, then, the term of the numerator cor- responding to each τ of dimension k + 1 is bounded above by 2 2 2 F x + F x +F x σ τ σ σ τ σ σ τ σ σ τ σ =σ τ = (k + 2) F x , σ τ σ σ τ by counting the number of times each term F x appears in the sum. Meanwhile, σ τ σ the denominator is equal to F x , so the Rayleigh quotient σ τ σ dim τ =k+1 σ τ is bounded above by k + 2. 123 Toward a spectral theory of cellular sheaves 337 5.1 Eigenvalue interlacing Deﬁnition 5.6 Let A, B be n × n matrices with real spectra. Let λ ≤ λ ≤ ··· ≤ λ 1 2 n be the eigenvalues of A and μ ≤ μ ≤ ··· ≤ μ be the eigenvalues of B.We 1 2 n say the eigenvalues of A are (p, q)-interlaced with the eigenvalues of B if for all k, λ ≤ μ ≤ λ .(We let λ = λ for k < 1 and λ = λ for k > n.) k− p k k+q k 1 k n The eigenvalues of low-rank perturbations of symmetric positive semideﬁnite matri- ces are related by interlacing. The following is a standard result: Theorem 5.7 Let A and B be positive semideﬁnite matrices, with rank B = t. Then the eigenvalues of A are (t , 0)-interlaced with the eigenvalues of A − B. Proof Let μ be the k-th largest eigenvalue of A − B and λ the k-th largest eigenvalue k k of A. By the Courant-Fischer theorem, we have y, Ay−y, By μ = min max dim Y =k y∈Y ,y=0 y, y y, Ay ≥ min max dim Y =k y∈Y ∩ker B,y=0 y, y y, Ay ≥ min max = λ k−t dim Y =k−t y∈Y ,y=0 y, y and y, Ay λ = min max dim Y =k y∈Y ,y=0 y, y y, Ay−y, By ≥ min max = μ . dim Y =k y∈Y ,y=0 y, y This result is immediately applicable to the spectra of sheaf Laplacians under the deletion of cells from their underlying complexes. The key part is the interpretation of the difference of the two Laplacians as the Laplacian of a third sheaf. Let F be a sheaf on X, and let C be an upward-closed set of cells of X, with Y = X \C.The inclusion map i : Y → X induces a restriction of F onto Y , the pullback sheaf i F. k k Consider the Hodge Laplacians Δ and Δ .If C contains cells of dimension k, F i F these matrices are different sizes, but we can derive a relationship by padding Δ i F with zeroes. Equivalently, this is the degree-k Laplacian of F with the restriction maps incident to cells in C set to zero. Proposition 5.8 Let G be the sheaf on X with the same stalks as F but with all restriction maps between cells not in C set to zero. The eigenvalues of Δ i F k k are (t , 0)-interlaced with the eigenvalues of Δ , where t = codim H (X ; G) = k k dim C (X ; F ) − dim H (X ; G). Such subtle moves are part and parcel of a sheaf-theoretic perspective. 123 338 J. Hansen , R. Ghrist Similar results can be derived for the up- and down-Laplacians. Specializing to graphs, interlacing is also possible for the normalized degree 0 sheaf Laplacian. The Rayleigh quotient for the normalized Laplacian L ∗ is i F −1/2 −1/2 x , D L ∗ D x y, L ∗ y y, L y−y, L y ∗ i F ∗ i F F G i F i F = = , x , x y, D ∗ y y, D y−y, D y i F F G −1/2 where we let y = D x. Then if {λ } are the ordered eigenvalues of L and {μ } ∗ k F k i F are the ordered eigenvalues of L ,wehave i F y, L y−y, L y F G μ = min max dim Y =k y∈Y ,y=0 y, D y−y, D y F G y, L y ≥ min max dim Y =k y, D y−y, D y y∈Y ∩H (X ;G),y=0 F G y, L y ≥ min max dim Y =k y, D y y∈Y ∩H (X ;G),y=0 y, L y ≥ min max = λ k−t dim Y =k−t y∈Y ,y=0 y, D y y, L y−y, L y F G μ = max min dim Y =n−k+1 y∈Y ,y=0 y, D y−y, D y F G y, L y ≤ max min dim Y =n−k+1 y, D y−y, D y y∈Y ∩H (X ;G),y=0 F G y, L y ≤ max min dim Y =n−k+1 y, D y y∈Y ∩H (X ;G),y=0 y, L y ≤ max min = λ k+t dim Y =n−k−t +1 y∈Y ,y=0 y, D y Therefore, the eigenvalues of the normalized Laplacians are (t , t )-interlaced. This generalizes interlacing results for normalized graph Laplacians. 5.2 Sheaf morphisms Proposition 5.9 Suppose ϕ : F → G is a morphism of weighted sheaves on a regular k+1 k k ∗ k k cell complex X. If ϕ is a unitary map, then L = (ϕ ) L ϕ . F G k+1 F G k F ∗ k+1 ∗ k+1 Proof The commutativity condition ϕ δ = δ ϕ implies that (δ ) (ϕ ) ϕ F k ∗ G ∗ G k k ∗ k k k+1 ∗ k+1 δ = (ϕ ) (δ ) δ ϕ = (ϕ ) L ϕ . Thus if (ϕ ) ϕ = id ,wehave k+1 C (X ;F ) k k ∗ k k k+1 L = (ϕ ) L ϕ . This condition holds if ϕ is unitary. F G An analogous result holds for the down-Laplacians of F, and these combine to a result for the full Hodge Laplacians. 123 Toward a spectral theory of cellular sheaves 339 5.3 Cell complex morphisms The following constructions are restricted to locally injective cellular morphisms, as discussed in Sect. 2.1. Recall that under these morphisms, cells map to cells of the same dimension and the preimage of the star of a cell is a disjoint union of subcomplexes, on each of which the map acts injectively. The sheaf Laplacian is invariant with respect to pushforwards over such maps: Proposition 5.10 Let X and Y be cell complexes, and let f : X → Y bealocally injective cellular morphism. If F is a sheaf on X, the kth coboundary Laplacian corresponding to f F on Y is the same (up to a unitary change of basis) as the kth coboundary Laplacian of F on X. Corollary 5.11 The sheaves F and f F are isospectral for the coboundary Laplacian. k k Proof There is a canonical isometry f : C (X , F ) → C (Y , f F ), which is given k ∗ on stalks by the obvious inclusion f : F (σ ) → f F ( f (σ )) = F (τ ). σ ∗ f (τ )= f (σ ) For σ σ , f commutes with the restriction map F and hence f commutes with σ σ σ k the coboundary map. But this implies that: k k ∗ k k ∗ ∗ k ∗ k ∗ k ∗ k L = (δ ) δ = (δ ) f f δ = f (δ ) δ f = f L f . (k+1) k k f F f F f F f F (k+1) f F k F F k F ∗ ∗ ∗ ∗ ∗ General locally injective maps behave nicely with sheaf pushforwards, and covering maps behave well with sheaf pullbacks. Recall that a covering map of cell complexes is a locally injective map f : C → X such that for every cell σ ∈ X, f is an −1 isomorphism on the disjoint components of f (st(σ )). Proposition 5.12 Let f : C → X be a covering map of cell complexes, with F a sheaf k k on X. Then for any k, the spectrum of L is contained in the spectrum of L . F f F k k ∗ Proof Consider the lifting map ϕ : C (X ; F ) → C (C ; f F ) given by x → x ◦ f . This map commutes with δ and δ . The commutativity with δ follows immediately from the proof of the contravariant functoriality of cochains. The commutativity with δ is more subtle, and relies on the fact that f is a covering map. k ∗ k+1 For y ∈ C (C ; f F ) and x ∈ C (X ; F ),wehave ∗ ∗ y,δ ϕx=δy,ϕx= [σ : τ ] f F (y ), (ϕx ) σ τ σ τ σ ,τ ∈P σ τ = [σ : τ ] F (y ), x σ τ σ τ −1 σ,τ ∈P X σ ∈ f (σ ) σ τ = [σ : τ ]F (ϕ y) , x σ τ σ τ σ,τ ∈P σ τ ∗ ∗ =δϕ y, x=y,ϕδ x . 123 340 J. Hansen , R. Ghrist k k k k k k ∗ ∗ Now, if L x = λx,wehave L ϕx = (δ ) δ ϕx = ϕ(δ ) δ x = ∗ ∗ ∗ F f F f F f F F F k k ϕL x = λϕx,so λ is an eigenvalue of L . F f F Even if f : Y → X is not quite a covering map, it is still possible to get some information about the spectrum of f F. For instance, for dimension-preserving cell maps with uniform ﬁber size we have a bound on the smallest nontrivial eigenvalue of the pullback: Proposition 5.13 Suppose f : Y → Xis a dimension-preserving map of regular −1 cell complexes such that for dim(σ ) = d, f (σ ) = is constant, and let F be a sheaf on X. If λ (F ) is the smallest nontrivial eigenvalue of L , then λ (F ) ≥ k k d ∗ λ ( f F ). d+1 Proof Let x be an eigenvector corresponding to λ (F ). Note that since every ﬁber is the same size, the lift ϕ preserves the inner product up to a scaling. That is, if y and z are d-cochains, ϕy,ϕz= y, z. This means that the pullback of x is orthogonal to the pullback of any cochain in the kernel of L . Therefore, we have δx,δx ϕδx,ϕδx δϕx,δϕx d d d λ (F ) = = = ≥ λ ( f F ). k k x , x ϕx,ϕx ϕx,ϕx d+1 d+1 d+1 5.4 Product complexes If X and Y are cell complexes, their product X × Y is a cell complex with cells σ × τ for σ ∈ X, τ ∈ Y , and incidence relations (σ × τ)(σ × τ ) whenever σ σ and τ τ . The dimension of σ × τ is dim(σ ) + dim(τ ). The complex X × Y possesses projection maps π and π onto X and Y . X Y Deﬁnition 5.14 If F and G are sheaves on X and Y , respectively, their product is the ∗ ∗ sheaf F G = π F ⊗ π G. Equivalently, we have (F G)(σ × τ) = F (σ ) ⊗ F (τ ) X Y and (F G) = F ⊗ G . σ ×τ σ ×τ σ σ τ τ Proposition 5.15 If L and L are the degree-0 Laplacians of F and G, the degree-0 F G Laplacian of F G is L = id 0 ⊗L + L ⊗ id 0 . F G G F C (X ;F ) C (Y ;G) Proof The vector space C (X × Y ; F G) has a natural decomposition into two subspaces: one generated by stalks of the form F (v) ⊗ G(e) for v avertexof X and e an edge of Y , and another generated by stalks of the opposite form F (e) ⊗ G(v).This induces an isomorphism 1 0 1 1 0 C (X × Y ; F G) = (C (X ; F ) ⊗ C (Y ; G)) ⊕ (C (X ; F ) ⊗ C (Y ; G)). Then the coboundary map of F G can be written as the block matrix id ⊗δ C (X ;F ) δ = . F G δ ⊗ id C (Y ;G) 123 Toward a spectral theory of cellular sheaves 341 ∗ ∗ ∗ A quick computation then gives L = δ δ = id ⊗δ δ + δ δ ⊗ F G F G G F C (X ;F ) F G G F id 0 = id 0 ⊗L + L ⊗ id 0 . G F C (Y ;G) C (X ;F ) C (Y ;G) Corollary 5.16 If the spectrum of L is {μ } and the spectrum of L is {λ } , then i i j j F G the spectrum of L is {μ + λ } . i j ij F G For higher degree Laplacians, this relationship becomes more complicated. For instance, the degree-1 up-Laplacian is computed as follows: ⎡ ⎤ id 0 ⊗δ 0 C (X ;F ) ⎢ ⎥ 0 0 δ = δ ⊗ id 1 id 1 ⊗δ . ⎣ ⎦ C (Y ;G) C (X ;F ) F G F G 0 δ ⊗ id C (Y ;G) 1 0 0 ∗ 0 id 0 ⊗L + L ⊗ id 1 (δ ) ⊗ δ C (X ;F ) C (Y ;G) 1 G F F G L = . F G 0 0 0 1 δ ⊗ (δ ) id 1 ⊗L + L ⊗ id 0 C (X ;F ) C (Y ;G) F G G F Because L is given by a block matrix in terms of various Laplacians and cobound- F G ary maps of F and G, computing its spectrum is more involved. When X and Y are graphs, this simpliﬁes signiﬁcantly and it is possible to compute the spectrum in terms of the spectra of F and G. Proposition 5.17 Suppose X and Y are graphs, with F and G sheaves on X and Y . 0 0 If v is an eigenvector of L with eigenvalue λ and v an eigenvector of L with F G F G λ 0 v ⊗ δ v F G μ G eigenvalue μ, then the vector v = is an eigenvector of L F G F G δ v ⊗ v F G λ F with eigenvalue λ + μ. Proof A computation. ⎡ ⎤ λ 0 0 0 ∗ 0 v ⊗ δ v L ⊗ id 1 (δ ) ⊗ δ F G μ G C (Y ;G) 1 F F G ⎣ ⎦ L v = F G F G 0 0 0 δ ⊗ (δ ) id 1 ⊗L 0 C (X ;F ) δ v ⊗ v F G G F G λ F ⎡ ⎤ ⎡ ⎤ λ 0 λ 0 + λv ⊗ δ v v ⊗ δ v F G F G μ λ G μ G ⎢ ⎥ ⎣ ⎦ = (λ + μ) ⎣ ⎦ λ μ 0 μ 0 + μδ v ⊗ v δ v ⊗ v F G F G μ λ F λ F A simpler way to obtain nearly the same result is to recall from Proposition 5.2 that 1 ∗ 1 1 1 ∗ (δ ) δ and δ (δ ) have the same spectrum up to the multiplicity of F G F G F G F G zero. But when X and Y are graphs, 1 1 ∗ 1 1 δ (δ ) = (Δ ) ⊗ id + id ⊗(Δ ) , 1 1 F G − C (Y ;G) C (X ;F ) − F G F G 123 342 J. Hansen , R. Ghrist 1 0 and since the nonzero eigenvalues of (Δ ) are the same as those of L , we obtain 1 0 a correspondence between eigenvalues of L and sums of eigenvalues of L and F G F L . However, for higher-dimensional complexes and higher-degree Laplacians, there appears to be no general simple formula giving the spectrum of F G in terms of the spectra of F and G. Indeed, we suspect that no such formula can exist, i.e., that the spectrum of F G is not in general determined by the spectra of F and G. 6 Eﬀective resistance Effective resistance is most naturally deﬁned for weighted cosheaves, but since every weighted sheaf has a canonical dual weighted cosheaf, the following deﬁnition applies to weighted sheaves as well. Deﬁnition 6.1 Let F be a cosheaf on a cell complex X, and let a, b ∈ ker(∂ ) be k F homologous k-cycles. The effective resistance R (a, b) is given by the solution to eff the optimization problem min c s.t. ∂ c = b − a. (6.1) k+1 c∈C (X ;F ) k+1 Proposition 6.2 Cosheaf effective resistance may be computed by the formula k † k ∗ R (a, b) =b − a,(L ) (b − a), where L is the up Laplacian ∂ ∂ . eff k+1 k+1 F F † † † ∗ Proof By a standard result about matrix pseudoinverses, (L ) = (∂ ) ∂ ,so k+1 k+1 † † † k † 2 b − a,(L ) (b − a)=∂ (b − a), ∂ (b − a)=∂ (b − a) .But if F k+1 k+1 k+1 b − a ∈ im ∂ , then ∂ (b − a) is the minimizer of the optimization problem (6.1). k+1 k+1 The condition that a and b be homologous becomes trivial if H (X ; F ) = 0. Note that if F is the constant cosheaf on a graph, a 0-cycle supported on a vertex v is homologous to a 0-cycle supported on a vertex w if their values are the same. This means that the deﬁnition of cosheaf effective resistance recovers the deﬁnition of graph effective resistance. For any cosheaf on a cell complex, we can get a measure of effective resistance over a (k +1)-cell σ by using the boundary map restricted to σ . Any choice of c ∈ F (σ ) gives an equivalence class of pairs of homologous k-cycles supported inside the boundary of σ . That is, we can decompose ∂c into the sum of two k-cycles in a number of equivalent ways. For instance, if σ is a 1-simplex with two distinct incident vertices, there is a natural decomposition of ∂c into a sum of two 0-cycles, one supported on each vertex. This gives a quadratic form on F (σ ): R (σ )(x ) =∂x , L ∂x . The choice eff of decomposition does not affect the quadratic form. Of course, by the inner product pairing, this quadratic form can be represented as a matrix (∂| ) L ∂| .In F (σ ) F (σ ) particular, this deﬁnes a matrix-valued effective resistance over an edge for a cosheaf on a graph. 123 Toward a spectral theory of cellular sheaves 343 6.1 Sparsification Graph effective resistance has also attracted attention due to its use in graph sparsiﬁ- cation. The goal when sparsifying a graph G is to ﬁnd a graph H with fewer edges that closely preserves properties of G. One important property we might wish to preserve is the size of boundaries of sets of vertices. If S is a set of vertices, we let |∂ S| be the sum of the weights of edges between S and its complement. We can compute this in terms of the Laplacian of G: |∂ S| = 1 L 1 , where 1 is the indicator vector on the G S S set S.If H well approximates G in this sense, we would like to have a relation like T T T (1 − )1 L 1 ≤ 1 L 1 ≤ (1 + )1 L 1 for every set S of vertices. Indeed, we G S H S G S S S S could strengthen this condition by requiring this to hold for all vectors in C (G; R), not just indicators of sets of vertices. The resulting relationship between the Laplacians of G and H is described by the Loewner order on positive semideﬁnite matrices. Deﬁnition 6.3 The Loewner order on the cone of symmetric positive deﬁnite matrices of size n × n is given by the relation A B if B − A is positive semideﬁnite. T T n Equivalently, A B if and only if x Ax ≤ x Bx for all x ∈ R . By the Courant-Fischer theorem, the relation A B has important implications for the eigenvalues and eigenvectors of these matrices. In particular, λ (B) ≥ λ (A) max max and λ (A) ≤ λ (B).If (1−)A B (1+)B, the eigenvalues and eigenvectors min min of B are constrained to be close to those of A. Thus, it is appropriate to call this relationship a spectral approximation of A by B. Spielman and Srivastava famously used effective resistances to construct spectral sparsiﬁers of graphs (Spielman and Srivastava 2008). This approach extends to sheaves on graphs: just as graph Laplacians can be spectrally approximated by Laplacians of sparse graphs, so too can sheaf Laplacians be spectrally approximated by Laplacians of sheaves on sparse complexes. Theorem 6.4 Let X be a regular cell complex of dimension d and F a cosheaf on X with dim C (X ; F ) = n. Given > 0 there exists a subcomplex X ⊆ X with the d−1 −2 same (d − 1)-skeleton and O( n log n) d-cells, together with a cosheaf F on X d−1 d−1 d−1 such that (1 − )L L (1 + )L . F F F d−1 Proof If ker L = 0, then an equivalent condition to the conclusion is 1 1 d−1 − d−1 d−1 − 2 2 λ ((L ) L (L ) ) ≤ 1 + max F F F and 1 1 d−1 − d−1 d−1 − 2 2 λ ((L ) L (L ) ) ≥ 1 − . min F F F d−1 d−1 If ker L is nontrivial, we use the pseudoinverse of L and restrict to the F F orthogonal complement of the kernel. This only offers notational difﬁculties, so in the following we will calculate as if the kernel were trivial. 123 344 J. Hansen , R. Ghrist Consider the restrictions of ∂ to each d-cell σ , and note that ∗ d−1 (∂ | )(∂ | ) = L . d σ d σ dim(σ )=d For each d-cell σ , we will choose σ to be in X with probability −2 p = min(1, 4 log(n) tr(R (σ ))). σ eff If σ is chosen to be in X , we choose its extension maps to be F = F . σ • σ • p Let A be independent Bernoulli random variables with E[A ]= p and let σ σ σ 1 1 1 d−1 d−1 − ∗ − 2 2 X = A (L ) (∂ | )(∂ | ) (L ) . Note that by construction X = σ σ d σ d σ σ p F F 1 1 d−1 − d−1 d−1 − 2 2 (L ) L (L ) and F F F 1 1 d−1 − d−1 d−1 − 2 2 E X = (L ) L (L ) = id σ C (X ;F ) d−1 F F F We wish to show that the eigenvalues of X are close to those of its expectation, for which we use a matrix Chernoff bound proven in Tropp (2012). This bound requires a bound on the norms of X : 1 1 1 d−1 d−1 − ∗ − 2 2 X ≤ (L ) (∂ | )(∂ | ) (L ) σ d σ d σ F F 1 1 1 d−1 − ∗ d−1 − 2 2 ≤ tr((L ) (∂ | )(∂ | ) (L ) ) d σ d σ F F 1 tr(R (σ )) eff ∗ d−1 † ≤ tr((∂| ) (L ) ∂ ) = . σ σ p p σ σ We can apriori subdivide any X with p = 1 into sufﬁciently many independent σ σ random variables so that their norms are as small as necessary. This does not affect the hypotheses of the concentration inequality, so we consider the case where p < 1, where X ≤ . Our matrix Chernoff bound then gives 4log n 1 1 −4 d−1 − d−1 d−1 − −2 −1 2 2 P λ ((L ) L (L ) ) ≤ 1 − ≤ n exp log n = n min F F F 1 1 −4 d−1 − d−1 d−1 − −2 −1/3 2 2 P λ ((L ) L (L ) ) ≥ 1 + ≤ n exp log n = n . max F F F When n is not trivially small there is therefore a high probability of L - approximating L . 123 Toward a spectral theory of cellular sheaves 345 We now check the expected number of d-cells in X .Thisis −2 p ≤ 4 log n tr(R (σ )), σ eff σ σ and ∗ d−1 −1 d−1 −1 ∗ tr(R (σ )) = tr((∂| ) (L ) ∂| ) = tr((L ) ∂ (∂| ) ) eff σ σ σ σ F F σ σ σ d−1 −1 ∗ d−1 −1 d−1 = tr (L ) ∂ (∂| ) = tr((L ) L ) ≤ n. σ σ F F F A standard Chernoff bound argument with the Bernoulli random variables determin- ing whether each cell is included then shows that the number of d-cells is concentrated −2 around its expectation and thus can be chosen to be O( n log n). The proof given here follows the outline of the proof for graphs given by Spielman in Spielman (2015). This newer proof simpliﬁes the original proof in Spielman and Srivastava (2008), which used a sampling of edges with replacement. Theorem 6.4 generalizes a number of theorems on sparsiﬁcation of graphs and simplicial complexes (Spielman and Teng 2011; Chung and Zhao 2012; Osting et al. 2017); however, it is not the most general sparsiﬁcation theorem. Indeed, the core argument does not rely on the cell complex structure, but only on the decomposition of the Laplacian into a sum of matrices, one corresponding to each cell. More general, and stronger, theorems about sparsifying sums of symmetric positive semideﬁnite matrices have been proven, such as the following from De Carli Silva et al. (2016): Theorem 6.5 (De Carli Silva et al. 2016) Let B ,..., B be symmetric, positive 1 m semideﬁnite matrices of size n × n and arbitrary rank. Set B := B . For any ∈ (0, 1), there is a deterministic algorithm to construct a vector y ∈ R with O(n/ ) nonzero entries such that y is nonnegative and B y B (1 + )B. i i i =1 3 2 The algorithm runs in O(mn / ) time. Moreover, the result continues to hold if the input matrices B ,..., B are Hermitian and positive semideﬁnite. 1 m The sheaf theoretic perspective, though not the most general or powerful possible, nevertheless maintains both a great deal of generality along with a geometric interpreta- tion of sparsiﬁcation in terms of an effective resistance. This geometric interpretation may then be pursued to develop efﬁcient methods for approximating the effective resistance and hence fast algorithms for sparsiﬁcation of cell complexes and cellular sheaves atop them. 123 346 J. Hansen , R. Ghrist 7 The Cheeger inequality 7.1 The Cheeger inequality for O(n)-bundles Recall from Sect. 3.5 the notion of an O(n)-bundle on a graph. Bandeira, Singer, and Spielman proved an analogue to the graph Cheeger inequality for O(n)-bundles (Ban- deira et al. 2013). Their goal was to give guarantees on the performance of a spectral method for ﬁnding an approximate section to a principal O(n)-bundle over a graph. For an O(n)-bundle on a graph with Laplacian L, degree matrix D and normalized −1/2 −1/2 Laplacian L = D LD , they deﬁned the frustration of a 0-cochain x to be x , Lx x , Lx η(x ) = = , x , Dx x , x and showed that any 0-cochain can be rounded to one with controlled frustration as follows. Given a 0-cochain x and a threshold κ ≥ 0, let x be the cochain whose value at a vertex v is x /x if x ≥ κ and is zero otherwise. For any such x there v v v exists a κ such that η(x ) ≤ 10η(x ). Taking the minimum over all 0-cochains x then implies that if λ (L) is the smallest eigenvalue of L, λ (L) ≤ min η(x ) ≤ 10λ (L). (7.1) 1 1 x =1or0 A natural question is whether this theorem extends to a more general class of sheaves on graphs. One reasonable candidate for extension is the class of sheaves on graphs where all restriction maps are partial isometries, i.e., maps which are unitary on the orthogonal complement of their kernels. One might view these as O(n)-bundles where the edge stalks have been reduced in dimension by an orthogonal projection. However, the cochain rounding approach does not work for these sheaves, as the following simple counterexample shows. Let G be a graph with two vertices and one edge, and let F (v ) = F (v ) = R and F (e) = R. Then let F =[10] and 1 2 v e √ 1 1 3 u F = . Then let x = and x = . Then η(x ) = 0, but η(x )> 0 v v v e 2 2 2 1 2 0 0 for any choice of u < 1. This means that there cannot exist any function f : R → R with f (0) = 0 such that η(x ) ≤ f (η(x )). This example does not immediately show that the Cheeger inequality (7.1)isfalse for this class of sheaves, since this sheaf does have a section of stalkwise norm 1, but it does offer a counterexample to the key lemma in the proof. Indeed, a more complicated family of counterexamples exists with sheaves that have no global sections. These counterexamples show that an approach based on variational principles and rounding is unlikely to prove an analogue of the results of Bandeira et al. for more general classes of sheaves. 123 Toward a spectral theory of cellular sheaves 347 7.2 Toward a structural Cheeger inequality Many extensions of the graph Cheeger inequality view it from the perspective of a constrained optimization problem over cochains. This is the origin of the Cheeger inequality for O(n)-bundles, and of the higher-dimensional Cheeger constants pro- posed by Gromov, Linial and Meshulam, and others (Linial and Meshulam 2006; Gromov 2010; Parzanchevski et al. 2016). However, a sheaf gives us more structure to work with than simply cochains. The traditional Cheeger inequality for graphs is frequently stated as a graph cutting problem: what is the optimal cut balancing the weight of edges removed with the sizes of the resulting partition? If we take the constant sheaf on a graph G, we can represent a cut of G by setting some restriction maps to 0, or, more violently, setting the edge stalks on the cut to be zero-dimensional. Thus, a potential analogue to the Cheeger constant for sheaves might be an optimal perturbation to the structure of the sheaf balancing the size of the perturbation with the size of the support of a new global section that the perturbation induces. For instance, we might measure the size of a perturbation of the sheaf’s restriction maps in terms of the square of the Frobenius norm · of the coboundary matrix. If we minimize δ − δ , a natural relaxation to the space of all matrices shows that F F this value is greater than λ (L ). 1 F 8 Toward applications The increase in abstraction and technical overhead implicit in lifting spectral graph theory to cellular sheaves is nontrivial. However, given the utility of spectral graph theory in so many areas, the generalization to sheaves would appear to be a good investment. As this work is an initial survey of the landscape, we quickly sketch a collection of potential applications. These sketches are brief enough to allow the curious to peruse, while providing experts with enough to construct details as needed. 8.1 Distributed consensus Graph Laplacians and adjacency matrices play an important role in the study and design of distributed dynamical systems. This begins with the observation that the continuous-time dynamical system on a set of real variables {x : v ∈ V (G)} indexed by the vertices of a graph G with Laplacian L, x˙ =−Lx , is local with respect to the graph structure: the only terms that inﬂuence x˙ are the x for w adjacent to v. Further, if the graph is connected, diagonalization of L shows that the ﬂow of this dynamical system converges to a consensus—the average of the initial condition. A similar observation holds for sheaves of ﬁnite-dimensional vector spaces on graphs: 123 348 J. Hansen , R. Ghrist Proposition 8.1 Let F be a sheaf on a cell complex X. The dynamical system x˙ = −Δ x has as its space of equilibria H (X ; F ), the space of harmonic k-cochains of F. The trajectory of this dynamical system initialized at x converges exponentially quickly to the orthogonal projection of x onto H (X ; F ). −t Δ Proof This is a linear dynamical system with ﬂows given by x (t ) = e x . Since k k Δ is self-adjoint, it has an orthogonal eigendecomposition Δ = V V , so that F F −t ∗ −t λ ﬂows are given by x (t ) = Ve V x = e v , x v .Thetermsofthissumfor 0 i 0 i λ > 0 converge exponentially to zero, while the terms with λ = 0 remain constant, i i so that the limit as t →∞ is v , x v . Since the v are orthonormal, i 0 i i v ∈H (X ;F ) this is an orthogonal projection onto H (X ; F ). In particular, for k = 0, this result implies that a distributed system can reach consensus on the nearest global section to an initial condition. 8.2 Flocking One well-known example of consensus on a sheaf comes from ﬂocking models (Jad- babaie et al. 2003; Tanner et al. 2003b). In a typical setting, a group of autonomous agents is tasked with arranging themselves into a stable formation. As a part of this, agents need a way to agree on a global frame of reference. Suppose one has a collection of autonomous agents in R , each of which has its own internal coordinate system with respect to which it measures the outside world. Each agent communicates with its neighbors, communication being encoded as a graph. Assume agents can calculate bearings to their neighbors in their own coordinate frames. The agents wish to agree on a single direction in a global, external frame, perhaps in order to travel in the same direction. However, the transformations between local frames are not known. To solve this, one constructs a sheaf on the neighborhood graph of these agents. The vertices have as stalks R , representing vectors in each agent’s individual coordinate frame. The edges have stalks R , used to compare bearings. Since the agents can measure the bearing to each neighbor, they can project vectors in their coordinate frame onto this bearing. Let b(v, w) be the unit vector in v’s frame pointing toward w. Then for the (oriented) edge e = v ∼ w, the restriction map F : R → R is ve given by b(v, w), •, while the restriction map F is −b(w, v), •. (The change we of sign is necessary because the bearing vectors are opposites in the global frame.) Any globally consistent direction for the swarm will be a section of this sheaf, and with a bit more information the agents can achieve consensus on a direction. This is merely one simple example of a sheaf for building consensus via Laplacian ﬂow. The literature on ﬂocking has various scenarios, including, e.g., the case in which the network communication graph changes over time (Tanner et al. 2003a). 8.3 Opinion dynamics Sheaf Laplacians provide a drop-in replacement for graph Laplacians when one wishes to constrain a distributed algorithm to a locally deﬁnable subspace of the global state 123 Toward a spectral theory of cellular sheaves 349 space. For example, the ﬂocking application in the previous example generalizes greatly to the setting of opinion dynamics on social networks. Consider the setting of a collection of agents, each of whom has an R-valued opinion on some matter (say, a measure of agreement or disagreement with a particular proposition). A social network among agents, modeled as a weighted graph, permits inﬂuence of opinions based on Laplacian dynamics: each member of the network continuously adjusts their opinion to be more similar to the average of their neighbors’ opinions, either in continuous or discrete time. The literature on opinion dynamics begins with this simple setting (DeGroot 1974; Lehrer 1975), and quickly grows to include a number of generalizations of graph Laplacians when there are multiple opinions or other features (Ye et al. 2018; Patterson and Bamieh 2010; Pirani and Sundaram 2014). Our perspective is that lifting the simple model to a sheaf automatically incorporates various novel features while maintaining the simplicity of a Laplacian ﬂow. The ﬁrst obvious generalization is that multiple opinions reside in higher- dimensional stalks. Each agent p has a vector space F (p) of opinions on some set of topics. These vector spaces need not have the same dimension across the network— there is no need to assume that every member of the network has an opinion on every topic. Between each pair (p, q) of participants adjacent in the social network, there is an edge e with a stalk F (e), which we might label a discourse space. Opinions in F (p) and F (q) are translated into the discourse space by the restriction maps F pe and F . qe The ﬂexibility of a sheaf permits a wonderful array of novel features. For instance, each pair of participants in the social network might only communicate about a handful of topics, and hence only inﬂuence each others’ opinions along certain directions. Other topics would therefore lie in the kernels of the restriction map to their shared discourse space. Some features which appear difﬁcult to model in the classical literature on opinion dynamics are easily programmed into a sheaf: what happens if certain agents lie about their opinion, and then only to certain individuals on certain topics? Is a “public” consensus (with privately-held or context-dependent personal opinions) still possible? This demonstrates the utility of sheaves not merely in having stalks which vary, but with varying and interesting restriction maps as well. 8.4 Distributed optimization Laplacian dynamics are useful not only for mere consensus, but also as a way to implement consistency constraints for other sorts of distributed algorithms. Particu- larly important among these are distributed optimization algorithms, where a network optimizes a sum of objective functions distributed across the nodes, with the Laplacian dynamics enforcing the constraint that local state be consistent across nodes. Fix a sheaf of ﬁnite-dimensional vector spaces over a graph G. For each node, v ∈ V (G), assume a cost function, say, a convex functional φ from the stalk of v to R. The problem of ﬁnding a global section x = (x ) which minimizes φ (x ) subject v v v to the constraint that x ∈ H (G; F ) is a relatively unexplored class of optimization 123 350 J. Hansen , R. Ghrist problems. Such problems are naturally distributed in nature, as the constraint (given in terms of the coboundary operator) is locally deﬁned. More generally, one can consider distributed optimization with homological con- straints on any cellular sheaf of vector spaces over a cell complex X. If the problem to be solved is the optimization of an objective function deﬁned on C (X ; F ) subject to the constraint that the optimum lie in H (X ; F ), then this is naturally distributed. One might call such problems homological programs, analogous to the manner in which linear constraints give rise to linear programs. The Laplacian evolution then plays a role in providing distributed algorithms to solve such optimization problems. 8.5 Communication compression Both discrete-time as well as continuous-time Laplacian evolution is useful. Consider the following modiﬁcation of the consensus problems previously discussed. Suppose one has a distributed system modeled by a graph G, where each node of G has state in R for some large D and the nodes are required to reach consensus. The Laplacian ﬂow on states may be discretized as x [t + 1]= (I − αL)x [t ]. (8.1) To implement this discrete-time evolution equation, at each time step, a node v must send its state x [t]∈ R to each of its neighbors, the cost of doing so scaling with state size D. It may be preferable instead to have each node send a lower-dimensional compression of its state to each neighbor, i.e., a projection of x [t ] onto a d D- dimensional subspace, with the subspace depending on the edge e. As with the continuous-time evolution, equilibria of (8.1) correspond to global sections of the sheaf. However, changing the stalks over edges and the correspond- ing restriction maps changes the sheaf and therefore, potentially, its global sections. The goal for reducing the communication complexity is therefore to program this compressed sheaf so as to preserve the zeroth cohomology H . Such a sheaf would comprise a certain approximation of the constant sheaf over the graph. 8.6 Sheaf approximation A sheaf of vector spaces can be thought of as a distributed system of linear trans- formations, and its cohomology H consists of equivalence classes of solutions to systems based on these constraints. From this perspective, questions of approximation — of sheaves and sheaf cohomology—take on especial relevance. The question of approximating global sections to a given sheaf has appeared in, e.g., Robinson (2017, 2018). Questions of approximating sheaves are equally interesting. Given the relative lack of investigation, the following deﬁnition is perhaps premature; nevertheless, it is well- motivated by problems of distributed consensus and by cognate notions of cellular approximation in algebraic topology. 123 Toward a spectral theory of cellular sheaves 351 Deﬁnition 8.2 Let X be a regular cell complex, and let G be a sheaf on X. We say that a sheaf F on X is a k-approximation to G if there exists a sheaf morphism a : G → F which is an isomorphism on stalks over cells of degree at most k, and which induces i i an isomorphism H (X ; G) → H (X ; F ) for all i ≤ k. If V is a vector space, we denote the constant sheaf with stalk V by V, and say that F is an approximation to the constant sheaf if F is an approximation to V. This deﬁnition is reminiscent of cellular approximation methods from algebraic topology. A space X may be k-approximated by a cell complex Y , via a morphism Y → X inducing an isomorphism on homotopy groups up to degree k.Herewe approximate a sheaf on a cell complex by one with the same cohomology in degrees up to k. In particular, a 0-approximation to F has the same vertex stalks and the same space of global sections as F. Proposition 8.3 If F is a 0-approximation to V, then it is isomorphic to a sheaf with vertex stalks V where for each edge e joining vertices v and w, the restriction maps F : V → F (e) and F : V → F (e) are equal. ve we Proof Note that because a : V → F is an isomorphism on vertex stalks, F is clearly isomorphic to a sheaf with vertex stalks V. For every edge e = (v, w) we have the diagram id VV id ve V F (e) id F we id VV and the only way it can commute is if F = F = a . ve we e The proof of this proposition shows that specifying an approximation to V is the same as specifying a morphism a : V → F (e) for each edge e of G. Further, in order to produce an approximation to V,the a must assemble to a map a : C (G; V) → C (G; F ) = F (e) such that ker(a ◦ δ ) = ker δ . This holds if ker a is V V e∈E contained in a complement to im δ; equivalently, the projection map π : C (G; V) → H (G; V) must be an isomorphism when restricted to ker a. This suggests a way to construct an approximation to the constant sheaf. Choose a subspace K of V(e) for each edge e of G and deﬁne a to be the projection map e e 1 1 V → V/K .If K has the same dimension in H (G; V) as in C (G; V), then e e e∈E a = a deﬁnes the edge maps giving an approximation to V. (The vertex maps e∈E may be taken to be the identity.) The question of when a collection {K } produces an approximation to the constant sheaf appears quite subtle, and will be the subject of future work. This description of approximations to the constant sheaf has ignored the question of weights—that is, what inner products to put on the quotient spaces V/K —which will be crucial to the spectral behavior of their Laplacians and hence to the performance of distributed consensus algorithms based thereon. 123 352 J. Hansen , R. Ghrist To understand this relationship, consider again the discretization of the Laplacian ﬂow x [t + 1]= (I − αL )x [t ]. The matrix (I − αL ) has an eigenvalue of 1 with F F eigenspace equal to H (G; F ), with all other eigenvalues less than 1. The optimal convergence rate for this consensus algorithm is obtained at an α keeping the nontrivial eigenvalues as close to zero as possible. If λ is the largest eigenvalue of L and max F λ the smallest nontrivial eigenvalue of L , this is obtained at α = ,for a min F λ +λ max min λ −λ max min nontrivial spectral radius of r = . λ +λ max min The number of steps necessary to reach a level of disagreement of is thus pro- log portional to .Ona k-regular graph with d-dimensional edge stalks, the total log(r ) amount of communication each node must undertake at each step is proportional to log kd. Thus the total communication cost per node is proportional to kd .For the log(r ) log λ (G)−λ (G) max min constant sheaf R , the total cost per node is kD , where R = is log(R) λ (G)−λ (G) max min the corresponding spectral radius for consensus over L D.If d log(R) < 1, D log(r ) the total communication cost for consensus using the approximation to the constant sheaf will be lower than that for the constant sheaf. Preliminary investigation suggests it may be possible to construct approximations to the constant sheaf that achieve this threshold, but more work is necessary to develop methods for creating spectrally advantageous approximations to the constant sheaf. These could then be marshaled to improve the speed and efﬁciency of distributed algorithms that involve consensus, such as distributed optimization. 8.7 Synchronization The concept of synchronization in the context of problems with data on graphs is exempliﬁed in work by Singer on the angular alignment problem (Singer 2011). The concept was developed further by Bandeira in his dissertation (Bandeira 2015). The general idea is to recover information about some set of parameters from knowledge of their pairwise relationships. The general formulation, due to Bandeira, is as follows: Given a group G, a graph X, and a function f : G → R for each edge i ∼ j of X, ij −1 ﬁnd a function g : V (X ) → G minimizing f (g(i )g( j ) ). ij i ∼ j Often, the functions f are chosen such that they have a unique minimum at a given ij element g ∈ G. One may view this as originating from a G-principal bundle on a ij graph, with the group elements g deﬁning transition maps. The desired solution is a ij section of the bundle, determined up to a self-action of G, but may not exist if there is error in the measured g . As a result, we seek an error-minimizing solution, where ij the error is measured by the functions f . ij Sheaves on graphs offer a broader formulation: synchronization is the problem of ﬁnding a global section, or approximate global section, of an observed sheaf on a graph. By choosing sheaves valued in a suitable category, we can recover the group- theoretic formulation. There is something of a gap between the natural formulation 123 Toward a spectral theory of cellular sheaves 353 of many synchronization problems and a sheaf valued in vector spaces; bridging that gap for synchronization over O(d) is the goal of Bandeira et al. (2013). One of the initial motivating problems for the study of synchronization was the cryo-electron microscopy alignment problem. The goal is to understand the con- ﬁguration of a molecule, represented by a density function on R . Cryo-electron microscopy allows one to measure projections of random rotations of this function onto a ﬁxed two-dimensional plane. One approach to recovery involves inferring these unknown rotations from pairwise information. After taking the Fourier transform of the measured two-dimensional distributions, each pair of distributions will agree on a one-dimensional subspace, speciﬁcally, the invariant axis for the rotation relating the two orientations of the molecule. Suppose the ith measurement is taken from the molecule in an orientation ρ ∈ SO(3), so that the transformation between the orientation of measurement i and mea- −1 surement j is ρ = ρ ρ .If x is a vector in the base orientation frame of the ij j molecule, its representation in the frames for i and j are ρ x and ρ x, respectively. i j These two vectors have the same projection onto the invariant subspace of ρ . Since ij this invariant subspace is precisely the subspace on which the relevant two projections agree, we can check whether two vectors in the frames for measurements i and j agree by projecting them onto this subspace. A single constraint of this form does not ensure equality of vectors in the different frames. However, sufﬁciently many generic such constraints will. Combining all these pairwise constraints gives us a sheaf with the same form as the sheaf of autonomous agents discussed in Sect. 8.2. Note that the pairwise data here obtained is not in the form of invertible transformations, but weaker constraints. Thus, a major motivat- ing problem for synchronization has a natural expression in the language of cellular sheaves. The explicitly sheaf-theoretic formulation of the synchronization problem suggests a different solution approach. If a synchronization sheaf has a global section—as is the case when the data are internally consistent and uncorrupted by noise—ﬁnding that section is trivial. The traditional approach to synchronization takes these transition functions as they are, and seeks an approximate section to the sheaf. On the other hand, we might try to denoise the measured relationships themselves using the condition of cycle-consistency. That is, given an observed sheaf, ﬁnd the nearest sheaf supporting a global section. A structural Cheeger inequality as discussed in Sect. 7.2 would give spectral insights into this problem. Deeper understanding would come from study of an appropriate moduli space of cellular sheaves, which is a direction for future work. 8.8 Consistent clustering As suggested by Gao et al. (2016), the data of a sheaf on a graph is useful for more than recovering a global section. The problem of clustering objects where the similarity measure comes from an explicit matching or transformation gives extra information. If we stipulate that objects within a cluster should have consistent transformations along cycles, the problem of clustering becomes the problem of partitioning a graph into subgraphs, each of which supports the appropriate space of global sections. 123 354 J. Hansen , R. Ghrist Similar ideas arise in Gao (2016), which considers correspondences between surfaces produced using the soft Procrustes distance. These correspondences are maps between probability distributions on the vertex sets of discretized surfaces. When these surfaces are meshes with varying numbers of vertices, these maps are not invertible, but by construction they are represented by doubly stochas- tic matrices, and the analogue of the inverse for such a map is simply the transpose of its corresponding matrix. These sorts of geometric correspondences are natural to consider in the context of geometric morphometrics, the ﬁeld devoted to studying and classifying species based on their geometric proper- ties. Gao constructs a matrix he calls the graph horizontal Laplacian, together with normalized versions he uses to formulate a ﬁber bundle version of the diffusion maps algorithm for dimensionality reduction. The graph horizontal Laplacian is related to a map of graphs X → G, where the ﬁbers over vertices of G are discrete. A weighting on the edges of X induces a matrix-valued weighting on the edges of G. This produces a weighted adjacency matrix W of G, from which the graph horizontal Laplacian is H H generated by L = D − W , where D is the diagonal matrix necessary to make L have row sums equal to zero. This is in fact equivalent to the sheaf Laplacian of the pushforward of the weighted constant sheaf on X, and as a consequence of Proposition 5.10, is simply a block subdivision of the Laplacian of X. This sheaf on G can then be normalized to construct a diffusion map embedding of the vertices of G, as well as an embedding of the vertices of X. When applied to the surface correspondence problem, the eigenvectors of the resulting sheaf Laplacian serve to partition the surfaces into automatically determined landmarks or regions of interest. Approaching these notions of partitioning, partial sections, and noninvertible matchings from a sheaf-theoretic perspective offers new tools and clariﬁes the prob- lems in question, with potential for the spectral approach to yield insights. 9 Closing questions There are numerous interesting open questions in an emerging spectral sheaf theory. We highlight a few below, with comments. 9.1 Metrics on the space of cellular sheaves Interleaving-type constructions have been used to deﬁne metrics on the space of con- structible sheaves (Curry 2014, Chapter 15). However, these rely on explicit geometric information about the sheaves and their underlying spaces. Working with weighted cellular sheaves may make it possible to deﬁne useful distances that rely only on the combinatorial and algebraic structure of the sheaves. What are the most useful metrics on the space of sheaves? How do they interact with the sheaf Laplacians and their spectra? How does this shed light on a moduli space of cellular sheaves? 123 Toward a spectral theory of cellular sheaves 355 9.2 Developing a Cheeger inequality Following the discussion in Sect. 7.2, a structural Cheeger inequality for sheaves is connected to questions of a potential moduli space of sheaves. Such an inequality would describe how the spectral properties of a sheaf interact with its distance to the nearest sheaf with a nontrivial global section. Can a Cheeger inequality emerge from approximations to the constant sheaf, seeking 0-cochains of small coboundary which are constant on large sets of vertices? 9.3 Interactions with the derived category The standard way of understanding sheaf cohomology is through the derived category of complexes of sheaves (Gelfand and Manin 2003). We may replace a sheaf by an injective resolution and take the cohomology of the complex of sheaves. What is the relationship between a weighted sheaf and its injective resolutions, and how do the resulting Laplacians connect with the Hodge Laplacian deﬁned on the cochain com- plex? What results can be proven about their spectra? How do they interact with the standard sheaf operations? Is there a consistent way to add weights to the derived cate- gory of sheaves? We should not expect the answers to these questions to be unique due to the dagger categorical issues discussed in Sect. 3.1, but there may be constructions which are nevertheless appealing. 9.4 Random walks Chung and Zhao (2012) considered random walks on discrete O(n)-bundles, including a deﬁnition of a sort of PageRank algorithm. Is it possible to deﬁne random walks on more general sheaves of vector spaces, and to what extent are such related to the sheaf Laplacian and its spectral features? Is there an analogous PageRank algorithm for sheaves? 9.5 Cones and directedness How does one model directedness and asymmetric relations on sheaves? Sheaves of cones and sheaf cohomology taking values in categories of cones have proven useful in recent applications of sheaf theory to problems incorporating directedness (Ghrist and Krishnan 2017; Kashiwara and Schapira 2018). Such methods, though promising, may be noncommutative, using semigroups or semimodules to encode the directed- ness, which, in turn, pushes the boundaries of existing methods in sheaf theory and nonabelian sheaf cohomology. Funding This funding was supported by Ofﬁce of Naval Research (Grant Nos. FA8650-18-2-7840, N00014- 16-1-2010) Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 Interna- tional License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, 123 356 J. Hansen , R. Ghrist and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. References Abraham, R., Marsden, J.E., Ratiu, T.: Manifolds, Tensor Analysis, and Applications. Springer, New York (1988) Bandeira, A.: Convex relaxations for certain inverse problems on graphs. PhD thesis, Princeton University, (2015) Bandeira, A.S., Singer, A., Spielman, D.A.: A Cheeger inequality for the graph connection Laplacian. SIAM J. Matrix Anal. Appl. 34(4), 1611–1630 (2013) Belkin, M., Niyogi, P.: Laplacian Eigenmaps for dimensionality reduction and data representation. Neural Comput. 15, 1373–1396 (2003) Björner, A.: Posets, regular CW complexes and Bruhat order. Eur. J. Comb. 5(1), 7–16 (1984) Boman, E.G., Chen, D., Parekh, O., Toledo, S.: On factor width and symmetric H-matrices. Linear Algebra Appl. 405(1), 239–248 (2005) Bredon, G.E.: Sheaf Theory: Number 170 in Graduate Texts in Mathematics, 2nd edn. Springer, Berlin (1997) Brouwer, A.E., Haemers., W.H.: Spectra of Graphs. Universitext. Springer, Berlin (2012) Brüning, J., Lesch, M.: Hilbert complexes. J. Funct. Anal. 108(1), 88–132 (1992) Bullo, F.: Lectures on network systems. CreateSpace, (2018) Carlsson, G.: The shape of data, (2012) Catanzaro, M.J., Chernyak, V.Y., Klein, J.R.: On Kirchhoff’s theorems with coefﬁcients in a line bundle. Homol. Homotopy Appl. 15(2), 267–280 (2013) Chung, F.: Spectral Graph Theory. AMS, (1992) Chung, F., Zhao, W.: Ranking and sparsifying a connection graph. In: International Workshop on Algorithms and Models for the Web-Graph, Lecture Notes in Computer Science. Springer, (2012) Coifman, R.R., Lafon, S.: Diffusion maps. Appl. Comput. Harmon. Anal. 21(1), 5–30 (2006) Curry, J.: Sheaves, cosheaves, and applications. PhD thesis, University of Pennsylvania, (2014) Curry, J., Ghrist, R., Robinson, M.: Euler calculus with applications to signals and sensing. In: Proceedings of the Symposium in Applied Mathematics. AMS, (2012) Cvetcovic, ´ D., Simic, ´ S.: Graph spectra in computer science. Linear Algebra Appl. 434(6), 1545–1562 (2011) Davis, J., Kirk, P.: Lecture Notes in Algebraic Topology, volume 35 of Graduate Studies in Mathematics. American Mathematical Society, Providence, Rhode Island (2001) De Carli Silva, M.K., Harvey, N.J.A., Sato, C.M.: Sparse sums of positive semideﬁnite matrices. ACM Trans. Algorithms 12(1), 9:1–9:17 (2016) DeGroot, M.H.: Reaching a consensus. J. Am. Stat. Assoc. 69, 118–121 (1974) Dörﬂer, F., Bullo, F.: Kron reduction of graphs with applications to electrical networks. IEEE Trans. Circ. Syst. I: Regul P. 60(1), 150 (2013) Eckmann, B.: Harmonische funktionen und randwertaufgaben in einem komplex. Comment. Math. Helv. 17(1), 240–255 (1945) Edelsbrunner, H., Harer, J.: Computational Toplogy: An Introduction. American Mathematical Society, Providence (2010) Friedman, J.: Sheaves on graphs, their homological invariants, and a proof of the Hanna Neumann conjecture. Memoirs of the American Mathematical Society 233(1100), (2015) Friedman, J.: Computing Betti numbers via combinatorial Laplacians. Algorithmica 21(4), 331–346 (1998) Gao, T.: The Diffusion Geometry of Fibre Bundles. arXiv:1602.02330, (2016) Gao, T., Brodzki, J., Mukherjee, S.: The Geometry of Synchronization Problems and Learning Group Actions. arXiv:1610.09051, (2016) Gelfand, S.I., Manin, Y.I.: Methods of Homological Algebra, Springer Monographs in Mathematics, 2nd edn. Springer, Berlin (2003) Ghrist, R.: Elementary Applied Topology. CreateSpace, https://www.math.upenn.edu/ghrist/notes.html, (2014) 123 Toward a spectral theory of cellular sheaves 357 Ghrist, R., Krishnan, S.: Positive Alexander duality for pursuit and evasion. SIAM J. Appl. Algebra Geom. 1(1), 308–327 (2017) Gromov, M.: Singularities, expanders and topology of maps. Part 2: from combinatorics to topology via algebraic isoperimetry. Geom. Funct. Anal. 20, 416–526 (2010) Hadani, R., Singer, A.: Representation theoretic patterns in three-dimensional cryo-electron microscopy II—the class averaging problem. Found. Comput. Math. 11(5), 589–616 (2011) Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge (2001) Heunen, C., Karvonen, M.: Limits in dagger categories. Theory Appl. Categ. 34(18), 468–513 (2019) Hoory, S., Linial, N., Widgerson, A.: Expander graphs and their applications. Bull. Am. Math. Soc. 43(4), 439–561 (2006) Horak, D., Jost, J.: Spectra of combinatorial Laplace operators on simplicial complexes. Adv. Math. 244, 303–336 (2013) Jadbabaie, A., Lin, J., Morse, A.S.: Coordination of groups of mobile autonomous agents using nearest neighbor. IEEE Trans. Autom. Control 50(3), 2953–2958 (2003) Johnson, C.R., Smith, R.L.: Closure Properties. In The Schur Complement and Its Applications, number 4 in Numerical Methods and Algorithms, pp. 111–136. Springer, (2005) Kaczynski, T., Mischaikow, K., Mrozek, M.: Computational Homology, Applied Mathematical Sciences. Springer, New York (2004) Kashiwara, M., Schapira, P.: Sheaves on Manifolds. (1990) Kashiwara, M., Schapira, P.: Persistent homology and microlocal sheaf theory. arXiv:1705.00955, (2018) Kenyon, R.: Spanning forests and the vector bundle Laplacian. Ann. Prob. 39(5), 1983–2017 (2011) Lehrer, K.: Social consensus and rational agnoiology. Synthese 31, 141–160 (1975) Linial, N., Meshulam, R.: Homological connectivity of random 2-complexes. Combinatorica 26(4), 475– 487 (2006) Lyons, R., Peres, Y.: Probability on Trees and Networks. Number 42 in Cambridge series in statistical and probabilistic mathematics. Cambridge University Press, (2016) MacPherson, R., Patel, A.: Persistent Local Systems. (2018) Mantuano, T.: Discretization of vector bundles and rough Laplacian. Asian J. Math. 11(4), 671–698 (2007) Osting, B., Palande, S., Wang, B.: Towards spectral sparsiﬁcation of simplicial complexes based on gener- alized effective resistance. (2017) Otter, N., Porter, M.A., Tillmann, U., Grindrod, P., Harrington, H.A.: A roadmap for the computation of persistent homology. EPJ Data Sci. 6(1), 17 (2017) Parzanchevski, O.: High dimensional expanders. PhD thesis, Hebrew University of Jerusalem, (2013) Parzanchevski, O., Rosenthal, R., Tessler, R.J.: Isoperimetric inequalities in simplicial complexes. Combi- natorica 36(2), 195–227 (2016) Patterson, S., Bamieh, B.: Interaction-driven opinion dynamics in online social networks. In: Proceedings of the First Workshop on Social Media Analytics, SOMA ’10, pp. 98–105. ACM, (2010) Pirani, M., Sundaram, S.: Spectral properties of the grounded Laplacian matrix with applications to con- sensus in the presence of stubborn agents. In: Proceedings of the American Control Conference, pp. 2160–2165, (2014) Robinson, M.: Sheaves are the canonical data structure for sensor integration. Inf Fusion 36, 208–224 (2017) Robinson, M.: Assignments to sheaves of pseudometric spaces. arXiv:1805.08927, (2018) Schaub, M.T., Benson, A.R., Horn, P., Lippner, G., Jadbabaie, A.: Random Walks on Simplicial Complexes and the normalized Hodge Laplacian. arXiv:1807.05044 , (2018) Singer, A.: Angular synchronization by eigenvectors and semideﬁnite programming. Appl. Comput. Har- mon. Anal. 30, 20–36 (2011) Singer, A., Wu, H.-T.: Vector diffusion maps and the connection Laplacian. Commun. Pure Appl. Math. 65(8), 1067–1144 (2012) Spielman, D.A.: Linear-time encodable and decodable error-correcting codes. IEEE Trans. Inf. Theory 42(6), 1723–1731 (1996) Spielman, D.: Course Notes: Spectral Graph Theory. http://www.cs.yale.edu/homes/spielman/561/, (2015) Spielman, D.A., Srivastava, N.: Graph Sparsiﬁcation by Effective Resistances. arXiv:0803.0929 , (2008) Spielman, D., Teng, S.-H.: Spectral sparsiﬁcation of graphs. SIAM J. Comput. 40(4), 981–1025 (2011) Spielman, D.A., Teng, S.-H.: Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. SIAM J. Matrix Anal. Appl. 35(3), 835–885 (2014) Steenbergen, J.: Towards a spectral theory for simplicial complexes. PhD thesis, Duke University, (2013) Sunada, T.: Discrete geometric analysis. In: Proceedings of Symposia in Pure Mathematics, (2008) 123 358 J. Hansen , R. Ghrist Tanner, H.G., Jadbabaie, A., Pappas, G.J.: Stable ﬂocking of mobile agents, part I: dynamic topology. In: 42nd IEEE International Conference on Decision and Control (IEEE Cat. No.03CH37475), vol. 2, pp. 2016–2021, (2003a) Tanner, H.G., Jadbabaie, A., Pappas, G.J.: Stable ﬂocking of mobile agents, part I: ﬁxed topology. In: 42nd IEEE International Conference on Decision and Control (IEEE Cat. No.03CH37475), vol. 2, pp. 2010–2015, (2003b) Tropp, J.A.: User-friendly tail bounds for sums of random matrices. Found. Comput. Math. 12, 389–434 (2012) Wu, C., Ren, S., Wu, J., Xia, K.: Weighted (Co)homology and Weighted Laplacian. arXiv:1804.06990, (2018) Ye, M., Trinh, M.H., Lim, Y-H., Anderson, B.D.O., Ahn, H-S.: Continuous-time Opinion Dynamics on Multiple Interdependent Topics. CoRR, arXiv:1805.02836, (2018) Zein, F.E., Snoussi, J.: Local Systems and constructible sheaves. In: Bass, H., Oesterlé, J., Weinstein, A., Zein, F.E., Suciu, A.I., Tosun, M., Muhammed Uludag, ˘ A., Yuzvinsky, S. (eds.) Arrangements, Local Systems and Singularities, vol. 283, pp. 111–153. Birkhäuser Basel, Basel (2009) Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional afﬁliations.

Journal

Journal of Applied and Computational Topology – Springer Journals

Published: Aug 30, 2019

References

Manifolds, Tensor Analysis, and Applications

Abraham, R; Marsden, JE; Ratiu, T
A Cheeger inequality for the graph connection Laplacian

Bandeira, AS; Singer, A; Spielman, DA
Laplacian Eigenmaps for dimensionality reduction and data representation

Belkin, M; Niyogi, P
Posets, regular CW complexes and Bruhat order

Björner, A
On factor width and symmetric H-matrices

Boman, EG; Chen, D; Parekh, O; Toledo, S
Sheaf Theory: Number 170 in Graduate Texts in Mathematics

Bredon, GE
Spectra of Graphs. Universitext

Brouwer, AE; Haemers., WH
Hilbert complexes

Brüning, J; Lesch, M
On Kirchhoff’s theorems with coefficients in a line bundle

Catanzaro, MJ; Chernyak, VY; Klein, JR
Diffusion maps

Coifman, RR; Lafon, S
Graph spectra in computer science

Cvetcović, D; Simić, S
Sparse sums of positive semidefinite matrices

De Carli Silva, MK; Harvey, NJA; Sato, CM
Reaching a consensus

DeGroot, MH
Kron reduction of graphs with applications to electrical networks

Dörfler, F; Bullo, F
Harmonische funktionen und randwertaufgaben in einem komplex

Eckmann, B
Computational Toplogy: An Introduction

Edelsbrunner, H; Harer, J
Sheaves on Graphs, Their Homological Invariants, and a Proof of the Hanna Neumann Conjecture: with an Appendix by Warren Dicks

Friedman, Joel
Computing Betti numbers via combinatorial Laplacians

Friedman, J
Methods of Homological Algebra, Springer Monographs in Mathematics

Gelfand, SI; Manin, YI
Positive Alexander duality for pursuit and evasion

Ghrist, R; Krishnan, S
Singularities, expanders and topology of maps. Part 2: from combinatorics to topology via algebraic isoperimetry

Gromov, M
Representation theoretic patterns in three-dimensional cryo-electron microscopy II—the class averaging problem

Hadani, R; Singer, A
Algebraic Topology

Hatcher, A
Limits in dagger categories

Heunen, C; Karvonen, M
Expander graphs and their applications

Hoory, S; Linial, N; Widgerson, A
Spectra of combinatorial Laplace operators on simplicial complexes

Horak, D; Jost, J
Coordination of groups of mobile autonomous agents using nearest neighbor

Jadbabaie, A; Lin, J; Morse, AS
Computational Homology, Applied Mathematical Sciences

Kaczynski, T; Mischaikow, K; Mrozek, M
Persistent homology and microlocal sheaf theory

Kashiwara, Masaki; Schapira, Pierre
Spanning forests and the vector bundle Laplacian

Kenyon, R
Social consensus and rational agnoiology

Lehrer, K
Homological connectivity of random 2-complexes

Linial, N; Meshulam, R
Discretization of vector bundles and rough Laplacian

Mantuano, T
A roadmap for the computation of persistent homology

Otter, N; Porter, MA; Tillmann, U; Grindrod, P; Harrington, HA
Isoperimetric inequalities in simplicial complexes

Parzanchevski, O; Rosenthal, R; Tessler, RJ
Sheaves are the canonical data structure for sensor integration

Robinson, M
Angular synchronization by eigenvectors and semidefinite programming

Singer, A
Vector diffusion maps and the connection Laplacian

Singer, A; Wu, H-T
Linear-time encodable and decodable error-correcting codes

Spielman, DA
Spectral sparsification of graphs

Spielman, D; Teng, S-H
Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems

Spielman, DA; Teng, S-H
User-friendly tail bounds for sums of random matrices

Tropp, JA
Arrangements, Local Systems and Singularities

Zein, FE; Snoussi, J

Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Toward a spectral theory of cellular sheaves

Toward a spectral theory of cellular sheaves

Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Toward a spectral theory of cellular sheaves

Toward a spectral theory of cellular sheaves

Abstract

Journal

Recommended Articles

References

Our policy towards the use of cookies