Matroids And Canonical Forms: Theory and Applications

This document introduces a combinatorial theory of homology, a topological descriptor of shape. The past fifteen years have seen a steady advance in the use of techniques and principles from algebraic topology to address problems in the data sciences. This new subfield of Topological Data Analysis [TDA] seeks to extract robust qualitative features from large, noisy data sets. A primary tool in this new approach is the homological persistence module, which leverages the categorical structure of homological data to generate and relate shape descriptors across scales of measurement. We define a combinatorial analog to this structure in terms of matroid canonical forms. Our principle application is a novel algorithm to compute persistent homology, which improves time and memory performance by up to several orders of magnitude over current state of the art. Additional applications include new theorems in discrete, spectral, and algebraic Morse theory, which treats the geometry and topology of abstract space through the analysis of critical points, and a novel paradigm for matroid representation, via abelian categories. Our principle tool is elementary exchange, a combinatorial notion that relates linear and categorical duality with matroid complementarity