Towards a Spectral Theory for Simplicial Complexes

Abstract

<p>In this dissertation we study combinatorial Hodge Laplacians on simplicial com-</p><p>plexes using tools generalized from spectral graph theory. Specifically, we consider</p><p>generalizations of graph Cheeger numbers and graph random walks. The results in</p><p>this dissertation can be thought of as the beginnings of a new spectral theory for</p><p>simplicial complexes and a new theory of high-dimensional expansion.</p><p>We first consider new high-dimensional isoperimetric constants. A new Cheeger-</p><p>type inequality is proved, under certain conditions, between an isoperimetric constant</p><p>and the smallest eigenvalue of the Laplacian in codimension 0. The proof is similar</p><p>to the proof of the Cheeger inequality for graphs. Furthermore, a negative result is</p><p>proved, using the new Cheeger-type inequality and special examples, showing that</p><p>certain Cheeger-type inequalities cannot hold in codimension 1.</p><p>Second, we consider new random walks with killing on the set of oriented sim-</p><p>plexes of a certain dimension. We show that there is a systematic way of relating</p><p>these walks to combinatorial Laplacians such that a certain notion of mixing time</p><p>is bounded by a spectral gap and such that distributions that are stationary in a</p><p>certain sense relate to the harmonics of the Laplacian. In addition, we consider the</p><p>possibility of using these new random walks for semi-supervised learning. An algo-</p><p>rithm is devised which generalizes a classic label-propagation algorithm on graphs to</p><p>simplicial complexes. This new algorithm applies to a new semi-supervised learning</p><p>problem, one in which the underlying structure to be learned is flow-like.</p>