A TOPOLOGICAL STUDY OF TOROIDAL DYNAMICS By Hitesh Gakhar A DISSERTATION Michigan State University in partial fulfillment of the requirements Submitted to for the degree of Mathematics – Doctor of Philosophy 2020 ABSTRACT A TOPOLOGICAL STUDY OF TOROIDAL DYNAMICS By Hitesh Gakhar This dissertation focuses on developing theoretical tools in the field of Topological Data Analysis and more specifically, in the study of toroidal dynamical systems. We make con- tributions to the development of persistent homology by proving Künneth-type theorems, to topological time series analysis by further developing the theory of sliding window em- beddings, and to multiscale data coordinatization in topological spaces by proving stability theorems. First, in classical algebraic topology, the Künneth theorem relates the homology of two topological spaces with that of their product. We prove Künneth theorems for the persistent homology of the categorical and tensor product of filtered spaces. That is, we describe the persistent homology of these product filtrations in terms of that of the filtered components. Using these theorems, we also develop novel methods for algorithmic and abstract compu- tations of persistent homology. One of the direct applications of these results is the abstract computation of Rips persistent homology of the N-dimensional torus. Next, we develop the general theory of sliding window embeddings of quasiperiodic functions and their persistent homology. We show that the sliding window embeddings of quasiperiodic functions, under appropriate choices of the embedding dimension and time delay, are dense in higher dimensional tori. We also explicitly provide methods to choose these parameters. Furthermore, we prove lower bounds on Rips persistent homology of these embeddings. Using one of the persistent Künneth formulae, we provide an alternate algo- rithm to compute the Rips persistent homology of the sliding window embedding, which outperforms the traditional methods of landmark sampling in both accuracy and time. We also apply our theory to music, where using sliding windows and persistent homology, we characterize dissonant sounds as quasiperiodic in nature. Finally, we prove stability results for sparse multiscale circular coordinates. These coor- dinates on a data set were first created to aid non-linear dimensionality reduction analysis. The algorithm identifies a significant integer persistent cohomology class in the Rips filtra- tion on a landmark set and solves a linear least squares optimization problem to construct a circled valued function on the data set. However, these coordinates depend on the choice of the landmarks. We show that these coordinates are stable under Wasserstein noise on the landmark set. To my family & friends iv ACKNOWLEDGEMENTS The last few years of my mathematical career, as cliché as it may sound, have been full of ups and downs. I would not have been able to make it to the finish line if not for the wonderful people I have met. First and foremost, I am thankful for my advisor Dr. Jose Perea. Moving from pursuing pure topology to applied topology was one of the hardest decisions I had to make, and if it was not for his guidance, expertise, and well chosen problems, this transition would have been a much harder one. His wisdom and work ethic continues to inspire me. I would also like to express the deepest of gratitude towards the members of my dissertation committee: Dr. Matthew Hedden, Dr. Elizabeth Munch, and Dr. Guowei Wei for their guidance through different stages of my Ph.D. career. There are two people who facilitated two major plot twists in my life. First, it was Bhavya Aggarwal who unintentionally made me question my career choices towards the end of high school which led me to switching from engineering to mathematics. Second, it was Harrison LeFrois who gave me an initial nudge towards considering applied topology as a field of research for my dissertation. My education in mathematics and science started at the Indian Institute of Science I am thankful for some of the faculty members who Education and Research, Mohali. contributed immensely to building my scientific temper, mathematical rigor, and academic integrity: Dr. Lingaraj Sahu, Dr. Kapil Paranjape, Dr. Amit Kulshrestha, Dr. Krishnendu Gongopadhyay, Dr. Lolitika Mandal, and Dr. N.G. Prasad. After moving to Michigan State University, I took many advanced courses in mathematics to expand my knowledge base. Thank you to all the faculty members who taught me in the last few years, with a special mention to Dr. Teena Gerhardt for teaching the qualifying course in introductory algebraic topology. I have been very fortunate to have access to the teaching resources and opportunities at v Michigan State. The encouragement to explore different styles of teaching that I received from the Central for Instructional Mentoring, in particular, Dr. Tsveta Sendova and Andy Krause, allowed me to grow as an educator. I am also grateful for Tsveta’s open door policy, which I utilized at every opportunity, be it a crisis or a moment of celebration. Without her presence in Wells Hall, this journey would have been arduous. I am glad to have worked on teaching assignments with the following people: Dr. Peter Magyar, Jane Zimmerman, Andrew Krause, Sue Allen, Dr. Russell Schwab, and Dr. Shiv Karunakaran. I am thankful for every feedback, critique, compliment, and opportunity that has been given to me. I would also like to thank the administrative staff in the mathematics department for all their work, especially Estrella Starn for her emails to the graduate students during the COVID-19 crisis, and Ami McMurphy and Nicole Holton for always stopping me in my tracks and genuinely asking me how I was doing. On the mathematical side, I would first like to thank my collaborators Dr. Joshua Mike, Luis Polanco, and Joseph Melby. It has been a pleasure working with them on different projects and I am extremely grateful for their assistance with both the theoretical and com- putational aspects of research. I am also thankful to Ákos Nagy for useful academic advice over the years. Having a large Geometry and Topology student group in the department has been very beneficial as it led to many productive discussions, seminar talks, and fun graduate conferences with Sanjay Kumar, Abhishek Mallick, Wenzhao Chen, Gorapada Bera, Brandon Bavier, Keshav Sutrave, Danika Van Niel, and Chloe Lewis. I am also happy to have known Michael Schultz, Mollee Shultz, Sami Merhi, Sugil Lee, Nick Ovenhouse, Dimitris Vardakis, Ioannis Zachos, Rami Fakhry, Rodrigo Matos, Leonardo Abbrescia, Jihye Hwang, Valentin Kuechle, Lubhashan Pathirana, Chamila Malagoda, Armstrong Guan, Nick Rekuski, and Arman Tavakoli during my time at Wells Hall. Outside the department, I have had the pleasure of meeting many wonderful people. I am very happy to have known my Spartan Village gang: Akshit Sarpal, Apratim Mukherjee, Sanjana Mukherjee, and Salil Sapre for being a crucial part of my first family in this country. vi While most of them graduated, Salil stayed and indirectly introduced me to more awesome folks: Charuta Parkhi, Amit Sharma, Manasi Mishra, Hetal Adhia, and most importantly Hariharan Iyer, who I have enjoyed watching Gunda with on numerous occasions. I am thankful to Ronak Sripal for introducing me to most of the Desi Boys: Abhiroop Ghosh, Bharath Basti Shenoy, Sai Chaitanya, Ankit Gautam, Abu Bakr, Siddharth Shukla, Karthik Krishnan, Anirudh Bhat, and Yash Roy. My weekly nights with them over the last couple years were a great way to unwind, whether it was playing pool, or getting dinner and drinks, watching a movie, playing board games, or Hookah at unexpected times. I have also cherished my time that I have spent with Hattie Cable, Sophia Zhang, Veditha Shetty, Ajay Dhara, and Anna Skelton. There are a few people who believed in me and cheered me on during my Ph.D.: Priyanka Jamadagni, Kritika Singhal, Sujoy Mukherjee, Rhea Palak Bakshi, Bharat Gehlot, Indrajeet Sagar, Nishika Bhatia, Ben Mackey, Lauren Conway, Stevie Simmons, and Ayesha Yala- marthy. Thank you for all your support! I am also grateful to Christos Grigoriadis for teaching me expletives in Greek, Eylem Yildiz for talking about politics over Indian food, and Allison Glasson for the wackiest of surprises and telling me, “I believe in you”. A set of wonderful friends, who I (secretly) call my Review Crew, read through tons of my abstracts, cover letters, reports, and statements. They helped me turn my drafts into something of value. In particular, I am thankful to: • Sarah Klanderman, for multiple discussions on homotopy colimits, long mid-day coffee walks, and being my most loyal writing partner. • Charlotte Ure, for countless conversations, inspiring me through her badassery, and being the best office mate I could hope for. • Tyler Bongers, for answering my analysis related questions, many adventures at Pinball Pete’s, getting me into craft beers, and sharing the love of terrible puns. vii • Rani Satyam, for Bollywood movie nights, Pokewalks, listening to my pointless venting about everything and everyone, and being my work accountability buddy. I owe my morning schedule to our CVS meetups. • Reshma Menon, for years of soul-saving Indian food, working together in GSC, and exchanging funny and sad stories about dating mishaps. We started our Ph.D. journeys together, got our first jobs on the same day, and shared most of the struggles in between. You were my Ph.D. soulmate. My partner, Livy Drexler is one of the kindest people I know. The last year of my dissertation was probably the hardest and the busiest stretch of time in my entire life. Her companionship has been one of the most important things that has kept me afloat. I am thankful for it along with the joy and optimism that she brings to my life. I am also thankful to her for introducing me to her wonderful parents: John and Amy Drexler, who treat me as a member of their family, and more importantly, send me fine chocolates throughout the year, and to her dog, Pixie, who makes my life less mundane. Finally, and most importantly, I am eternally grateful to my parents, Ashok and Usha, for everything. It is only because of you that I have made it this far in life. Not only did you provide for me the best education possible, you lent me your unwavering support. The amount of flexibility and freedom I had in regards to choosing my career path was significant. Thank you for doing the right thing before 3 Idiots was released. I would also like to thank my brother, Nivesh, for always having my back no matter what. It has meant a lot to me. viii TABLE OF CONTENTS LIST OF TABLES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi LIST OF FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xii CHAPTER 1 1.1.1 Persistent Künneth theorems INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1 Outline & Overview of the dissertation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.1.1 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . Sliding window embeddings of quasiperiodic functions . . . . . . . . . 1.1.2.1 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . Stability of circular coordinates . . . . . . . . . . . . . . . . . . . . . 1.1.3.1 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.2 1.1.3 CHAPTER 2 BACKGROUND . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1 Category Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1 Definitions and Examples . . . . . . . . . . . . . . . . . . . . . . . . 2.1.2 Functors and natural transformations . . . . . . . . . . . . . . . . . . 2.1.3 Coequalizers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Algebraic Topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 The Classical Künneth Theorems . . . . . . . . . . . . . . . . . . . . 2.2.2 Homotopy Colimits . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.3 Principal bundles and Čech cohomology . . . . . . . . . . . . . . . . 2.3 Persistent Homology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Dynamical Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.1 Takens’s embedding theorem . . . . . . . . . . . . . . . . . . . . . . . 2.5 Analytical tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.1 Fourier Series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.2 Kronecker’s theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.3 Wasserstein metric on probability measures . . . . . . . . . . . . . . CHAPTER 3 PERSISTENT KÜNNETH THEOREMS . . . . . . . . . . . . . . . 3.1 Products of Diagrams of Spaces . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 A comparison theorem . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 A Persistent Künneth formula for the categorical product . . . . . . . . . . . 3.3 A Persistent Künneth Formula for the generalized tensor product . . . . . . 3.3.1 The tensor product and Tor of graded modules . . . . . . . . . . . . 3.3.2 The Graded Algebraic Künneth Formula . . . . . . . . . . . . . . . . 3.3.3 A Persistent Eilenberg-Zilber theorem . . . . . . . . . . . . . . . . . . 3.3.4 Barcode Formulae . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Application: Persistent Homology of N-torus . . . . . . . . . . . . . . . . . . CHAPTER 4 QUASIPERIODICITY . . . . . . . . . . . . . . . . . . . . . . . . . ix 1 3 3 6 7 10 11 14 15 15 15 17 19 20 20 22 25 31 39 41 46 46 47 48 50 50 58 61 64 65 68 70 77 79 81 4.0.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Quasiperiodic functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . “Fourier series” of a quasiperiodic function . . . . . . . . . . . . . . . . . . . 4.2 4.2.1 The iterated Fourier series . . . . . . . . . . . . . . . . . . . . . . . . 4.2.2 Analyzing the coefficients ˆF(k) . . . . . . . . . . . . . . . . . . . . . 4.2.3 Approximation theorems for sliding window embeddings . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 81 84 84 88 93 4.3 The geometric structure of SWd,τ SZ f 95 4.4 Persistent Homology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 4.5 Computational Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 4.5.1 An approximation strategy using a persistent Künneth formula . . . . 110 . . . . . . . . . . . . . . . . 111 4.5.1.1 An example with 2 frequencies 4.5.1.2 Computational Results . . . . . . . . . . . . . . . . . . . . . 112 4.5.2 An application to music theory . . . . . . . . . . . . . . . . . . . . . 114 CHAPTER 5 STABILITY OF MULTISCALE CIRCULAR COORDINATES . . . . 117 5.0.1 The sparse circular coordinates algorithm . . . . . . . . . . . . . . . . 117 5.1 The stability set-up . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 5.1.1 Partition of Unity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 5.1.2 Weights on edges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 . . . . . . . . . . . . . . . . . . . . . . 130 5.3.1 Landmark Augmentation . . . . . . . . . . . . . . . . . . . . . . . . . 131 5.3.2 Coordinates old and new . . . . . . . . . . . . . . . . . . . . . . . . . 136 5.3.3 Wasserstein stability . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 5.4 Example & Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 5.2 Geometric noise model 5.3 The general Wasserstein noise model BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 x LIST OF TABLES Table 4.1: Example of τ estimation: Candidates for τ, along with the corresponding local minimums, and the angles θk,l (in degrees) between uk and ul . . . 101 Table 4.2: Computational times, and number of points, for the landmark and Kün- neth approximations to bcdR i (SWd,τ f), i ≤ 2. . . . . . . . . . . . . . . . . 113 Table 4.3: Areas for confidence regions from bcdR i (XL × YL) (red), i = 1, 2 (see Figure 4.4). A smaller area suggests a better approx- imation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 i (L) (blue) and bcdR Table 4.4: List of frequencies in the amplitude-frequency spectrum: The first row is the list of frequencies that were detected. The second row is their conversion to Hertz. The third row is their ratio with respect to the first one.115 xi LIST OF FIGURES Figure 1.1: A filtered simplicial circle X . The numbers next to simplex indicate when that corresponding simplex appeared in the filtration. . . . . . . . Figure 1.2: The product filtrations X × X (left) and X ⊗ X (right). The numbers next to simplex indicate when that corresponding simplex appeared in the filtration. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Figure 1.3: In the leftmost figure, we see a quasiperiodic function. In the mid- dle figure, we see a PCA visualization of the reconstructed torus from sliding window embedding. In the rightmost figure, we see the 1 and 2-dimensional Rips persistence diagrams (blue and red points respec- tively) of the sliding window point cloud. . . . . . . . . . . . . . . . . . . Figure 1.4: (Left) The data set X of 1000 points sampled around a circle, with two different sets of 40 landmarks (Middle). For each of these sets, we obtain a function that assigns to each data point in X a circular coordinate. (Right) We see a comparison of the two coordinate functions. Figure 2.1: A filtered simplicial circle K = {Ki}i, with Ki = K5 for i ≥ 5. Figure 2.2: The Lorenz attractor for parameters σ = 10, β = 8 3, and ρ = 28. . . . . . . . . . . . . . . . . . Figure 2.3: The evolution of (0, 0) under the irrational flow φ on T2 as defined in Example 2.4.2 for ω = 3. . . . . . . . . . . . . . . . . . . . . . . . . . . √ Figure 2.4: Time series associated to the observation f of the evolution of (0, 0) for the irrational flow φ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 5 10 13 37 39 40 42 Figure 2.5: Dynamical System to Sliding Window Reconstruction for a counter- clockwise flow on S1: In the leftmost figure, we see a standard circle. In the middle, we see the time series generated g(t). In the rightmost figure, we see the reconstructed circle from sliding window embedding. . 44 Figure 2.6: Dynamical System to Persistence for a rational flow on T2: In the left- most figure, we see a rational flow on T2. In the second, we see the time series generated g(t). In the third figure, we see a PCA visualiza- tion of the reconstructed circle from sliding window embedding. In the rightmost figure, we see the 1- dimensional Rips persistence diagram of a sliding window point cloud sampled from the third figure. . . . . . . . 44 xii Figure 2.7: Dynamical System to Persistence for an irrational flow on T2: In the leftmost figure, we see an irrational flow on T2. In the second, we see the time series generated g(t). In the third figure, we see a PCA visu- alization of the reconstructed torus from sliding window embedding. In the rightmost figure, we see the Rips persistence diagrams in dimensions 1, 2 of a sliding window point cloud sampled from the third figure. . . . . Figure 3.1: Visual representation for the deformation retract H3. √ √ 3) ≡ ( Figure 4.1: The sets Zβ for tuples β = ( 2, √ √ √ √ 3} (third), and β = ( 2, 2 + 2 3, 3 . . . . . . . . . . . √ √ 3, 0) (left), β = ( 2+ √ 3, π) (right). 3) (second), {√ 2, √ 2, √ √ √ 2, 3, 45 58 98 Figure 4.2: Example: The objective function G(x) for finding an optimal τ, for the √ function f(t) = eit + ei Figure 4.3: (Left) real(cid:16) f(t)(cid:17) = 1√ √ 3t + ei( 2 cos(t) + 1√ 3+1)t. 2 cos( . . . . . . . . . . . . . . . . . . . 101 √ 3t) for the quasiperiodic time series f, and (Right) a PCA projection into R3 of the point cloud SWd,τ f. 111 Figure 4.4: Confidence regions for bcdR i (XL × YL), i = 1, 2. For a given color, each box (confidence region) contains a point (‘J , ρJ) corresponding to a unique J ∈ bcdR i (L) and bcdR Figure 4.5: The audioread plot of a dissonant music sample created on a brass horn. i (SWd,τ f). . . . . . . . . . . . . . . . 114 115 Figure 4.6: The amplitude-frequency spectrum of the music sample plot using Fast Fourier Transform. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 Figure 4.7: (Left) PCA representation of the sliding window point cloud generated from the dissonant sample with parameters d = 9 and τ = 0.02858. (Right) Persistence Diagrams in homological dimension 1 and 2. The dotted lines separate the top 2 persistence points (sim. maximum per- sistence point) from the rest in dimension 1 (sim. dimension 2). . . . . . 116 Figure 5.1: An example of reconstructed toroidal dynamics: (Left) The irrational √ 3. (Second) The winding on a 2-torus starting at (0, 0) with slope sliding window embedding of the observation f(t) = 1√ 2 eit + 1√ 3t of the winding. (Third) The Rips persistence diagram in dimension 0, 1. The two 1-persistent cocycles can be used to create two sets of circular coordinates. (Right) The pair of coordinates can be used to reconstruct the toroidal winding. The average slope is estimated to be 1.9698. . . . . 119 2 ei √ xiii Figure 5.2: An example demonstrating stability of Circular Coordinates: (Left) The data set X of 1000 points sampled around a circle, with two different sets of 40 landmarks (Middle). For each of these sets, we obtain a function that assigns to each data point in X a circular coordinate. (Right) We see a comparison of the two coordinate functions. . . . . . . . . . . . . . 145 Figure 5.3: Comparison between Hausdorff and Wasserstein noise: (Left) Example of the dataset in black and 16 landmarks shown in blue. (Right) Com- parison of the number of replicates against the incurred error between the circular coordinates. Red shows the initial ‘Zero-Hausdorff-distance’ pair, while green shows the second ‘Zero-Wasserstein-distance’ pair. . . 146 xiv CHAPTER 1 INTRODUCTION The story begins with the need to understand time series data. Such data prevails in this world and makes for an important object to study. As a result, there are many methods to study it. Some of these include the Discrete Fourier Transform, Wavelet analysis, correlation methods, etc. One method for detecting recurrence in time series data was recently developed [59] using ideas from geometry and topology. This novel framework used two key ingredients, sliding window embeddings and persistent homology. The first of these ingredients, sliding window embeddings, were originally used in the study of dynamical systems to reconstruct the topology of underlying dynamics, under smoothness conditions given by Takens [67], from generic observation functions. It was shown in [59] that the sliding window embedding of a periodic function is homeomorphic to a circle. We study a closely related class of functions, namely quasiperiodic functions, which are defined as a superposition of periodic functions with non-commensurate harmonics. Such dynamics appear naturally in biphonation phenomena in mammals [74], as well as in the transition to chaos in rotating fluids [37]. An important point conveyed by Takens’ theorem [67] is that the topological shape of the sliding window embedding can be measured and leveraged for applications. To measure this shape, we turn to our second ingredient, persistent homology [28, 76]. It is an algebraic and computational tool widely used in Topological Data Analysis (TDA) to quantify mul- tiscale features of shapes. The input to a persistent homology computation is a sequence of topological spaces called a filtration, while the output is a multiset of intervals called a barcode, which constitutes a finite topological invariant of the coarse geometry governing the shape of a given point cloud. Some of its applications to science and engineering include recurrence detection in time series data [53, 57, 59], coverage problems in sensor networks [23], the identification of spaces 1 of fundamental features from natural scenes [15], inferring spatial properties of unknown environments via biobots [26], and many more. Some of the underlying ideas of persistence are also starting to permeate pure mathematics, most notably symplectic geometry [61, 70]. Although persistent homology is informative about the topology of data sets, one can further use it to perform nonlinear dimensionality reduction, for example on the point cloud obtained from sliding window embeddings, for the purposes of visualization and reconstruc- tion of the underlying dynamics. This recoordinatization process, called Eilenberg-MacLane coordinatization, turns persistent cohomology classes into maps from point clouds into vari- ous Eilenberg-MacLane spaces, like the circle [25, 55], real or complex projective space [54], or lens spaces [60]. This dissertation focuses on developing theoretical tools in the field of TDA and more specifically, in the study of dynamical systems on tori. There are three major contributions: 1. Theoretical development of persistent homology: We develop two persistent Künneth formulae, that is, results relating persistent homology of two filtered spaces to persistent homology of their products. Leveraging these formulae, we present novel methods for algorithmic and abstract computations of persistent homology. 2. Theoretical foundations of sliding window embeddings: We prove foundational results in the theory of sliding window embeddings for quasiperiodic functions and develop a theoretical framework to detect quasiperiodicity in time series data using sliding window embeddings and a persistent Künneth formula for Rips complexes. 3. Stability results for circular coordinates: The circular coordinatization algorithm identifies a significant Rips persistent cohomology class on a subset of the point cloud called the landmarks, and solves a linear least squares optimization problem to con- struct a circle valued function on the data set. We prove that circular coordinates are stable under Wasserstein noise on the landmark set. 2 1.1 Outline & Overview of the dissertation Due to the diverse nature of research problems discussed here, a wide range of mathe- matical concepts were used. While a comprehensive review for all of them is beyond the scope of this dissertation, we provide the necessary background in Chapter 2. We prove the two persistent Künneth formulae in Chapter 3 and revisit the persistent homology of an N-torus as an application. In Chapter 4, we develop the theory of sliding window embed- dings for quasiperiodic functions. Using theorems from Chapter 3, we provide an alternate strategy to recover toroidal features from the sliding window point clouds. We also present an application where we characterize dissonance in music theory as a quasiperiodic feature. In Chapter 5, we prove stability results for the construction of sparse circular coordinates algorithm under Wasserstein noise on the landmarks. Next we provide an overview of the main results in this dissertation. 1.1.1 Persistent Künneth theorems For a Principal Ideal Domain (PID) R and topological spaces X and Y , the classical Künneth formula given by the split natural short exact sequence 0 →M (Hi(X) ⊗R Hn−i(Y )) → Hn(X × Y ) →M (TorR(Hi(X), Hn−i−1(Y ))) → 0 (1.1) i i relates the homology of the product space X × Y to the homology of spaces X and Y , with coefficients in R. As discussed above, the persistent homology algorithm takes a sequence of topological spaces or simplicial complexes, called a filtration X : X0 ,→ X1 ,→ X2 ,→ ··· ,→ Xd ,→ ··· where d ∈ N0 = N ∪ {0}, as the input. It returns in homological dimension n, a bar- code bcdn(X ) which is a collection of real intervals, or equivalently a persistence diagram dgmn(X ), which is a multiset of points in the plane R2. In this dissertation, we exploit the equivalence of these two invariants and use them interchangeably. A brief review is provided 3 in section 2.3. In Chapter 3, we develop Künneth formulae for persistent homology. For filtered topological spaces X and Y, we consider two notions of product filtrations: (X ⊗ Y)d = [ i+j=d (X × Y)d = Xd × Yd and Xi × Yj. These choices are motivated by different observations. The first choice of filtration, which we refer to as the categorical product, is of interest for two reasons: (a) it is the product in the category of filtered topological spaces, and (b) it is relevant in certain computational settings. More precisely, if (X, dX) is a metric space and R(X, dX) = {σ ⊂ X : |σ| < ∞, diam(σ) ≤ } is its Rips complex at parameter , then R(X × Y, dX×Y ) = R(X, dX) × R(Y, dY ) [1, Proposition 10.2]. Here dX×Y is the maximum metric (cid:16)(x, y), (x0, y0)(cid:17) = max{dX(x, x0), dY (y, y0)}, dX×Y and the product of Rips complexes is in the category of abstract simplicial complexes (see section 3.1). The other choice of filtration, which we call the tensor product, is relevant due to an algebraic resemblance between the short exact sequence it satisfies and the classical equation 1.1. In Figure 1.1, we see an example of a topological circle X , while in Figure 1.2, we see two filtrations of a 2-torus defined by our products. Figure 1.1: A filtered simplicial circle X . The numbers next to simplex indicate when that corresponding simplex appeared in the filtration. In the following theorem, we state the two Künneth formulae in terms of their barcode representation: 4 Figure 1.2: The product filtrations X × X (left) and X ⊗ X (right). The numbers next to simplex indicate when that corresponding simplex appeared in the filtration. Theorem 1.1.1. Let X and Y be pointwise finite filtrations. Then the barcodes of the categorical product X × Y are given by the (disjoint) union of multisets (1.2) Similarly, the barcodes for the tensor product filtration X ⊗ Y satisfy bcdn (X × Y) = [ . (cid:27) (cid:26) i+j=n I ∩ J (cid:12)(cid:12)(cid:12)(cid:12) I ∈ bcdi(X ) , J ∈ bcdj(Y) ) (cid:12)(cid:12)(cid:12)(cid:12) I ∈ bcdi(X ) , J ∈ bcdj(Y) [ ) (cid:12)(cid:12)(cid:12)(cid:12) I ∈ bcdi(X ) , J ∈ bcdj(Y) (ρJ + I) ∩ (ρI + J) ( (‘J + I) ∩ (‘I + J) ( bcdn(X ⊗ Y) = [ [ i+j=n i+j=n−1 where ‘J and ρJ denote, respectively, the left and right endpoints of the interval J. The first Künneth formula implies the following corollary for the Rips persistent homology (i.e. persistent homology of Rips filtration) of product metric spaces: Corollary 1.1.2. Let (X, dX), (Y, dY ) be finite metric spaces and let bcdR n-th dimensional barcode of the Rips filtration R(X, dX) := {R(X, dX)}≥0. Then, (cid:27) j (Y, dY ) n (X × Y, dX×Y ) = [ i (X, dX) , J ∈ bcdR (cid:12)(cid:12)(cid:12)(cid:12) I ∈ bcdR bcdR I ∩ J (cid:26) i+j=n n (X, dX) be the for all n ∈ N0, where dX×Y is the maximum metric. 5 The above formulae also hold true when the inclusions Xi ,→ Xi+1 and Yi ,→ Yi+1 are replaced by continuous maps. The categorical product of R-indexed diagrams is just the R-indexed diagram defined using index-wise products. That is, (X × Y)r = Xr × Yr for all r ∈ R. The generalized tensor product ⊗g of N0-indexed diagrams —equivalent to ⊗ for inclusions— is defined as follows: the space (X ⊗g Y)k is the homotopy colimit (see section 2.2.2) of the functor from the poset 4k = {(i, j) ∈ N2 : i + j ≤ k} to Top sending (i, j) to Xi × Yj, and (i ≤ i0, j ≤ j0) to the map Xi × Yj → Xi0 × Yj0 induced by composite maps Xi → Xi0 and Yj → Yj0. The map (X ⊗g Y)k → (X ⊗g Y)k+1 is the one induced at the level of homotopy colimits by the inclusion 4k ⊂ 4k+1. 1.1.1.1 Related work Different versions of the algebraic Künneth theorem in persistent homology have appeared in the last three years. In [62, Proposition 2.9], the authors prove a Künneth formula for the tensor product of filtered chain complexes, while [12, Section 10] establishes Künneth theorems for the graded tensor product and the sheaf tensor product of persistence modules. In [14], the authors prove a Künneth formula relating the persistent homology of metric spaces (X, dX), (Y, dY ) to the persistence of their cartesian product equipped with the L1 (sum) metric (X×Y, dX +dY ), for homological dimensions n = 0, 1. The persistent Künneth theorems proven in this dissertation and [35] are the first to start at the level of filtered spaces, identifying the appropriate product filtrations and resulting barcode formulae. Compared to the sum metric [14], we remark that our results for the maximum metric hold in all homological dimensions. 6 1.1.2 Sliding window embeddings of quasiperiodic functions The sliding window embedding of a function f : R → C for a fixed embedding dimension d ∈ N and time delay τ > 0, at t ∈ R is defined as  f(t) f(t + τ) ... f(t + dτ)  . SWd,τ f(t) = This definition is motivated by Takens’ embedding theorem which we cover in section 2.4.1. In its essence, the theorem provides conditions under which a smooth attractor can be reconstructed from a sequence of observations made with a generic observation function. While this reconstructed attractor might have a different geometric shape than the original, its topology is still preserved. As discussed at the beginning of this chapter, if the set of harmonics controlling a func- tion is incommensurate, that is if it is linearly independent over Q, we call the function a quasiperiodic function. More rigorously, we define f : R → C to be quasiperiodic with a given set of frequencies {ω1, . . . , ωN} if there is a function F : RN → C, called a parent function, such that F is periodic in the n-th variable with period 2π , the restriction of F to ωn the diagonal takes the values of f, and N is minimal. See Definition 4.1.1. Assuming that the parent function is continuously differentiable and using tools from multivariate harmonic analysis, we can write a Fourier-like series that converges everywhere to F and its restriction to the diagonal gives us the following series for the quasiperiodic function f: f(t) = F(t, . . . , t) = X NQ ωn n=1 (2π)N 2π ω1Z 0 k∈ZN e−ik1ω1t1 ˆF(k)eithk,ωi ωNZ ω2Z 2π 2π ··· 0 0 ˆF(k) = F(t1, . . . , tN)e−ikN ωN tN dtN . . . dt1. where ω is the frequency vector (ω1, . . . , ωN) and h·,·i is the dot product in RN. As in single variable Fourier analysis, we can use a truncation parameter Z ∈ N0 to approximate f by 7 the partial sum polynomials SZ f: ˆF(k)eithk,ωi SZ f(t) = X o. Since SZ f(t) → f(t) everywhere as Z → ∞ and since k∈IN Z Z =nk ∈ ZN (cid:12)(cid:12)(cid:12) ||k||∞ ≤ Z where IN for fixed parameters d, τ, the map f → SWd,τ f is a bounded linear operator (see Proposition 2.4.8), we conclude that SWd,τ SZ f → SWd,τ f everywhere as Z → ∞. The next theorem gives us a series of bounds —for different levels of regularity of f— on the proximity of sliding window embeddings of f to that of its truncated polynomial SZ f. Moreover, the more regular f is, the faster the convergence of sliding window embeddings will be. Then by the stability theorem for persistent homology [19], we have the following amalgamation of theorem 4.2.8 and corollary 4.2.9: Theorem 1.1.3. Let r ∈ N \ {1}. If F ∈ Cr(cid:16)RN , C(cid:17), then for any bounded T ⊂ R, i (SWd,τ SZ f(T))(cid:17) ≤ 2dH SWd,τ f(T), SWd,τ SZ f(T)(cid:17) (cid:16) i (SWd,τ f(T)), bcdR r(cid:16) Area(SN−1)(cid:17)1/2 1/2 √  NX √ !1/2 N √ ωr−1 2r − 2 min (cid:16)bcdR d + 1 Zr−1 NQ ||RZ(∂r nF)||2 ≤ 2 dB |ωn| n=1 n=1 where RZ f := f − SZ f, and dH and dB are the Hausdorff and the Bottleneck distance respectively (see section 4.4). The theorem tells us that as the sliding window point cloud SWd,τ SZ f(T) approximates SWd,τ f(T) in the Hausdorff sense, the Rips persistent homology bcdR i (SWd,τ SZ f) converges to bcdR i (SWd,τ f) in the Bottleneck sense. This suggests that one could replace the study of a function f with that of its approximation SZ f. Accordingly, we study the geometric struc- ture of the sliding window embedding of the truncated polynomial SZ f. We see next that under appropriate conditions on d, τ, and Z, the closure of the sliding window embedding SWd,τ SZ f is homeomorphic to TN wrapped around Td+1. Indeed, we have the following structure theorem: 8 Theorem 1.1.4. The sliding window embedding SWd,τ SZ f(Z) = n SWd,τ SZ f(z) | z ∈ Zo is dense in a space homeomorphic to TN in Td+1 if • d + 1 ≥ α := the number of terms in IN Z with non zero coefficients, and • τ satisfies that G(τ) < (d + 1)2 for G(x) = X (cid:12)(cid:12)(cid:12)1 + eixhk−l,ωi + ··· + eixhk−l,ωid(cid:12)(cid:12)(cid:12)2 . k6=l∈IN Z The condition on τ only guarantees the same topology as a torus. Unfortunately, the Rips persistent homology cares about the underlying geometry and that requires τ to satisfy an extra condition: for some practically reasonable large Υ ∈ R+, τ satisfies τ = argmin x∈[0,Υ] G(x). The last main result we present here pertains to the Rips persistent homology of SWd,τ SZ f. Let λmin be the square of the minimum singular value of  ΩZ,f = eihk1,ωiτ0 ... eihk1,ωiτ d eihkα,ωiτ0 ··· ... ··· eihkα,ωiτ d, ...  and | ˆF(k)min| be the smallest non-zero Fourier coefficient in absolute value. Then we have the following theorem: Theorem 1.1.5. For i ≤ N, there will be at least (cid:16)N (cid:17) bars i )) (0, d1), (0, d2), . . . , (0, d(N (cid:17). SWd,τ SZ f,||·||2 where dn ≥ √ 3| ˆF(k)min|√ (cid:16) λmin in bcdR i i We finish this section with an example: Example 1.1.6. Assume that we are given a quasiperiodic time series f(t) = cos(t) + √ 3t). The sliding window embedding SWd,τ f(R) of f with appropriate dimension and cos( delay recovers the topology of T2. Rips persistent homology confirms that in the accompa- nying figure. 9 Figure 1.3: In the leftmost figure, we see a quasiperiodic function. In the middle figure, we see a PCA visualization of the reconstructed torus from sliding window embedding. In the rightmost figure, we see the 1 and 2-dimensional Rips persistence diagrams (blue and red points respectively) of the sliding window point cloud. 1.1.2.1 Related work Since the inception of sliding windows and persistence technique for time series analysis in [59], there have been a few advancements to both theory and applications. The first results on sliding window embeddings for quasiperiodic functions [53] were restricted to the special case of sums of exponentials with incommensurate frequencies. Said results are proved in generality in this dissertation and [36]. While the sliding window embeddings of quasiperiodic functions trace tori densely, in [75], the authors construct families of time series whose sliding window embeddings trace Klein bottles, spheres, and projective planes. A recently published survey ties the worlds of dynamical systems and topological data analysis [57]. Among the applications of sliding window embeddings and persistence, a few are: periodicity quantification in gene expression data [58]; (quasi)periodicity detection in video data [69]; synthesis of slow-motion videos from recurrent movements [68]; detection of wheeze, which is an abnormal whistling sound produced while breathing [33]; and detection and classification of chatter (vibrations caused by machines) in machining [45, 46]. 10 1.1.3 Stability of circular coordinates Circular coordinates on a data set were developed to aid non-linear dimensionality reduction analysis [25]. Such reduction schemes address the problem of representing high dimensional data in terms of low dimensional coordinates. The authors used persistent cohomology to construct circular coordinates on a data set X. The algorithm identifies a significant integer persistent cohomology class on the Rips filtration and solves a linear least squares optimization problem to construct a circled valued function on the data set. Using similar ideas and principal Z-bundles, the sparse circular coordinates were con- structed by using a landmark set L = {‘1, . . . , ‘N} in lieu of the entire data set X [55]. The idea is as follows. For a fixed prime q > 2, compute the 1-dimensional Rips persistent cohomology P H1(R(L); Zq). Choose a bar [a, b) from the resultant barcode bcdR(L) sat- isfying 2a < b. Let 2a < 2α < b and let η00 ∈ Z1(R2α(L); Zq) be a cocycle representative for the persistent cohomology class corresponding to [a, b). Lift η00 to an integer cocycle η0 ∈ Z1(R2α(L); Z) such that η00 − η0 mod q is a coboundary in C1(R2α(L); Zq). Lastly, define η to be the image of η0 under C1(R2α(L); Z) → C1(R2α(L); R) induced by the inclu- sion ι : Z ,→ R. Choose positive weights for the vertices and edges of R2α(L) and let d+ 2α be the weighted Moore-Penrose pseudoinverse of the coboundary map and define d2α : C0(R2α(L); R) → C1(R2α(L); R). τ := −d+ 2α(η) and θ := η + d2α(τ). Denote τj := τ([‘j]) and θjk := θ([‘j, ‘k]) when [‘j, ‘k] ∈ R2α(L), and 0 otherwise. Let Bα(‘j) denote the ball of radius α centered around ‘j ∈ L, and {ϕj}j a partition of unity subordinate to the collection {Bα(‘j)}j. The sparse circular coordinates are defined as 11 follows: hθ,τ : N[ 2πi τj + NX r=1  . ϕr(b)θjr Bα(‘r) → S1 ⊂ C r=1 Bα(‘j) 3 b 7→ exp We give a more detailed version of this algorithm in section 5.0.1. Observe that the coordinates generated from this algorithm depend on the choice of landmarks. For any two finite landmark sets L, ˜L with probability weights ω and ˜ω, we obtain two circular coordinate functions h and ˜h respectively. Assume that dW,∞((L, ω), (˜L, ˜ω)) < δ where dW,∞ is the Wasserstein-Kantorovich-Rubinstein metric as in Definition 2.5.5. Our first result shows the stability of circular coordinates for a special case, that is when L and ˜L are in a weight preserving bijective correspondence. We call this the geometric stability of circular coordinates. The following theorem appears in more detail as theorem 5.2.7. Theorem 1.1.7. If (L, ω) and (˜L, ˜ω) are landmark sets in a weight preserving bijective correspondence, and h and ˜h are the associated circle-valued functions, then ||h − ˜h||∞ ≤ Cδ where C is a term dependent on the choice of weights, the harmonic cocycle, and partitions of unity used in the construction of circular coordinates. Let us look at the following example: Example 1.1.8. We start with a dataset X with 1000 points sampled around a unit circle with Gaussian noise of 0.5. We first select the “blue” landmark set with 40 points by maxmin sampling. We define the “red” landmark set by choosing the respective nearest neighbours of the “blue” landmarks. See Figure 1.4. 12 Figure 1.4: (Left) The data set X of 1000 points sampled around a circle, with two different sets of 40 landmarks (Middle). For each of these sets, we obtain a function that assigns to each data point in X a circular coordinate. (Right) We see a comparison of the two coordinate functions. In a more general scenario, L and ˜L might have different cardinalities or vertex probabil- ity weights. In section 5.3.1, we introduce a way to create two new landmark sets (Lm, ωm), (˜Lm, ˜ωm) such that they are in a weight preserving bijective correspondence, thereby reduc- ing the case of Wasserstein stability to the case of geometric stability. Both landmark sets Lm, ˜Lm are just L, ˜L respectively, augmented with copies of points. The next result de- scribes the relationship between the circular coordinates generated by L and the augmented Lm (and similarly for ˜L and ˜Lm). Theorem 1.1.9. Let Lm be the landmark set augmented from L, and hm and h be the circular functions associated to them. Then for all b ∈ X, hm(b) = h(b). See theorem 5.3.13 for more details. As a consequence, we can replace h, ˜h with hm, ˜hm to obtain ||h − ˜h||∞ = ||hm − ˜hm||∞ where the right hand side can be bounded using bounds the geometric stability theorem. These arguments are presented in section 5.3.3, in particular summarized in Theorem 5.3.15. 13 1.1.3.1 Related work In [25], a strategy for non-linear dimensionality reduction was developed using the first (non- sparse) circular coordinates. In [55], the theory of principal Z-bundles was used to construct sparse circular coordinates by considering Rips filtration on a landmark set L ⊂ X. In [54], the multiscale projective coordinates were constructed, along with a non-linear dimen- sionality reduction scheme called Principal Projective Component Analysis. Using similar techniques, lens spaces coordinates were constructed in [60]. The authors also presented a non-linear dimensionality reduction scheme called LPCA or Lens Principal Component Analysis. 14 CHAPTER 2 BACKGROUND This chapter deals with the necessary mathematical background for the later chapters of this dissertation. We provide a terse introduction to category theory in 2.1. In 2.2, we provide background material for an assortment of topics in topology. Using ideas from these two sections, we give a brief background for persistent homology in 2.3. In section 2.4, we discuss the basics of dynamical systems along with Takens’ theorem and sliding window embeddings. In section 2.5, we review one variable Fourier series, Kronecker’s approximation theorem, and Wasserstein metric on probability measures. 2.1 Category Theory In this section, we give a succinct review of category theory. For a more comprehensive review, we refer the mathematician reader to [48] and the data scientist reader to [65]. Category theory was originally developed by Eilenberg and MacLane to bridge the gap between the fields of algebra and topology. More generally, category theory takes a bird eye’s view of mathematics by considering abstractions of mathematical concepts. The advantage to this view is that a lot of intricate and subtle results can be proved by ‘cleaner’ methods. Over the last few decades, category theory has found itself useful in sciences, like quantum physics[2] and theoretical computer science [3]. 2.1.1 Definitions and Examples Definition 2.1.1. A catgeory C consists of a class of objects denoted by Obj(C) and a set of morphisms Mor(a, b) for any two objects a, b ∈ Obj(C) such that the following axioms hold: 1. If f ∈ Mor(a, b) and g ∈ Mor(b, c), then g ◦ f ∈ Mor(a, c). 2. For each a ∈ Obj(C), there is a unique morphism 1a ∈ Mor(a, a) called the identity 15 morphism satisfying f ◦ 1a = f = 1b ◦ f for any b ∈ Obj(C) and any f ∈ Mor(a, b). 3. For any f ∈ Mor(a, b), g ∈ Mor(b, c), and h ∈ Mor(c, d), h ◦ (g ◦ f) = (h ◦ g) ◦ f. Some of the categories that we are interested in are: Example 2.1.2. Top is an example of a category with topological spaces as objects and continuous maps as morphisms. Example 2.1.3. Given a commutative ring R with unity, ModR is the category of all R- modules as objects and for any two R-modules M, N, the set of morphisms from M to N is the set of all R-module homomorphisms from M to N. Example 2.1.4. Given a commutative ring R with unity, ChR is the category of all chain complexes of R-modules as objects and for any two such chain complexes C, C0, the set of morphisms from C to C0 is the set of all chain maps from C to C0. Definition 2.1.5. A category C is small if the class of its objects, Obj(C), forms a set. In some categories, like Top, the sets of morphisms may be very large in cardinality. For purposes of this document, we are interested in another special type of category that restricts the size of morphism classes: Definition 2.1.6. A category is called thin if there is at most one morphism between any two objects. Definition 2.1.7. A subcategory D of C consists of the following data: 1. A subclass Obj(D) of Obj(C), 16 2. For each a, b ∈ Obj(D), a subset of MorC(a, b), 3. For each a ∈ Obj(D), the identity 1a ∈ MorC(a, a) belongs to MorD(a, a), and 4. For each f : MorD(a, b) and g ∈ MorD(b, c), the composition g ◦ f is in MorD(a, c). Definition 2.1.8. A full subcategory D of C satisfies MorD(a, b) = MorC(a, b) for any objects a, b ∈ Obj(D). In fact, any subclass of Obj(C) yields a unique full subcategory of C. Definition 2.1.9. For a category C, its opposite category Cop is defined as Obj(Cop) := Obj(C) MorCop(a, b) := MorC(b, a), that is, all the morphisms are reversed. 2.1.2 Functors and natural transformations Definition 2.1.10. Let C and C0 be categories. A covariant functor D from C to C0 associates to each object, a ∈ Obj(C) an object D(a) ∈ Obj(C0) and to each morphism f ∈ MorC(a, b), a morphism D(f) ∈ MorC0(D(a), D(b)). Moreover, it is required that the functor respects morphism composition and preserves the identity morphisms, that is, D(g ◦ f) = D(g) ◦ D(f) and D(1a) = 1D(a) respectively. Similarly, a contravariant functor D from C to C0 associates to each object a ∈ Obj(C), an object D(a) ∈ Obj(C0) and to each morphism f ∈ MorC(a, b), a morphism D(f) ∈ MorC0(D(b), D(a)). Moreover, it is required that the functor preserves the identity mor- phisms, however D(g ◦ f) = D(f) ◦ D(g). 17 For example, if C = Top and C0 = ModR, then the functor D that takes a topological space X to the homology module Hn(X; R) is covariant, while the functor D0 that takes X to the cohomology module Hn(X; R) is contravariant. Definition 2.1.11. Let D, D0 be covariant functors from C to C0. A natural transformation η : D → D0 consists of a family of morphisms η(a) : D(a) → D0(a) for each object a ∈ Obj(C), such that for each morphism f ∈ MorC(a, b), the diagram η(a) D(a) D(f) D(b) η(b) D0(a) D0(b) D0(f) commutes. Definition 2.1.12. If C and I are categories, with I small, then we denote by CI the category whose objects are functors from I to C, and whose morphisms are natural transformations between said functors. The objects of the functor category CI are often referred to in the literature as I-indexed diagrams in C. Two diagrams D, D0 ∈ CI are said to be isomorphic, denoted D ∼= D0, if they are naturally isomorphic as functors. Here is an example describing the main type of indexing category we will consider throughout the dissertation. Definition 2.1.13. A partially ordered set, or poset, is a set P with a relation (cid:22) satisfying the following properties: 1. Reflexivity: for each x ∈ P, we have x (cid:22) x. 2. Transitivity: for each x, y, z ∈ P satisfying x (cid:22) y and y (cid:22) z, it is also true that x (cid:22) z. 3. Antisymmetry: for each x, y ∈ P satisfying x (cid:22) y and y (cid:22) x, it is true that x = y. Example 2.1.14. Let (P,(cid:22)) be a partially ordered set (i.e., a poset). Let P denote the category whose objects are the elements of P, and a unique morphism x → y for each pair x (cid:22) y in P. We call P the poset category of P. 18 This category is both small and thin and will be used for the purpose of indexing category I. As for the target category C, we will mostly be interested in spaces and their algebraic invariants. 2.1.3 Coequalizers The contents of this section will be useful for the theory of homotopy colimits in section 2.2.2. Definition 2.1.15. The undercategory of c ∈ C, denoted (c ↓ C), is the category whose objects are pairs (c0, σ) consisting of an object c0 ∈ C and a morphism σ : c → c0 in C. A morphism from (c0, σ : c → c0) to (c00, β : c → c00) is a morphism τ : c0 → c00 in C such that τ ◦ σ = β. Remark 2.1.16. If σ : c → c0 is a morphism in C, then composing with σ induces covariant functors σ∗ : (c0 ↓ C) → (c ↓ C) and σ∗ op : (c0 ↓ C)op → (c ↓ C)op. Definition 2.1.17. Let {Ai}i∈I be a family of objects in a category C. The product of this family, if it exists, is an object P ∈ C along with morphisms pi : P → Ai such that for any Y ∈ C and any collection of morphisms {yi : Y → Ai}i∈I, there exists a unique morphism f : Y → P so that pi ◦ f = yi for each i. The product, since when it exists it is unique up to isomorphism, will be denoted × Ai. The existence of f for any Y and any {yi}i∈I, is referred to as the universal property defining the categorical product. i∈A The dual notion of coproduct of {Ai}i∈I is the object C ∈ C, when it exists, along with morphisms ci : Ai → C such that for any object Y and any collection of morphisms {yi : Ai → Y }i∈I, there exists a unique morphism g : C → Y such that g ◦ ci = yi for each i. The coproduct of {Ai}i∈I is denoted ‘ Ai, and the existence of g is the universal property i∈I defining it. 19 Example 2.1.18. If Ai ∈ Top, then the product × is the Cartesian product endowed with the product topology, while the coproduct ‘ Ai is the space whose underlying set Ai is i∈A their disjoint union. i∈I Definition 2.1.19. Let f, g : A → B be morphisms in a category C. The coequalizer of f and g, denoted coeq(A→→B) if it exists, is an object C ∈ C with a morphism q : B → C such that q ◦ f = q ◦ g. Moreover, if there is another pair (C0, q0) such that q0 ◦ f = q0 ◦ g, then there is a unique u : C → C0 satisfying u ◦ q = q0. Example 2.1.20. If f, g : A → B are two morphisms in Top, then coeq(A→→B) is the quotient space B .(cid:16) f(a) ∼ g(a), ∀a ∈ A (cid:17). 2.2 Algebraic Topology In this section, we provide a brief review of the classical Künneth formula for the product of topological spaces with coefficients in a Principal Ideal Domain (PID) in 2.2.1, an explicit model for the homotopy colimit of a diagram of topological spaces in 2.2.2, and the theory of principal bundles and Čech cohomology in 2.2.3. 2.2.1 The Classical Künneth Theorems The classical Künneth theorem in algebraic topology relates the homology of the product of two spaces to the homology of its factors. The relation is via a split natural short exact sequence, and the proof is a combination of the algebraic Künneth formula for chain com- plexes, and the Eilenberg-Zilber theorem. Both theorems are stated next, but first here are two relevant definitions: Definition 2.2.1. Let R be a commutative ring, and let C, C0 ∈ ChR. The tensor product chain complex C ⊗R C0 consists of R-modules (C ⊗R C0)n =L n−i) and boundary (Ci ⊗R C0 i 20 morphisms n−i −→ (C ⊗R C0)n Ci ⊗R C0 c ⊗R c0 7→ ∂ic ⊗R c0 + (−1)ic ⊗R ∂0 n−ic0. Definition 2.2.2. An R-module M is called flat, if for every short exact sequence 0 → A → A0 → A00 → 0 of R-modules, the induced sequence 0 → A ⊗R M → A0 ⊗R M → A00 ⊗R M → 0 is also exact. In particular, all free modules are flat. Theorem 2.2.3 (The Algebraic Künneth Formula). If R is a PID and at least one of the chain complexes C, C0 is flat (i.e., the constituent modules are flat), then for each n ∈ N0 there is a natural short exact sequence 0 −→ M i+j=n (Hi(C) ⊗R Hj(C0)) −→ Hn(C ⊗R C0) −→ M TorR(Hi(C), Hj−1(C0)) −→ 0 which splits but not naturally. i+j See for instance [40, Chapter 5, Theorem 2.1]. It is well known that when C and C0 are the singular chain complexes of two topological spaces X and Y , denoted by S∗(X; R) and S∗(Y ; R) respectively, then the Eilenberg-Zilber theorem [32] provides a link between the algebraic Künneth theorem and the homology of X × Y : Theorem 2.2.4 (Eilenberg-Zilber). For topological spaces X and Y , there is a natural chain equivalence ζ : S∗(X; R) ⊗R S∗(Y ; R) −→ S∗(X × Y ; R), and thus Hn(X × Y ; R) ∼= Hn for all n ≥ 0. (cid:16) S∗(X; R) ⊗R S∗(Y ; R)(cid:17) 21 The existence of ζ is in fact an application of the acyclic models theorem of Eilenberg and MacLane [30]. This theorem provides conditions under which two functors to the category of chain complexes produce naturally isomorphic homology theories. Later, we will use similar ideas to prove a persistent Eilenberg-Zilber theorem (Theorem 3.3.10), which then yields our persistent Künneth formula for the tensor product (Theorem 3.3.12). For now, here is the topological Künneth theorem: Corollary 2.2.5 (The topological Künneth formula). Let X, Y be topological spaces and let R be a PID. Then, there exists a natural short exact sequence (Hi(X; R) ⊗R Hj(Y ; R)) −→ Hn(X × Y ; R) −→ M TorR(Hi(X; R), Hj−1(Y ; R)) −→ 0 (2.1) 0 −→ M i+j=n which splits, though not naturally. i+j=n For the sake of completeness, here is an example using the topological Künneth formula to compute the homology of a product of topological spaces: Example 2.2.6. Let X = S1 = Y and R = Z. Then the homology modules are Hi(X; Z) = Z = Hi(Y ; Z) for i = 0, 1 and {0} otherwise. Since TorZ is {0} for any free input, we obtain that H0(X × Y ; Z) ∼= H0(X; Z) ⊗Z H0(Y ; Z) = Z ⊗Z Z ∼= Z H1(X × Y ; Z) ∼= H0(X; Z) ⊗Z H1(Y ; Z) ⊕ H1(X; Z) ⊗Z H0(Y ; Z) ∼= Z ⊕ Z H2(X × Y ; Z) ∼= H1(X; Z) ⊗Z H1(Y ; Z) = Z ⊗Z Z ∼= Z which is indeed the homology of a 2-torus. 2.2.2 Homotopy Colimits The machinery of homotopy colimits will be used in Section 3.1 to define the generalized tensor product ⊗g : TopN × TopN −→ TopN appearing in Theorem 3.3.12. We provide 22 here a basic review, but direct the interested reader to [27] or [73] for a more comprehensive presentation. If C is a category, then let BC denote its classifying space—i.e., the geometric realization of the nerve of C. Definition 2.2.7. For a small indexing category I, let D : I −→ Top be a functor. The colimit of D is defined as: colim(D) := coeq (2.2) a i→j D(i)→→a i  D(i) a i→j D(i) × B(j ↓ I)op→→a i  where the top map sends D(i) to itself via the identity, the bottom map sends D(i) to D(j) via D(i → j), and the first coproduct is indexed over all morphisms in I. Similarly, the homotopy colimit of D is defined as: hocolim(D) := coeq D(i) × B(i ↓ I)op (2.3) The top map D(i) × B(j ↓ I)op → D(j) × B(j ↓ I)op is D(i → j) times the identity, while the bottom map D(i)×B(j ↓ I)op → D(i)×B(i ↓ I)op is the identity of D(i) times the map on classifying spaces induced by (i → j)∗ op : (j ↓ I)op → (i ↓ I)op. It is worth noting that if D, D0 ∈ TopI, then any morphism D → D0 induces (functori- ally) a map hocolim(D) → hocolim(D0), and that if f ∈ JI and D ∈ TopJ, then f induces a natural map φf : hocolim(D ◦ f) → hocolim(D) called the change of indexing category. Moreover, we have the following theorem from [27]: Proposition 2.2.8. Let f : I → J, g : J → K and D : K → Top be functors. Then φg◦f = φg ◦ φf. While both the colimit and the homotopy colimit of a diagram of spaces yield methods for functorially gluing spaces along maps, only the latter preservers homotopy equivalences. Indeed, [73, Proposition 3.7] says: Theorem 2.2.9. Let D, D0 ∈ TopI. If D → D0 is a natural (weak) homotopy equivalence— i.e. each D(i) → D0(i) is a (weak) homotopy equivalence—then the induced map hocolim(D) → hocolim(D0) is a (weak) homotopy equivalence. 23 When the indexing category has a terminal object, that is, a unique object z such that for all i ∈ I there is a unique morphism i → z, then the homotopy colimit is particularly simple [27, Lemma 6.8]. Theorem 2.2.10. Suppose that I has a terminal object z. Then for all D ∈ TopI, the collapse map hocolim(D) → D(z) is a weak homotopy equivalence. Notice that by collapsing the classifying spaces B(j ↓ I)op and B(i ↓ I)op in the definition of homotopy colimit to a point, we recover the definition of the colimit. Next, we will see specific conditions under which this collapse defines a homotopy equivalence from hocolim(D) to colim(D). In order to state the result, we recall the notion of a cofibration. Definition 2.2.11. A continuous map f : A → X is called a cofibration if it satisfies the homotopy extension property with respect to all spaces Y . That is, given a homotopy ht : A → Y and a map H0 : X → Y such that H0 ◦ f = h0, then there is a homotopy Ht : X → Y such that Ht ◦ f = ht for all t. If f(A) is a closed subset of X, then f is called a closed cofibration. Remark 2.2.12. Let X ∈ TopN, and let T (X ) ∈ TopN be the functor defined as follows. For j ∈ N0, let Tj(X ) be the mapping telescope of X0 f1−→ ··· fj−2−−−→ Xj−1 f0−→ X1 Explicitly, Tj(X ) is the quotient space G !(cid:30) Tj(X ) = Xj × {j} t fj−1−−−→ Xj. Xi × [i, i + 1] (x, i + 1) ∼ (fi(x), i + 1). i 0 called the embedding dimension and a real number τ > 0 called the time delay, the sliding window embedding of f at t is given by:   SWd,τ f(t) = f(t) f(t + τ) ... f(t + dτ) If this function is indeed a time series generated by observing some underlying dynamical system, Takens’ theorem implies that by studying the shape of the sliding window point cloud, we can recover some information about the dynamical system. Let us look at some examples, with a simple function g(t) = cos(t) first. Example 2.4.5. Assume a particle at (1, 0) on a unit circle S1 is moving counter-clockwise with the function φ(t) = (cos(t), sin(t)). Let p : S1 → R defined as p((x, y)) = x be the observation. Then we get a time series g(t) = p(φ(t)) = cos(t). The sliding window embedding SWd,τ g(R) of g with appropriate dimension and delay re- covers the topology of S1. While the figure on the right is topologically a circle, it looks different from a standard circle geometrically. The reader might ponder why it would be a problem—because in real applications, we only have a discrete time series and the hope is that the sliding window embedding of a continuous approximation to this time series recovers the topology of the un- derlying dynamical system. In [58], Perea and Harer used Rips persistent homology to study finite sliding window point clouds generated from general periodic functions and provided 43 Figure 2.5: Dynamical System to Sliding Window Reconstruction for a counterclockwise flow on S1: In the leftmost figure, we see a standard circle. In the middle, we see the time series generated g(t). In the rightmost figure, we see the reconstructed circle from sliding window embedding. conditions on parameters d and τ under which the geometry of the recovered topological circle is a good geometric approximation. In particular, we will use persistent homology of Rips complexes on SWd,τ g(T) ⊂ SWd,τ g(R) ⊂ Cd+1 for some T ⊂ R. Next, we have another example of sliding window embedding of a periodic function g(t) = cos(t) + cos(3t). Example 2.4.6. Assume a particle at (0, 0) on T2 is moving with the function φ(t) = (t, 3t). Let p : T2 → R defined as p((x, y)) = cos(x) + cos(y) be the observation. Then we get a time series g(t) = p(φ(t)) = cos(t) + cos(3t). The sliding window embedding SWd,τ g(R) of g with appropriate dimension and delay re- covers the topology of S1. Rips persistent homology confirms that in Figure 2.6. Figure 2.6: Dynamical System to Persistence for a rational flow on T2: In the leftmost figure, we see a rational flow on T2. In the second, we see the time series generated g(t). In the third figure, we see a PCA visualization of the reconstructed circle from sliding window embedding. In the rightmost figure, we see the 1- dimensional Rips persistence diagram of a sliding window point cloud sampled from the third figure. 44 √ A closely related function to the periodic function in the example above is g(t) = 3t), which is an example of a quasiperiodic function, which we will study cos(t) + cos( in its generality in Chapter 4. In simpler terms, a quasiperiodic function is controlled by two or more harmonics and these harmonics are linearly independent over Q. A special first case was studied by Perea in [53]. √ Example 2.4.7. Assume a particle at (0, 0) on T2 is moving with the irrational flow function 3t). Let p : T2 → R defined as p((x, y)) = cos(x) + cos(y) be the observation. φ(t) = (t, Then we get a time series g(t) = p(φ(t)) = cos(t) + cos( √ 3t). The sliding window embedding SWd,τ g(R) of g with appropriate dimension and delay re- covers the topology of T2. Rips persistent homology confirms that in Figure 2.7. Figure 2.7: Dynamical System to Persistence for an irrational flow on T2: In the leftmost figure, we see an irrational flow on T2. In the second, we see the time series generated g(t). In the third figure, we see a PCA visualization of the reconstructed torus from sliding window embedding. In the rightmost figure, we see the Rips persistence diagrams in dimensions 1, 2 of a sliding window point cloud sampled from the third figure. Before finishing this section, we want to mention a property that we will use later. The following was shown in [59]. Proposition 2.4.8. For all d ∈ N and τ > 0, the mapping SWd,τ : C(R, C) → C(R, Cd+1) is a bounded linear operator with norm || SWd,τ ||≤ √ d + 1. 45 2.5 Analytical tools In this section, we provide a brief review of Fourier series in 2.5.1, Kronecker’s approxi- mation theorem in 2.5.2, and Wasserstein metric on probability measures in 2.5.3. 2.5.1 Fourier Series Fourier series were introduced by Joseph Fourier in the 1800s for the purpose of solving the heat equation in a metal plate. Using the ideas that Fourier introduced, it was shown that every arbitrary real valued continuous periodic function can be approximated by a sum of sines and cosines. Since then Fourier series have had many applications in electrical engineering, acoustics, optics, signal & image processing, etc. Let us review: Let T be the quotient space R/(2πZ). For a single variable periodic function g ∈ L2 (T) and Z ∈ N0 = N∪{0}, its Fourier series and its Z-truncated Fourier polynomial are written as ∞X k=−∞ g(t) = respectively, where ZX k=−Z ˆg(k)eikt ˆg(k)eikt and SZ g(t) = ˆg(k) = 1 2π πZ −π g(t)e−iktdt are the Fourier coefficients of g and the series given by partial sums SZ g converges to g almost everywhere as Z → ∞. If additionally, g is continuously differentiable, then pointwise convergence is guaranteed by the following pipeline of results in analysis: Proposition 2.5.1. 1. If f ∈ C1([a, b]), then f, f0 are both continuous on [a, b] by defi- nition. Then f is Lipschitz. 2. If f is Lipschitz on [a, b], then f is uniformly continuous and has bounded variation, with the variation bounded by Lf(b − a) where Lf is the Lipschitz constant. 46 3. (Jordan’s Criterion) If f is a function of bounded variation in a neighbourhood of x, then Z→∞ SZ f(x) = 1 lim 2[f(x+) + f(x−)]. From this proposition, we can conclude that if g ∈ C1([a, b]), then SZ g(x) converges to g(x) for all x ∈ [a, b]. A proof of these propositions can be found in [29, Chapter 10]. 2.5.2 Kronecker’s theorems Recall that R can be viewed as an infinite dimensional vector space over Q with an uncount- able basis. A finite subset {β1, . . . , βN} ⊂ R of reals (vectors) is called incommensurate if β1, . . . , βN are linearly independent over Q, that is, r1β1 + ··· + rN βN = 0 ⇒ r1 = ··· = rN = 0 for r1, . . . , rN ∈ Q. The following theorem by Kronecker is a result about diophantine approximations applying to several real numbers. A proof can be found in [42, Chapter 2]. Theorem 2.5.2 (Kronecker’s theorem). Let {β1, . . . , βN} be a set of real numbers, r1, . . . , rN be arbitrary real numbers, and , L be arbitrary positive numbers, then one can find integers l and p1, . . . , pN with |βnl − rn − pn| <  for 1 ≤ n ≤ N where |l| ≥ L if and only if {β1, . . . , βN} is incommensurate. As a consequence, {β1, . . . , βN} is incommensurate over Q if and only if the collection {(zβ1, . . . , zβN) | z ∈ Z} of N-tuples is dense in TN = (R/(2πZ))N, which is equivalent to the collection {(eiβ1z, . . . , eiβN z)|z ∈ Z} being dense in TN = S1 × ··· × S1. In section 4.3, we will use Kronecker’s theorem to prove: Corollary 4.3.1: An α-tuple β = (β1, . . . , βα) of real numbers spans a N-dimensional vector space over Q if and only if the collection {zβ | z ∈ Z} is dense in an embedding of TN in 47 Tα. which in turn will be essential to proving the structure theorem: Theorem 4.3.5: The sliding window embedding SWd,τ SZ f(Z) is dense in a space homeo- morphic to TN in Td+1 for appropriate conditions on τ, d, and Z. 2.5.3 Wasserstein metric on probability measures In this section, we review the definition and relevant properties of the Wasserstein metric. We will use this metric to measure the noise on the landmark sets in Chapter 5, for which we prove the stability theorems. To begin, consider a compact metric space (M, d). Definition 2.5.3. A correspondence (or relation) between non-empty subsets A, B ⊂ M is a subset R ⊂ A × B such that • for all a ∈ A, there exists b ∈ B such that (a, b) ∈ R, and • for all b ∈ B, there exists a ∈ A such that (a, b) ∈ R. Denote by R(A, B) the set of all possible correspondences between A and B. Furthermore, define the Hausdorff distance as dH(A, B) = inf R∈R(A,B) sup (a,b)∈R d(a, b). Definition 2.5.4. Given A, B ⊂ M and measures µA, µB on M with Supp(µA) = A and Supp(µB) = B, a measure µ on A × B is a coupling of µA and µB if and only if µ(A0 × B) = µA(A0) ∀A0 ⊂ A measureable and µ(A × B0) = µB(B0) ∀B0 ⊂ B measureable. Denote by M(µA, µB), the collection of all couplings of µA and µB. Denote by R(µ) = B =n Supp(µ), the correspondence defined by the support of a coupling. For A = {ai} and o finite, we represent a coupling as a |A| × |B| matrix [µij] with µij = µ(ai, bj). bj 48 Definition 2.5.5. For p ≥ 1 or p = ∞, the following Z dW,p(µA, µB)p = d(a, b)pdµ(a, b) and, inf µ∈M(µA,µB) A×B dW,∞(µA, µB) = inf µ∈M(µA,µB) sup (a,b)∈R(µ) d(a, b) define the Wasserstein–Kantorovich–Rubinstein metrics between measures on M. Since the support of a coupling yields a relation, we have Lemma 2.5.6. Let A, B ⊂ (M, d) compact metric space and let µA and µB be measures on M. Then, dH(Supp(µA), Supp(µB)) ≤ dW,∞(µA, µB). Proof. See Corollary 2.1 [49]. 49 CHAPTER 3 PERSISTENT KÜNNETH THEOREMS In this chapter, we prove our two Künneth formulae in persistent homology. In section 3.1, we define two products of (diagrams of) spaces, namely the categorical product in Definition 3.1.1 and the generalized tensor product in Definition 3.1.13, study their properties, and give examples. In sections 3.2 and 3.3, we provide the proofs of our persistent Künneth formulae for the categorical and generalized tensor products, respectively. In section 3.4, as an application of the categorical Künneth formula for Rips complexes (Corollary 3.2.6), we revisit the theoretical results about the Rips persistent homology of the N-torus. Parts of this chapter appeared in [35]. 3.1 Products of Diagrams of Spaces Given a category S of spaces, such as Top, Simp, or Met, and a small indexing category I, the first objective is to identify relevant products between I-indexed diagrams X ,Y ∈ SI. For a particular product, the goal is to describe its persistent homology in terms of the persistent homology of X and Y. This is what we call a persistent Künneth formula. We begin with the first product construction: the categorical product in SI. Definition 3.1.1. Let S be a category having all pairwise products (e.g., finitely complete), let X ,Y ∈ SI, and let X × Y : I −→ S be the functor taking each object i ∈ I to the (categorical) product Xi × Yi ∈ S, and each morphism i → j in I to the unique morphism X × Y(i → j) making the following diagram commute: X (i→j)◦pX i Xj pX j Xi × Yi Xj × Yj Y(i→j)◦pY i Yj pY j (3.1) where pX i and pY j are canonical projections of Xi × Yj onto Xi and Yj respectively. The 50 existence of X × Y(i → j) follows from the universal property defining Xj × Yj. We have the following observation: Proposition 3.1.2. Let S be a category with all pairwise products. Then, X × Y ∈ SI is the categorical product of X ,Y ∈ SI. Proof. First, note that the existence of pX : X ×Y −→ X and pY : X ×Y −→ Y follows from : Xi × Yi −→ Yi for each i ∈ I, and the commutativity that of pX i of (3.1) for each i → j. : Xi × Yi −→ Xi and pY i Let Z ∈ SI, and let µ : Z → X , ν : Z → Y be morphisms. For each i ∈ I, let µi×νi : Zi → Xi×Yi be the unique morphism so that pX i ◦(µi×νi) = νi. It readily follows that µ × ν : Z −→ X × Y, given by (µ × ν)(i) = µi × νi, is the unique morphism of I-indexed diagrams such that pX ◦ (µ × ν) = µ, and pY ◦ (µ × ν) = ν. i ◦(µi×νi) = µi and pY Let us describe in more detail the categories we have in mind for S, as well as what the categorical products are in each case. Example 3.1.3 (Topological spaces). Recall that Top denotes the category of topological spaces and continuous maps. For X, Y ∈ Top, their Cartesian product equipped with the product topology is the categorical product of X and Y in Top. Example 3.1.4 (Metric Spaces). Let Met denote the category of metric spaces and non- expansive maps. That is, its objects are pairs (X, dX)—a set and a metric— and its mor- phisms are functions f : X −→ Y satisfying dY (f(x), f(x0)) ≤ dX(x, x0) for all x, x0 ∈ X. Definition 3.1.5. Given (X, dX), (Y, dY ) ∈ Met, let X × Y denote the Cartesian product of the underlying sets, and let dX×Y be the maximum metric on X × Y : (cid:16)(x, y), (x0, y0)(cid:17) := max{dX(x, x0), dY (y, y0)}. dX×Y Since the coordinate projections pX : X × Y −→ X and pY : X × Y −→ Y are non- expansive, it readily follows that (X × Y, dX×Y ) is the categorical product of (X, dX) and (Y, dY ) in Met. 51 Example 3.1.6 (Simplicial Complexes). Let Simp be the category of simplicial complexes and simplicial maps. Definition 3.1.7. For K, K0 ∈ Simp, let K × K0 be the smallest simplicial complex con- taining all Cartesian products σ × σ0, for σ ∈ K and σ0 ∈ K0. In other words, τ ∈ K × K0 if and only if there exist σ ∈ K and σ0 ∈ K0 with τ ⊂ σ × σ0. Let p : τ → σ and p0 : τ → σ0 be the projection maps onto the first and second coordinate, respectively. Since p(τ) ⊂ σ, then p(τ) ∈ K, and similarly p0(τ) ∈ K0. Hence p and p0 define p←− K × K0 p0−→ K0, and it readily follows that K × K0 is the categorical simplicial maps K product of K and K0 in Simp. The Rips complex at scale  ∈ R+ is a simplicial complex which can be associated to any metric space (X, dX). It is widely used in TDA—when (X, dX) is the observed data set—and it is defined as ( {x0, . . . , xn} ⊂ X : max 0≤i,j≤n ) dX(xi, xj) <  R(X) := . (3.2) Notice that any non-expansive function f : X → Y between metric spaces extends to a simplicial map R(f) : R(X) → R(Y ), and thus R defines a functor from Met to Simp. This functor is in fact compatible with the categorical products: Lemma 3.1.8. Let (X, dX), (Y, dY ) be metric spaces, and let  ∈ R+. Then, R(X × Y ) = R(X) × R(Y ). Proof. See the proof of Proposition 10.2 in [1]. One drawback of the categorical product in Simp is that it is not well-behaved with respect to geometric realizations. Indeed, recall that the geometric realization of a simplicial complex K—denoted |K|—is the collection of all functions ϕ : K(0) → [0, 1] so that {v ∈ K(0) : ϕ(v) 6= 0} ∈ K, and for which P ϕ(v) = 1. Moreover, if ϕ, ψ ∈ |K|, then v∈K(0) d|K|(ϕ, ψ) := X |ϕ(v) − ψ(v)| v∈K(0) 52 defines a metric on |K|. Every simplicial map f : K → L induces a function |f| : |K| → |L| given by ϕ(v) , |f|(ϕ)(w) = 0 if w /∈ f(K(0)) |f|(ϕ)(w) = X v∈K(0) f(v)=w which, as one can check, is non-expansive. In other words, geometric realization defines a functor | · | : Simp −→ Met. To see the incompatibility of | · | and the product in Simp, let K = L = {0, 1,{0, 1}}. It follows that |K × L| is (homeomorphic to) the geometric 3-simplex n(t0, . . . , t3) ∈ R4 : tj ≥ 0, t0 + ··· + t3 = 1o, while |K| × |L| is the unit square [0, 1] × [0, 1] ⊂ R2. Hence, |K × L| is in general not equal, nor homeomorphic to |K| × |L|. This leads one to consider other alternatives; specifically, the category of ordered simplicial complexes. Example 3.1.9 (Ordered Simplicial Complexes). If K(0) comes equipped with a partial or- der so that each simplex is totally ordered, then we say that K is an ordered simplicial com- plex. A simplicial map between ordered simplicial complexes is said to be order-preserving, if it is so between 0-simplices. Let oSimp denote the resulting category. For data analysis applications, and particularly for the Rips complex construction, oSimp is perhaps more relevant than Simp. Indeed, a data set (X, dX) stored in a computer comes with an explicit total order on X. If K, K0 ∈ oSimp, with partial orders (cid:22),(cid:22)0, respectively, and σ ∈ K, σ0 ∈ K0, then the Cartesian product σ×σ0 has a partial order (cid:22)× given by (v, v0) (cid:22)× (w, w0) if and only if v (cid:22) w and v0 (cid:22)0 w0. Definition 3.1.10. For K, K0 ∈ oSimp, let K (cid:11) K0 be defined as follows: τ ∈ K (cid:11) K0 if and only if there exist σ ∈ K and σ0 ∈ K0 so that τ is a totally ordered subset of σ × σ0, with respect to (cid:22)×. Just like for simplicial complexes, the coordinate projections p and p0 induce order- preserving simplicial maps p : K (cid:11) K0 → K and p0 : K (cid:11) K0 → K0. Moreover, Lemma 3.1.11. Let K and K0 be ordered simplicial complexes. Then, 53 1. K (cid:11) K0 is their categorical product in oSimp. 2. K (cid:11) K0 ⊂ K × K0, where the right hand side is the categorical product in Simp. Moreover, |K (cid:11) K0| is a deformation retract of |K × K0|. 3. The product map |p| × |p0| : |K (cid:11) K0| −→ |K| × |K0| is a homeomorphism. Proof. See [31], specifically Definitions 8.1, 8.8 and Lemmas 8.9, 8.11. The above are the categories of spaces and the products we will consider moving forward. Going back to diagrams in Top, recall that a CW-complex is a topological space X together with a CW-structure. That is, a filtration X = {X(k)}k∈N0 of X, so that X(0) has the discrete topology, X(k) is obtained from X(k−1) by attaching k-dimensional cells Dk ∼= α ⊂ X via continuous maps ϕα : ∂Dk → X(k−1), and so that the topology on X coincides ek with the weak topology induced by X . It follows that X ∈ FTop ⊂ TopN. In this context, (cid:16) a cellular map between CW-complexes—i.e. a continuous function f : X → Y so that X(k)(cid:17) ⊂ Y (k) for all k—is exactly a morphism in TopN. Thus, if CW denotes the f category of locally compact CW-complexes (we will see in a moment why this restriction) and cellular maps, then CW is a full subcategory of FTop. If X and Y are CW-complexes, then their topological product X × Y can also be written β with k = i + j, as a union of cells. Specifically, the k-cells of X × Y are the products ei for ei α an i-cell of X, and ej α × ej β a j-cell of Y . Thus, if (X × Y )(k) := [ i+j=k X(i) × Y (j) , k ∈ N0 (3.3) then n(X × Y )(k)o will be a CW-structure for X × Y provided the product topology coincides with the weak topology induced by (3.3). If either X or Y are locally compact, then this will be the case (see Theorem A.6 in [39]). k∈N0 In summary: the categorical product in TopN does not recover the usual product of CW-complexes, which suggests the existence of other useful (non-categorial) products in FTop and TopN. The product of CW-complexes suggests the following definition, 54 Definition 3.1.12. If X ,Y ∈ FTop, then their tensor product is the filtered space  . k∈N0  [ i+j=k X ⊗ Y := Xi × Yj The tensor product of filtered spaces is sometimes regarded in the literature as the de facto product filtration; see for instance [8, 11, 64] or [66, Chapter 27]. For general objects in TopN—e.g., when the internal maps are not inclusions—taking the union of, say, Xi+1 × Yj and Xi × Yj+1 does not make sense. Instead, the corresponding operation would be to glue these spaces along the images of the product maps Xi+1 × Yj ←− Xi × Yj −→ Xi × Yj+1. Here is where the machinery of homotopy colimits comes in as a means to defining a gener- alized tensor product in TopN: Definition 3.1.13. For k ∈ N0, let 4k be the poset category of {(i, j) ∈ N2 with its usual product order, and for X ,Y ∈ TopN, let 0 : i + j ≤ k} X (cid:2) Y : N2 −→ Top be the functor sending (i, j) to Xi × Yj, and (i, j) ≤ (s, t) to X (i ≤ s) × Y(j ≤ t). The generalized tensor product of X and Y is the object X ⊗g Y ∈ TopN given by X ⊗g Y(k) := hocolim(X (cid:2) Y|4k ) X (cid:2) Y|4k X ⊗g Y(k ≤ k0) := hocolim (cid:18) (cid:19) → X (cid:2) Y|4k0 (3.4) where the latter is the continuous map associated to the change of indexing categories induced by the inclusion 4k ⊂ 4k0. Remark 3.1.14. The definition of the generalized tensor product can be extended to diagrams indexed by other subcategories of R. For example, to the poset categories of R, R+ (the set of non negative reals) and R∗ (the set of positive reals). In general, for I = N, R, R+, or R∗, we let 4r = {(i, j) ∈ I2 : i + j ≤ r} and define X ⊗g Y : I −→ Top as in (3.4). 55 Although 4r and X (cid:2) Y are different for each choice of I, we will use the same notation for aesthetic purposes. The choice will be clear from the context as we will specify the I in TopI. We have the following relation between ⊗ and ⊗g, Lemma 3.1.15. Let X ,Y ∈ TopN, and let T (X ),T (Y) ∈ FTop be their telescope filtra- tions. Then, X ⊗g Y is naturally homotopy equivalent to T (X ) ⊗ T (Y). (cid:16)X ⊗g Y(cid:17) −→(cid:16)T (X ) ⊗ T (Y)(cid:17) Proof. We will show that there is a morphism X ⊗g Y −→ T (X ) ⊗ T (Y), so that each map , k ∈ N0, is a homotopy equivalence. Indeed, since Tj(X ) deformation retracts onto Xj, then each inclusion Xj ,→ Tj(X ) is a homotopy equivalence, and thus (by Theorem 2.2.9) so is the induced map k k (cid:16)X ⊗g Y(cid:17) = hocolim k (cid:19) (cid:18) X (cid:2) Y(cid:12)(cid:12)(cid:12)4k −→ hocolim (cid:18) T (X ) (cid:2) T (Y)(cid:12)(cid:12)(cid:12)4k (cid:19) . Since each inclusion Ti(X ) ,→ Tj(X ) is a closed cofibration (Remark 2.2.12), then the pro- jection Lemma 2.2.13 implies that the collapse map (cid:18) T (X ) (cid:2) T (Y)(cid:12)(cid:12)(cid:12)4k (cid:19) hocolim (cid:18) T (X ) (cid:2) T (Y)(cid:12)(cid:12)(cid:12)4k (cid:19) −→ colim is a homotopy equivalence. Moreover, since all the maps in T (X )(cid:2)T (Y) are inclusions, and the colimit of such a diagram is essentially the union of the spaces, then there is a natural homeomorphism (cid:18) T (X ) (cid:2) T (Y)(cid:12)(cid:12)(cid:12)4k (cid:19) ∼= [ i+j≤k colim Ti(X ) × Tj(Y) =(cid:16)T (X ) ⊗ T (Y)(cid:17) k which completes the proof. It follows that, Corollary 3.1.16. If X ,Y ∈ TopN, then P Hn(X ⊗g Y; F) ∼= P Hn graded F[t]-modules. (cid:16)T (X ) ⊗ T (Y); F) as 56 Later on—when studying the persistent singular chains of T (X )⊗T (Y)—it will be useful to have Proposition 3.1.17 below. The setup is as follows: observe that if X ∈ TopN and 0 <  < 1, then T  j (X ) := Xj × [j, j + ) t Xi × [i, i + 1] (x, i + 1) ∼ (fi(x), i + 1) G i 0. A matching between bcd(M) and bcd(N ) is called a δ-matching if the following conditions hold: 1. If I and J are matched, then max{|‘I − ‘J|,|ρI − ρJ|} ≤ δ. Recall that ‘I and ρI are, respectively, the left and right endpoints of the interval I. 2. If I is unmatched, then |‘I − ρI| ≤ 2δ. The bottleneck distance dB between bcd(M) and bcd(N ) is defined as: (cid:16)bcd(M), bcd(N )(cid:17) := infn δ | bcd(M) and bcd(N ) are δ-matched o dB 60 If no δ-matchings exist, then the bottleneck distance is ∞. The Isometry Theorem [7] implies that if M,N ∈ ModRF are pointwise finite, then dI(M,N ) = dB (bcd(M), bcd(N )) . The following corollary is a direct consequence of the above equality and Theorem 3.1.20. Corollary 3.1.21. Let X ,Y ∈ TopR∗ be so that X × Y and X ⊗g Y are pointwise finite. Then (cid:16)bcdn(X × Y), bcdn(X ⊗g Y)(cid:17)—which exists by [19, 1. If under a matching realizing dB Theorem 5.12]—we have that I is matched to J, then 1 2 ≤ ‘I ‘J , ρI ρJ ≤ 2. 2. If I is unmatched, then ρI ‘I ≤ 4. 3.2 A Persistent Künneth formula for the categorical product Let I be a small indexing category and let S be any of the categories of spaces from Section 3.1 (that is S = Top, Met, Simp, or oSimp). In this section, we relate the rank invariants of two objects in SI to that of their categorical product, and prove the persistent Künneth formula for the categorical product in SP, where P is the poset category of a separable totally ordered poset P. Remark 3.2.1. Recall that the topological Künneth formula (Corollary 2.2.5) holds for objects X, Y ∈ Top and singular homology. Every (X, dX) ∈ Met can be viewed as a topological space via the metric topology, and since the maximum metric induces the product topology, then the Künneth formula holds for Met. Let K, L ∈ oSimp, and let | · | : oSimp → Top be the geometric realization functor. From the homeomorphism |K (cid:11) L| → |K| × |L| and the natural isomorphism Hn(|K|; R) ∼= Hn(K; R) between singular and simplicial homology, the formula holds in oSimp. Using (2) of lemma 3.1.11, the formula also holds for Simp. 61 Let F be a field and let X and Y be objects in SI. Using the topological Künneth formula and the observation that Hn(Xr; F) and Hn(Yr; F) are vector spaces for each n ∈ N0, r ∈ I, we obtain isomorphisms M i+j=n Hi(Xr; F) ⊗F Hj(Yr; F) ∼=−−−→ Hn(Xr × Yr; F). Using naturality, this yields an isomorphism in ModIF between Hn(X ×Y; F) and Mn, where Mn(r) := M i+j=n Hi(Xr; F) ⊗F Hj(Yr; F) (3.7) and the homomorphism Mn(r → r0) is the sum of the ones induced between tensor products by the maps Xr → Xr0 and Yr → Yr0. In other words, and using the notation of tensor product and direct sum of objects in ModIF (see Definition 2.3.7), we obtain the following: Lemma 3.2.2. If X ,Y ∈ SI, then for every n ∈ N0 and every field F Hn(X × Y; F) ∼= M i+j=n Hi(X ; F) ⊗ Hj(Y; F) in ModIF. An immediate consequence is the following calculation at the level of rank invariants (see Definition 2.3.22): Proposition 3.2.3. Let X ,Y ∈ SI and let ρX , ρY be their rank invariants. Then (r → r0) = X ρX×Y n i+j=n i (r → r0) · ρY ρX j (r → r0) for every r → r0 in I, with the convention that ∞ · 0 = 0 = 0 · ∞. Proof. This follows by direct inspection of the homomorphism fr0,r ⊗F gr0,r : Hi(Xr; F) ⊗F Hj(Yr; F) −→ Hi(Xr0; F) ⊗F Hj(Yr0; F) a ⊗F b 7→ fr0,r(a) ⊗F gr0,r(b) 62 for each r → r0 ∈ I. Indeed, since Img(fr0,r ⊗F gr0,r) = Img(fr0,r) ⊗F Img(gr0,r), then the result follows from the fact that the dimension of the tensor product of two vector spaces equals the product of the dimensions. We are now ready to prove the main result of this section: the Künneth formula for the categorical product X × Y. Theorem 3.2.4. Let P be the poset category of a separable (with respect to the order topol- ogy) totally ordered set. Let X ,Y ∈ SP be P-indexed diagrams of spaces, and assume that Hi(X ; F) and Hj(Y; F) are pointwise finite for each 0 ≤ i, j ≤ n. Then Hn(X × Y; F) is pointwise finite, and its barcode satisfies: bcdn (X × Y; F) = [ i+j=n (cid:26) I ∩ J (cid:12)(cid:12)(cid:12)(cid:12) I ∈ bcdi(X ; F), J ∈ bcdj(Y; F) (cid:27) where the union on the right is of multisets (i.e., repetitions may occur). Proof. The fact that Hn(X × Y; F) is pointwise finite follows directly from Lemma 3.2.2. As for the barcode formula, and removing the field F from the notation, we have the following sequence of isomorphisms i+j=n Hn(X × Y) ∼= M ∼= M ∼= M ∼= M i+j=n i+j=n i+j=n  ⊗  M J∈bcdj(Y)  1J 1I Hi(X ) ⊗ Hj(Y)  M I∈bcdi(X ) M I∈bcdi(X ) J∈bcdj(Y) M I∈bcdi(X ) J∈bcdj(Y) 1I ⊗ 1J 1I∩J . The direct sum distributes with respect to the tensor product in ModPF since it does so in ModF. The last isomorphism is the one from Example 2.3.8, and the theorem follows from the uniqueness of the barcode. 63 This result generalizes to the product of k objects in SP by inductively using bcdj (Xk) and bcdi (X1 × ··· × Xk−1) to compute bcdi+j (X1 × ··· × Xk): Corollary 3.2.5. Let X1, . . . ,Xk ∈ SP. Assume that for each 1 ≤ j ≤ k, 0 ≤ nj ≤ n, Hnj(Xj) is pointwise finite. Then bcdn (X1 × ··· × Xk) = ( I1 ∩ ··· ∩ Ik (cid:12)(cid:12)(cid:12)(cid:12)(cid:12) Ij ∈ bcdnj(Xj), ) nj = n . kX j=1 The result which is perhaps most relevant to persistent homology computations with Rips complexes is as follows: Corollary 3.2.6. Let (X, dX), (Y, dY ) be finite metric spaces and let bcdR barcode of the Rips filtration R(X, dX) := {R(X, dX)}≥0. Then, n (X × Y, dX×Y ) = [ bcdR i+j=n (cid:26) I ∩ J (cid:12)(cid:12)(cid:12)(cid:12) I ∈ bcdR i (X, dX) , J ∈ bcdR (cid:27) j (Y, dY ) n (X, dX) be the for all n ∈ N0, if dX×Y is the maximum metric. Proof. Fix total orders on X and Y . Then, their -Rips complexes are ordered simplicial complexes, and by lemmas 3.1.8 and 3.1.11 we have that: |R(X × Y )| = |R(X) × R(Y )| ’ |R(X) (cid:11) R(Y )| ∼= |R(X)| × |R(Y )|. Since the equivalences commute with inclusions of Rips complexes, the result follows. 3.3 A Persistent Künneth Formula for the generalized tensor prod- uct In this section, we will establish the Künneth formula for the generalized tensor product X ⊗g Y of two objects X ,Y ∈ TopN. We start with a brief discussion on the grading of the tensor product and Tor of two graded modules over a graded ring R. The discussion then specializes to R = F[t] in order to establish the F[t]-isomorphisms (cid:17) ⊗F[t] (cid:16) P 1 I=[‘I ,ρI) P 1 J=[‘J ,ρJ ) (cid:16) (cid:16) TorF[t] P 1 I=[‘I ,ρI) , P 1 J=[‘J ,ρJ ) 64 (cid:17) ∼= P 1(‘J +I)∩(‘I+J) (cid:17) ∼= P 1(ρJ +I)∩(ρI+J) (3.8) for intervals I, J ⊂ N0. We end with a persistent Eilenberg-Zilber theorem, from which the aforementioned persistent Künneth theorem will follow. 3.3.1 The tensor product and Tor of graded modules Recall that a commutative ring R with unity is called graded if it can be written as R = R0 ⊕ R1 ⊕ ··· where each Ri is an additive subgroup of R and RiRj ⊂ Ri+j for every i, j ∈ N0. Similarly, an R-module A is graded if it can be written as A = A0 ⊕ A1 ⊕ ··· , where the Ai’s are subgroups of A and RiAj ⊂ Ai+j for all i, j ∈ N0. An element a ∈ A (resp. in R) is called homogeneous of degree i ∈ N0 if a ∈ Ai (resp. in Ri), and we will use the notation deg(a) = i. Let A, B be graded modules over a graded ring R. Our first goal is to describe a direct sum decomposition of the R-module A ⊗R B inducing the structure of a graded R-module. Indeed, since Ai and Bj are R0-modules for all i, j ∈ N0, then so are A, B and we have the R0-isomorphism A ⊗R0 B ∼= M  M k∈N0 i+j=k  . Ai ⊗R0 Bj Fix k ∈ N0 and let Jk be the R0-submodule of A ⊗R0 B generated by elements of the form (ra) ⊗ b − a ⊗ (rb), where a ∈ A, b ∈ B and r ∈ R are homogeneous elements with deg(a) + deg(r) + deg(b) = k. It follows that Jk is a submodule of (cid:16) (cid:17) k A ⊗R0 B := M i+j=k Ai ⊗R0 Bj and thus Jk ∩ J‘ = {0} if k 6= ‘. Let J = J0 ⊕ J1 ⊕ ··· . Any homogeneous element r ∈ R of degree ‘ induces a well-defined R0-homomorphism (A ⊗R0 B)k/Jk −→ (A ⊗R0 B)k+‘/Jk+‘ a ⊗ b + Jk 7→ (ra) ⊗ b + Jk+‘ = a ⊗ (rb) + Jk+‘ and therefore A ⊗R0 B/J ∼= M k∈N0 (A ⊗R0 B)k/Jk 65 (3.9) inherits the structure of a graded R-module. The inclusion R0 ,→ R induces an R0-epimorphism ι : A ⊗R0 B −→ A ⊗R B with ker(ι) = J. Indeed, the elements of J are exactly the relations missing between A ⊗R0 B and A ⊗R B when defining the latter as a quotient module. It follows that ι induces an isomorphism ι∗ : A ⊗R0 B/J −→ A ⊗R B of R-modules, and the grading on the codomain induced by (3.9) turns ι∗ into a graded isomorphism of graded R-modules. We summarize this analysis as follows: Proposition 3.3.1. Let A, B be graded modules over a graded ring R. Then A ⊗R B decomposes as the direct sum of the subgroups (cid:12)(cid:12)(cid:12)(cid:12) aα ∈ A, bα ∈ B homogeneous, deg(aα) + deg(bα) = k ) (A ⊗R B)k = aα ⊗ bα (X α and R‘ · (A ⊗R B)k ⊂ (A ⊗R B)k+‘ for all k, ‘ ∈ N0. In other words, A ⊗R B is a graded R-module. And now we prove the corresponding proposition for TorR(A, B): Proposition 3.3.2. If A, B are graded R-modules, then so is TorR(A, B). Proof. Fix a graded free resolution ··· → F2(A) → F1(A) → F0(A) → F−1(A) = A → 0 defined inductively as follows. Let F0(A) be the free R-module generated by the homoge- neous elements of A, and define for each i ∈ N0 the additive subgroup ) (cid:12)(cid:12)(cid:12)(cid:12) rα ∈ R, aα ∈ A homogeneous with deg(rα) + deg(aα) = i . F0,i(A) = rα · aα (X α Then F0(A) = F0,0(A) ⊕ F0,1(A) ⊕ ··· , and with this decomposition, the natural map F0(A) → F−1(A) is a surjective graded homomorphism of graded R-modules. In particular, the kernel of this homomorphism is a graded R-submodule of F0(A). We proceed inductively 66 by letting Fj+1(A) be the graded free R-module generated by the homogeneous elements in the kernel of Fj(A) → Fj−1(A). Taking the tensor product with B over R yields ··· → F2(A) ⊗R B → F1(A) ⊗R B → F0(A) ⊗R B → A ⊗R B → 0 and we note that: 1. Each Fj(A)⊗R B is a graded R-module, by Proposition 3.3.1, and each Fj(A)⊗R B → Fj−1(A) ⊗R B is a graded R-homomorphism. (cid:18) Fj(A) ⊗R B → Fj−1(A) ⊗R B 2. ker (cid:17) (cid:19) (cid:18)(cid:16)Fj(A) ⊗R B k ker M (cid:18) k∈N0 Fj+1(A) ⊗R B → Fj(A) ⊗R B M k∈N0 (cid:18)(cid:16)Fj+1(A) ⊗R B Img (cid:17) k decomposes as the direct sum →(cid:16)Fj−1(A) ⊗R B (cid:17) (cid:19) k (cid:19) →(cid:16)Fj(A) ⊗R B decomposes as (cid:17) (cid:19) k and similarly, Img with the image being a graded R-submodule of the kernel. 3. TorR(A, B) inherits the structure of a graded R-module from the decomposition TorR(A, B) ∼= M ker (cid:18)(cid:16)F1(A) ⊗R B (cid:17) (cid:18)(cid:16)F2(A) ⊗R B (cid:17) k k (cid:17) →(cid:16)F0(A) ⊗R B →(cid:16)F1(A) ⊗R B (cid:17) (cid:19) (cid:19) k k k∈N0 Img finishing the proof. We now specialize to the case R = F[t] and present explicit computations for interval modules. For m ∈ N0, k ∈ N0 ∪ {∞}, let Im,k denote the graded F[t]-module P 1[m,m+k). For brevity, we will drop the subscript k if it is ∞. That is, we will use Im to denote P 1[m,∞). Then, Im,k Proposition 3.3.3. Let m, n ∈ N0, k, l ∈ N0 ∪ {∞}. Then Im,k ⊗F[t] In,l and TorF[t](Im,k,In,l) ∼= Im+n+max{k,l},min{k,l}. ∼= tmF[t].(tm+k) and Im ∼= tmF[t]. ∼= Im+n,min{k,l} 67 Proof. There is a graded F[t]-isomorphism Im ⊗F[t] In → Im+n, which takes the generator tm ⊗F[t] tn to tm+n. Since Im,k and In,l are quotient modules of Im and In respectively, their tensor product is isomorphic to a quotient module of Im+n, say Im+n,q for some gives tp ·(cid:16) appropriate 1 ≤ q ≤ ∞. The isomorphism takes tm ⊗F[t] tn to tm+n and the action of tp or if tp+n is zero in In,l. This implies that if p ≥ min{k, l}, then tm+n+p is zero in Im+n,q. The minimum of all such p is min{k, l} and therefore, q = min{k, l}. To compute TorF[t] tm ⊗F[t] tn(cid:17) → tm+n+p. The left hand side is zero if either tp+m is zero in Im,k (cid:17), we fix a graded free resolution for Im,k: (cid:16)Im,k,In,l 0 → Im+k → Im → Im,k → 0. Taking the tensor product of the sequence with In,l gives us: Im+k ⊗F[t] In,l → Im ⊗F[t] In,l → Im,k ⊗F[t] In,l → 0. Using the definition of Tor and the tensor product of intervals, we get that TorF[t](Im,k,In,l) ∼= Ker Im+k ⊗F[t] In,l → Im ⊗F[t] In,l ∼= Ker Im+k+n,l → Im+n,l ∼= Im+n+max{k,l},min{k,l} (cid:18) (cid:18) (cid:19) (cid:19) where the last isomorphism is justified by the following argument: the element tm+p+n ∈ Im+k+n,l goes to tptm+n ∈ Im+n,l where p ≥ k. The latter is zero if and only if p ≥ l, or said equivalently p ≥ max{k, l}. This finishes the proof. Remark 3.3.4. This last proposition recovers the formulas shown in (3.8). Moreover, using bilinearity, these isomorphisms can be used to compute the tensor product and Tor of any pair of finitely generated graded F[t]-modules. 3.3.2 The Graded Algebraic Künneth Formula The Algebraic Künneth Formula for graded modules over a graded PID R is proved in exactly the same way as Theorem 2.2.3, by noticing that all the steps can be carried out in 68 a degree-preserving fashion. A few versions of this have appeared recently, see for instance [62, Proposition 2.9] or [12, Theorem 10.1], and we include it next for completeness: Theorem 3.3.5. Let C and C0 be two chain complexes of graded modules over a graded PID R, and assume that one of C, C0 is flat. Then, for each n ∈ N0, there is a natural short exact sequence 0 −→ M i+j=n Hi(C) ⊗R Hj(C0) µ−−→ Hn(C ⊗R C0) ν−−→ M TorR(Hi(C), Hj−1(C0)) −→ 0 which splits, though not naturally. i+j=n It is at this point that we depart from the existing literature on persistent Künneth formulas for the tensor product of filtered chain complexes. Indeed, next we will turn these algebraic results into theorems at the level of filtered topological spaces. We begin with the following result: Theorem 3.3.6. Let X ,Y ∈ TopN. Then, for all n ∈ N0, we have a natural short exact sequence 0 → M i+j=n P Hi(X ) ⊗F[t] P Hj(Y) → Hn (cid:16) P S∗(T (X )) ⊗F[t] P S∗(T (Y))(cid:17) → M P Hi(X ), P Hj−1(Y)(cid:17) → 0 TorF[t] (cid:16) i+j=n which splits, but not naturally. Proof. Since T (X ) and T (Y) are filtered spaces, then P S∗(T (X )) and P S∗(T (Y)) are chain complexes of free graded F[t]-modules, and hence flat. Now, each inclusion ιi : Xi ,→ Ti(X ) is a homotopy equivalence, and thus induces an isomorphism at the level of homology. One thing to note is that if i < j, then Ti(X ) ιi Tj(X ) ιj Xi X (i 0. Proof. If M =(cid:16)Σe∆p, Σf∆q(cid:17), then (cid:16)Σe∆p ⊗ Σf∆q(cid:17) ∼= P S∗(Σe+f∆p × ∆q) F (M) = P S∗ as chain complexes of graded F[t]-modules. Since ∆p × ∆q is convex, then Hn(F(M)) ∼= P Hn(Σe+f∆p × ∆q) = 0 for all n > 0, showing that M is F-acyclic. To show that M is E-acyclic, notice that P Hn (Σe∆p) = 0 for n > 0, and that P H0 (Σe∆p) ∼= teF[t] is a free graded F[t]-module. By the graded algebraic Künneth Theo- rem 3.3.5, with C = P S∗(Σe∆p) and C0 = P S∗(Σf∆q), we get that Hn(E(M)) = Hn(P S∗(Σe∆p) ⊗F[t] P S∗(Σf∆q)) = 0 for all n > 0, since the tensor products and Tor modules in the short exact sequence are all zero. Lemma 3.3.8. For each n ∈ N0, the functors Fn and En are free with base in M. Proof. Let n ∈ N0. The functor Fn (resp. En) being free with base in M means that for all (X ,Y) ∈ FTop0 × FTop0, the graded F[t]-module Fn(X ,Y) (resp. En(X ,Y)) is freely generated over F[t] by some subset of [ Img M∈M u:M→(X ,Y) (cid:18) (cid:19) Fn(u) : Fn(M) −→ Fn(X ,Y) where u ranges over all morphisms in FTop0 × FTop0 from M ∈ M to (X ,Y). 71 Starting with F, we will first construct a free F[t]-basis for Fn(X ,Y) = P Sn(X ⊗ Y) = M X Sn(Xi × Yj) k∈N0 i+j=k consisting of singular n-simplices on the spaces Xi × Yj. We proceed inductively as follows: Let S0 be the collection of all singular n-simplices ∆n → X0 × Y0, and assume that for a fixed k ≥ 1 and every 0 ≤ ‘ < k, we have constructed a set S‘ of simplices ∆n → Xp × Yq, p + q = ‘, so that Ak−1 = tk−1S0 ∪ tk−2S1 ∪ ··· ∪ tSk−2 ∪ Sk−1 is a basis, over F, for P Sn(X ⊗ Y)k−1 = X p+q=k−1 Sn(Xp × Xq). Since P Sn(X ⊗ Y) is an F[t]-submodule of P Sn(X ⊗ Y) and the latter is torsion free, then tAk−1 is an F-linearly independent subset of P Sn(X ⊗ Y)k. We claim that tAk−1 can be completed to an F-basis Ak of P Sn(X ⊗ Y)k, consisting of singular n-simplices ∆n → Xi × Yj, i + j = k. Indeed, if C is the collection of all sets C of simplices ∆n → Xi × Yj, i + j = k, so that C is F-linearly independent in P Sn(X ⊗ Y)k and tAk−1 ⊂ C, then C can be ordered by inclusion, and any chain in C is bounded above by its union. By Zorn’s lemma C has a maximal element Ak, which yields the desired basis. If we let Sk = Ak (cid:114) tAk−1, then S := [ k∈N0 Sk is a free F[t]-basis for P Sn(X ⊗ Y). morphism u : M → (X ,Y) in FTop2 some i, j ∈ N0, then there are unique singular simplices σX We claim that each σ ∈ S is in the image of Fn(u) for some model M ∈ M and some 0. Indeed, since σ is of the form σ : ∆n → Xi × Yj for (cid:17) ◦ d. Let : ∆n → Yj, : Σi∆n → X be the morphism in FTop0 defined as the inclusion ∅ ,→ X‘ for ‘ < i, so that if d : ∆n → ∆n × ∆n is the diagonal map d(a) = (a, a), then σ =(cid:16) : ∆n → Xi and σY σX i , σY j j i ΣσX i 72 fashion. Then, (cid:16)ΣσX and as the composition ∆n i , ΣσY j di,j ∈ Sn σX i−−→ Xi ,→ X‘ for ‘ ≥ i. Define ΣσY (cid:17) :(cid:16)Σi∆n, Σj∆n(cid:17) −→ (X ,Y) is a morphism in FTop2 (cid:16)(Σi∆n)i × (Σj∆n)j j : Σj∆n → Y in a similar 0, and if is the singular n-simplex corresponding to the diagonal map d, then (cid:17) = Sn(∆n × ∆n) (cid:17) (di,j) = σ. (cid:16)ΣσX Fn i , ΣσY j As for the freeness of En(X ,Y) = M p+q=n P Sp(X ) ⊗F[t] P Sq(Y), we note that each direct summand P Sp(X ) ⊗F[t] P Sq(Y) is freely generated over F[t] by elements which can be written as the tensor product of a homogeneous element from P Sp(X ) and a homogeneous element from P Sq(Y). That is, by elements of the form σX p ⊗F[t] σY q , p : Σe∆p → X p : ∆p → Xe and σY where σX q : Σf∆q −→ Y be defined as in the analysis of Fn above. Let ip ∈ P Sp(Σe∆p) and Σf σY be the homogeneous element of degree e corresponding to the identity of ∆p, and define iq ∈ P Sq(Σf∆q) in a similar fashion. Then, ip ⊗F[t] iq ∈ En(Σe∆p, Σf∆q) and q : ∆q → Yf are singular simplices. We let ΣeσX (cid:16)ΣeσX p , Σf σY q (cid:17) (ip ⊗F[t] iq), p ⊗F[t] σY σX q = En thus completing the proof. Lemma 3.3.9. The functors H0F and H0E are naturally equivalent. Proof. Given (X ,Y) ∈ FTop0 × FTop0, our goal is to define a natural isomorphism (cid:16) P S∗(X ) ⊗F[t] P S∗(Y)(cid:17) −→ H0 (cid:16) P S∗(X ⊗ Y)(cid:17) . Ψ : H0 The first thing to note is that the graded algebraic Künneth formula (Theorem 3.3.5) yields a natural isomorphism (cid:16) P S∗(X ) ⊗F[t] P S∗(Y)(cid:17) ∼= P H0(X ) ⊗F[t] P H0(Y). H0 73 Moreover, since each Xk−‘ × Y‘ is open in (X ⊗ Y)k, then the inclusion X i+j=k Sn(Xi × Yj) ,→ Sn((X ⊗ Y)k) is a chain homotopy equivalence (see [39, Proposition 2.21]), and thus (cid:16) P S∗(X ⊗ Y)(cid:17) ∼= P Hn(X ⊗ Y). Hn Therefore, it is enough to construct a natural isomorphism Ψ : P H0(X ) ⊗F[t] P H0(Y) −→ P H0(X ⊗ Y) and we will do so on each degree k as follows. Recall that (see Proposition 3.3.1) (cid:16) P H0(X ) ⊗F[t] P H0(Y)(cid:17) where Jk is the linear subspace of L k i+j=k  M i+j=k ∼= form (t‘a) ⊗F b − a ⊗F (t‘b) with deg(a) + deg(b) + ‘ = k. Let (cid:30) Jk H0(Xi) ⊗F H0(Yj) H0(Xi) ⊗F H0(Yj) generated by elements of the ψk : L i+j=k H0(Xi) ⊗F H0(Yj) −→ H0((X ⊗ Y)k) i ⊗F ΓY ΓX j 7→ Γ (resp. ΓY j ) is a path-connected component of Xi (resp. Yj), i+ j = k, and Γ is the where ΓX i unique path-connected component of (X ⊗ Y)k containing ΓX j . This definition on basis elements uniquely determines ψk as an F-linear map, and we claim that it is surjective with ker(ψk) = Jk. Surjectivity follows from observing that if (x, y) ∈ Γ, then (x, y) ∈ Xi × Yj for some i + j = k, and that if ΓX j are the path-connected components in Xi and Yj, respectively, so that (x, y) ∈ ΓX j and maximality of Γ imply ΓX j , then path-connectedness of ΓX i and ΓY i ×ΓY i ×ΓY i ×ΓY i × ΓY j ⊂ Γ. The inclusion Jk ⊂ ker(ψk) is immediate, since it holds true for elements of the form k−j ⊗F ΓY (cid:17), and these generate Jk over F. In order to show that (cid:16) t‘ΓX ker(ψk) ⊂ Jk, we will first establish the following: k−j ⊗F t‘ΓY j−‘ j−‘ − ΓX 74 i × ΓY Claim 1: If ΓX p + q = i + j = k, such that ψk (cid:16)ΓX j ⊂ Xi × Yj and ΓX i ⊗F ΓY (cid:16)ΓX i ⊗F ΓY j (cid:17) = ψk (cid:16)ΓX p ⊗F ΓY (cid:17) ∈ Jk. p ⊗F ΓY q q j − ΓX (cid:17), then p × ΓY q ⊂ Xp × Yq are path-connected components, p × ΓY Indeed, let γ : [0, 1] −→ (X ⊗ Y)k be a path with γ(0) ∈ ΓX q . Since each Xk−‘ × Y‘ is open in (X ⊗ Y)k, then the Lebesgue’s number lemma yields a partition 0 = r0 < r1 < ··· < rN = 1 such that γ ([rn, rn+1]) ⊂ Xin × Yjn and in + jn = k for all 0 ≤ n < N. Let (xn, yn) = γ (rn), and let ΓX jn be its path-connected component in Xin × Yjn. Since (i, j) = (i0, j0) and (p, q) = (iN , jN), then it is enough to show that j and γ(1) ∈ ΓX in ×ΓY i × ΓY (cid:16)ΓX in ⊗F ΓY (cid:17) ∈ Jk jn − ΓX in+1 ⊗F ΓY jn+1 for all n = 0, . . . , N − 1. Fix 0 ≤ n < N, assume that in ≤ in+1 , and let ‘ = in+1 − in = jn − jn+1 (the argument is similar if in ≥ in+1). Since the projection πX (γ ([rn, rn+1])) ⊂ Xin is a path in Xin from xn in+1 in H0(Xin+1). Similarly, the projection πY (γ ([rn, rn+1])) ⊂ to xn+1, then t‘ΓX Yjn is a path in Yjn from yn to yn+1, and since jn+1 ≤ jn, then t‘ΓY jn in H0(Yjn). This calculation shows that jn+1 = ΓY in = ΓX jn − ΓX i ⊗F ΓY (cid:16)ΓX in ⊗F ΓY and therefore (cid:16)ΓX Let us now show that ker(ψk) ⊂ Jk. To this end, let c ∈ ker(ψk) and write (cid:17) =(cid:16)ΓX jn+1 − t‘ΓX (cid:17) ∈ Jk. (end of Claim 1) jn+1 p ⊗F ΓY cn ·(cid:16)ΓX NX in+1 ⊗F ΓY j − ΓX in ⊗F t‘ΓY in ⊗F ΓY jn+1 c = (cid:17) q in ⊗F ΓY jn (cid:17) ∈ Jk n=1 where cn ∈ F, and where the indices (in, jn) have been ordered such that there are integers 0 = n0 < n1 < ··· < nD = N, and distinct path-connected components Γ1, . . . , ΓD of (X ⊗ Y)k so that if nd−1 < n ≤ nd, then ψk the Γd’s are linearly independent in H0((X ⊗ Y)k), then ψk(c) = 0 implies (cid:17) = Γd for all d = 1, . . . , D. Since (cid:16)ΓX in ⊗F ΓY jn nd−1X n=1+nd−1 cnd = −cn , d = 1, . . . , D 75 and therefore DX nd−1X d=1 n=1+nd−1 cn · c = (cid:18) in ⊗F ΓY ΓX jn − ΓX ind (cid:19) ⊗F ΓY jnd where each summand is an element of Jk, by Claim 1 above. Thus, ker(ψk) = Jk, ψk induces a natural F-isomorphism Ψk :(cid:16) P H0(X ) ⊗F[t] P H0(Y)(cid:17) −→ H0((X ⊗ Y)k) k and letting Ψ = Ψ0 ⊕ Ψ1 ⊕ ··· completes the proof. We now move onto the main results of this section. Lemma 3.3.10 (Persistent Eilenberg-Zilber). For objects X ,Y ∈ FTop0 and coefficients in a field F, there is a natural graded chain equivalence ζ : P S∗(X ) ⊗F[t] P S∗(Y) −→ P S∗(X ⊗ Y) with H0(ζ) = Ψ (Lemma 3.3.9), and unique up to a graded chain homotopy. Proof. The proof follows exactly that of Theorem 2.2.4 [32], using acyclic models [30] (see also the proof of Theorem 5.3 in [71] for a more direct comparison). Indeed, the functors in question are acyclic (Lemma 3.3.7), free (Lemma 3.3.8), and naturally equivalent at the level of zero-th homology (Lemma 3.3.9). Theorem 3.3.11. If X ,Y ∈ TopN, then there is a natural F[t]-isomorphism (cid:16) P S∗(T (X )) ⊗F[t] P S∗(T (Y))(cid:17) ∼= P Hn(X ⊗g Y). Hn Proof. Lemma 3.1.15 implies that P Hn(X ⊗g Y) ∼= P Hn(T (X ) ⊗ T (Y)), and Proposition 3.1.17 shows that if 0 <  < 1, then P Hn(T (X ) ⊗ T (Y)) ∼= P Hn(T (X ) ⊗ T (Y)). Moreover, since T (X ) ∈ FTop0, then the inclusion P S∗(T (X ) ⊗ T (Y)) ,→ P S∗(T (X ) ⊗ T (Y)) 76 is a graded chain homotopy equivalence (see [39, Proposition 2.21]), and thus Lemma 3.3.10 shows that P Hn(X ⊗g Y) ∼= Hn (cid:16) P S∗(T (X )) ⊗F[t] P S∗(T (Y))(cid:17) . The  can be removed since T  which completes the proof. k (X ) deformation retracts onto Tk(X ) (Proposition 3.1.17), Finally, we obtain Theorem 3.3.12. Let X ,Y ∈ TopN. Then there is a natural short exact sequence of graded F[t]-modules 0 → M (cid:16) i+j=n P Hi(X ; F) ⊗F[t] P Hj(Y; F)(cid:17) → P Hn (cid:16)X ⊗g Y(cid:17) → P Hi(X ; F), P Hj−1(Y; F)(cid:17) → 0 M TorF[t] (cid:16) which splits, though not naturally. i+j=n Remark 3.3.13. If S is either Top, Met, oSimp, or Simp, then following Remark 3.2.1 yields a similar Persistent Künneth theorem in each case. 3.3.4 Barcode Formulae We now give the barcode formula for the generalized tensor product of objects in SN. Recall from Theorem 2.3.10 that pointwise finite objects in ModNF can be uniquely decomposed into interval diagrams. In Proposition 3.3.3, the tensor product and Tor of the associated interval modules was computed, and the following is a consequence of Theorem 3.3.12. Theorem 3.3.14. Let X ,Y ∈ SN. Assume that for 0 ≤ i, j ≤ n, the diagrams Hi(X ) and 77 Hj(Y) are pointwise finite. Then Hn(X ⊗g Y) is pointwise finite with barcode ( bcdn(X ⊗g Y) = [ [ i+j=n i+j=n (‘J + I) ∩ (‘I + J) ( (ρJ + I) ∩ (ρI + J) ) (cid:12)(cid:12)(cid:12)(cid:12) I ∈ bcdi(X ), J ∈ bcdj(Y) [ ) (cid:12)(cid:12)(cid:12)(cid:12) I ∈ bcdi(X ), J ∈ bcdj−1(Y) . In the above formula, the first union of intervals is associated with the tensor part of the sequence in theorem 3.3.12, while the second union is associated with the Tor part. The results are easy to generalize to 0-th persistent homology in the case of finite tensor product of objects in Top. Corollary 3.3.15 (0-th persistent homology). Let X1, . . . ,Xp∈ SN, and assume that H0 (Xi) is pointwise finite for all i ∈ N0. Let bcd0(Xi) be the 0-dimensional barcode of Xi, then ) , Ii ∈ bcd0(Xi) (cid:16)X1 ⊗g ··· ⊗g Xp (cid:17) + Ii ( p\ (cid:17) = pX (cid:16)(cid:16) bcd0 . ‘ − ‘Ii (cid:17)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12) ‘ = ‘Ii i=1 In other words, a bar in X1 ⊗g ··· ⊗g Xp corresponding to p bars, one from each bcd0(Xi), starts at the sum of the starting points and lives as long as the shortest one. i=1 Topological inference deals with estimating the homology of a metric space X from a finite point cloud X, as discussed in Example 2.3.2. Usually, longer bars in a barcode represent significant topological features. The following corollary allows us to count the number of bars longer than a threshold  > 0 in the barcode of the tensor product. Corollary 3.3.16 (On high persistence). For n ≥ 0 and  > 0, let cX n (β ≥ ) denote the number of bars with length exactly β and at least  respectively in bcdn(X ). Assume that the lengths of longest bars in bcdn(X ) and bcdn(Y) are βX n respectively, then (cid:26) l−1} n and βY k , βY min{βX n (β) and cX min{βX X⊗gY n (cid:27)) = max ( (cid:26) (cid:27) β max k+l=n and cX⊗gY n (β ≥ ) = X k+l=n cY l (β ≥ )cX cY l (β ≥ )cX k (β ≥ ). (3.10) , max k+l=n k , βY l } k (β ≥ ) + X k+l=n−1 78 X⊗gY By replacing  with β n , the formula in equation 3.10 can be used to compute the number of bars with the longest length in bcdn (cid:16)X ⊗g Y(cid:17). 3.4 Application: Persistent Homology of N-torus The Rips persistence diagrams of a standard N-torus equipped with the maximum metric can be computed from the following two propositions 3.4.1 and 3.4.2. The first is a result by Adams and Adamaszek [1] that theoretically computes the homotopy type of the Rips complex of a circle S1, at each scale . In the original result, the circle was a equipped with the geodesic metric but we present a remetrized version with the Euclidean metric: Proposition 3.4.1 ([1]). The Vietoris-Rips complex R(S1 with Euclidean metric) is homotopy equivalent to S2l+1 if ! 2r sin l π 2l + 1 <  ≤ 2r sin l + 1 2l + 3 π ! . r) of a circle of radius r (equipped Recall the homology of an m-sphere, with coefficients in some field F, is F in dimensions i = 0, m and {0} otherwise. Now, Proposition 3.4.1 implies that for a circle of radius r, the Rips persistence diagrams in odd dimensions are singleton as multisets and empty in positive even dimensions: (cid:17) , 2r sin(cid:16) π l+1 2l+3 (cid:17)(cid:17)o π l 2l+1 (cid:16) S1 r (cid:17) = bcdR i  nh2r sin(cid:16) {[0,∞)} ∅ if i = 2l + 1 if i = 0 if i = 2l + 2 (3.11) for l ∈ N0. The second proposition is an extension of Corollary 3.2.6 to an N-fold product of metric spaces: Proposition 3.4.2. Let (X1, d1), . . . , (XN , dN) be finite metric spaces and let bcdR be the n-th dimensional persistence diagram of the Rips filtration R(X, dX) := {R(X, dX)}≥0. n (X, dX) 79 Then, bcdR n (X1 × ··· × XN , dmax) = (cid:26) N\ m=1 Im (cid:12)(cid:12)(cid:12)(cid:12) Im ∈ bcdR im(Xm, dm) (cid:27) [ NP m=1 im=n for all n ∈ N0, where dmax is the maximum metric. Consider the Vietoris-Rips complexes on the N-torus TN := S1 equipped with the maximum metric. Then by Propositions 3.4.1 and 3.4.2, we obtain the following theorem about the Rips persistence of a N-torus: r1 × ··· × S1 rN Theorem 3.4.3. Let TN := S1 be the N-torus equipped with the maximum metric dmax. Then for each homological dimension p, the Rips persistence barcode of TN can be computed as: r1 × ··· × S1 rN (cid:16)TN , dmax bcdR p (cid:17) = [ NP m=1 im=p  N\ m=1 (cid:12)(cid:12)(cid:12)(cid:12) Im ∈ bcdR im (cid:16) S1 rm Im (cid:17)  . More explicitly, √ o bcdR 1 in dimension 1, and 3rn] (cid:12)(cid:12)(cid:12)n = 1, . . . , N (cid:16)TN , dmax (cid:17) =n[0, 3 min{rn, rm}i (cid:12)(cid:12)(cid:12)(cid:12)(cid:12) n, m = 1, . . . , N (h0, in dimension 2. Let r = min{r1, . . . , rN}. Then, (cid:17) bars in bcdR Corollary 3.4.4. There are exactly (cid:16)N (cid:16)TN , dmax (cid:16)TN , dmax (cid:17) = bcdR 2 √ p p ) (cid:17) that are born at 0 and live longer than or of length atleast √ 3r. √ This is true because all the bars used in the persistent Künneth formula are either infinite, 3r, or shorter, depending on the dimension. 80 CHAPTER 4 QUASIPERIODICITY In this chapter, we develop the general theory of sliding window embeddings of quasiperi- odic functions and their persistent homology. We define quasiperiodic functions in a rigorous manner and study their properties in section 4.1 and write a Fourier-like decomposition in section 4.2. In section 4.3, we show that the sliding window embeddings of quasiperiodic functions, under appropriate choices of the embedding dimension d and time delay τ, are dense in higher dimensional tori. We also explicitly provide methods to choose these parame- ters. In section 4.4, we prove lower bounds on Rips persistent homology of these embeddings. The last section of this chapter is dedicated to computational results and an application to music. Parts of this chapter will appear in [36]. 4.0.1 Notation Let T = R/2πZ ’ S1, that is, [0, 2π] with the endpoints identified. Similarly for N ∈ N, let TN = (R/2πZ)N ’ S1 × ··· × S1. Let v = (v1,··· , vM) ∈ RM such that none of the coordinates vm are 0, then let Tv define , 2π ! v1 , 2π ! Z . vM Tv = R Z × ··· × R c denotes the circle of radius c, then for c = (c1, . . . , cN) ∈ CN where none of the cn are If S1 0, let TNc denote TNc := S1|c1| × ··· × S1|cN|. 4.1 Quasiperiodic functions In this section, we provide a general definition of a quasiperiodic function for a given incommensurate set of harmonics and give some examples. 81 Definition 4.1.1. Let f : R → C be a function and let ω = {ω1, . . . , ωN} ⊂ R \ {0} be an incommensurate set, that is, ω is linearly independent over Q. Then we call f a quasiperiodic function with the set of harmonics ω if there exists a function F : RN → C (t1, , . . . , tN) → F(t1, , . . . , tN) such that 1. F(t, . . . , t) = f(t) for all t ∈ R, 2. for all 1 ≤ n ≤ N, and ∀(cid:16) (cid:17) ∈ RN−1, the one variable function n+1, . . . , t∗ N)) t∗ 1, . . . , t∗ tn → F((t∗ n−1, t∗ 1, . . . , t∗ n+1, . . . , t∗ n−1, tn, t∗ N is periodic with time period 2π ωn , and 3. N is the lowest such integer. We will call F a parent function of f. The condition that N must be minimal is necessary. In its absence, f(t) = eiteiπt will have two parent functions: F(t1, t2) = eit1eiπt2 and G(t1) = ei(π+1)t1. The function f is clearly periodic with a single frequency π + 1. (cid:27) (cid:26)2π Remark 4.1.2. Note that every periodic function can be viewed as a quasiperiodic function. Indeed, if f is periodic with time period tf, then it is quasiperiodic with the set of harmonics ω = and the associated parent function F(t1) := f(t1). However, the incommensurate- ness of the harmonics implies that not all quasiperiodic functions are periodic. For example, f(t) = eit + eiπt is quasiperiodic with {1, π} and parent function F(t1, t2) = eit1 + eiπt2, but (cid:17) of the time periods of individual terms of f does not it is not periodic because lcm(cid:16)2π1 , 2π tf π exist. The following example demonstrates that for a quasiperiodic function f with a set of harmonics ω, its parent function may not be unique. 82 Example 4.1.3. The function f(t) = eit + eiπt is quasiperiodic with the set of harmonics {1, π}. Let F, G : R2 → C be defined as F(t1, t2) = eit1 + eiπt2 G(t1, t2) = eit2 + eiπt1. Clearly, f is the restriction to the diagonal of the functions F and G. Moreover, F(t1, t∗ 2) and G(t1, t∗ 2) are periodic in t1 with periods 2π and 2 respectively for all choices of t?2, and F(t∗ 1, t2) are periodic in t2 with periods 2 and 2π respectively for all choices of t∗ 1. Therefore, F and G are distinct parent functions of f. 1, t2) and G(t∗ In the next proposition, we show that for a continuous quasiperiodic f associated to a given set ω, its continuous parent function is unique up to a permutation of variables: Proposition 4.1.4. If f is a continuous quasiperiodic function with a set ω = {ω1, . . . , ωN}, then its continuous parent function is unique up to a permutation of variables. (cid:26)(cid:18) k1 2π ω1 + t, . . . , kN 2π ωN + t (cid:19)(cid:12)(cid:12)(cid:12)t ∈ R (cid:27) Proof. Let f : R → C be a quasiperiodic function with the incommensurate set {ω1, . . . , ωN} and let there be two continuous parent functions F, G : RN → C. After a permutation of variables, assume that the functions F and G are periodic with the same time period 2π in tn. ωn By definition, F and G agree on the diagonal 40 = {(t, . . . , t)|t ∈ R}. Therefore, they agree on the lines 4k = for each k = (k1, . . . , kN) ∈ ZN. We claim that the set of all 4k is dense in the set of all lines parallel to the diagonal. For an arbitrary (t1, . . . , tN) ∈ RN, consider the hyperplane V : t1 = t1. We will show that there is a line 4k intersecting V at a point arbitrarily close to (t1, . . . , tN). Any line 4k intersects V at a point which yields that t1 = t1 and for ω2 + t, . . . , kN 2 ≤ n ≤ N, tn = kn 2π ω1 . Without loss of generality, we can assume that t1 = 0. ωn We want to show that the set of the intersection points I is dense in V . We can rewrite tn = 2π ωn V . Then the intersection points satisfy s1 = t1 = t1 and sn = kn − k1 ωn (cid:17). Define sn = ωn2π tn for 2 ≤ n ≤ N. Call this rescaled hyperplane ω1 for 2 ≤ n ≤ N. (cid:18) t1, k2 2π + t1 − k1 2π kn − k1 ωn ω1 (cid:16) (cid:19) 2π ωN + t 83 ωN ω1 ω1 , . . . , o is incommensurate. Then by Kronecker’s theorem (theorem 2.5.2), Clearly, n ω2 for any arbitrary (t1, s2, . . . , sN) ∈ V , we can find an intersection point arbitrarily close to it. Therefore, we can find an intersection point arbitrarily close to (t1, . . . , tN). This proves our claim. Therefore, F and G agree on a dense subset of the set of lines parallel to the diagonal. By their continuity, they agree everywhere. Before we move on to writing a Fourier like series for a quasiperiodic function f, we want to mention that some functions can be quasiperiodic with different sets of harmonics: Example 4.1.5. Observe that the function f(t) = (cid:16) eit + 1(cid:17) eiπt is quasiperiodic with sets {1, π} and {1, π+1}: it is the restriction to the diagonal of two parent functions F, G : R2 → C defined as F(t1, t2) =(cid:16) eit1 + 1(cid:17) eiπt2 G(t1, t2) = ei(π+1)t1 + eiπt2. 2) and G(t1, t∗ F(t1, t∗ of t?2, and F(t∗ 2) are periodic in t1 with periods 2π and 2π π+1 respectively for all choices 1, t2) are both periodic in t2 with periods 2 for all choices of t∗ 1. 1, t2) and G(t∗ 4.2 “Fourier series” of a quasiperiodic function In this section, we adapt the theory of multivariate Fourier analysis to write a Fourier-like series for the function f. For a more comprehensive review, see [38, Chapter 3]. 4.2.1 The iterated Fourier series Let f : R → C be a quasiperiodic function with the incommensurate set {ω1, . . . , ωN} and parent function F : RN → C. Let ω denote the frequency vector (ω1, . . . , ωN) and recall the notation (section 4.0.1) for Tω: , 2π ! Z ω1 Tω = R , 2π ! Z . ωN × ··· × R 84 Furthermore assume that the parent function F belongs to C1(Tω). Recall that by definition of a quasiperiodic function, each marginal (cid:16) Fn(tn) := F t∗ 1, . . . , t∗ n−1, tn, t∗ n+1, . . . , t∗ N (cid:17) is a one variable periodic function in tn with the period 2π ωn . Lemma 4.2.1. If g : X → C is a continuously differentiable function on a finite measure space X ⊂ Rm, then it is square integrable on X. The next proposition shows that for each such F, all its marginal functions Fn are continuously differentiable. Proposition 4.2.2. Let TωN = R (cid:30)(cid:18) 2π ωN (cid:19) Z . If F ∈ C1 (Tω), then FN ∈ C1 (TωN ). Proof. Since F is continuously differentiable on Tω, all its partial derivatives exist and are continuous, which yields that FN is continuously differentiable with respect to tN. Therefore, FN ∈ C1 (TωN ). For each choice of (cid:16) t∗ 1, . . . , t∗ (cid:17) ∈ Tω1 × ··· × TωN−1, we obtain a Fourier series (cid:17) = X t∗ 1, . . . , t∗ t∗ 1, . . . , t∗ eikN ωN tN N−1, kN (cid:16) ˆF (cid:16) F N−1, tN N−1 (cid:17) kN∈Z where (cid:16) ˆF t∗ 1, . . . , t∗ N−1, kN (cid:17) = ωN 2π (cid:16) F 2π ωNZ 0 t∗ 1, . . . , t∗ N−1, tN (cid:17) e−ikN ωN tN dtN are its Fourier coefficients. By proposition 2.5.1, the series converges pointwise to FN. The next proposition shows that the coefficient functions ˆF (t1, . . . , tN−1, kN) for each choice of kN ∈ Z are square integrable on Tω1 × ··· × TωN−1. Proposition 4.2.3. If F ∈ C1 (Tω), then for all kN ∈ Z, the N − 1 variable coefficient functions ˆF(t1, . . . , tN−1, kN) ∈ L2(cid:16)Tω1 × ··· × TωN−1(cid:17). 85 Proof. The proof follows directly from the definition: Z Z Tω1×···×TωN−1 = Tω1×···×TωN−1 Z ≤ ωN 2π (cid:12)(cid:12)(cid:12) ˆF(t1, . . . , tN−1, kN)(cid:12)(cid:12)(cid:12)2 (cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12) ωNZ ωN 2π 2π 0 2π ωNZ dtN−1 ··· dt1 F(t1, . . . , tN)e−ikN ωN tN dtN 2 (cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12) dtN−1 ··· dt1 |F(t1, . . . , tN)|2 dtN dtN−1 ··· dt1 < ∞ Tω1×···×TωN−1 0 where the last term is finite because F ∈ C1(Tω) and Lemma 4.2.1. Now observe that for each (t∗ one variable function defined by 1, . . . , t∗ N−2) ∈ Tω1 × ··· × TωN−2 and each kN ∈ Z, the ˆF(t∗ 1, . . . , t∗ N−2.tN−1, kN) = ωN 2π 2π ωNZ 0 F(t∗ 1, . . . , t∗ N−2, tN−1, tN)e−ikN ωN tN dtN is periodic in tN−1 with period Proposition 4.2.4. For each (t∗ function ˆF(t∗ 1, . . . , t∗ 2π . ωN−1 1, . . . , t∗ N−2, tN−1, kN) ∈ L2(cid:16)TωN−1(cid:17) ∩ C1(cid:16)TωN−1(cid:17). N−2) ∈ Tω1 × ··· × TωN−2 and each kN ∈ Z, the Proof. Similar to the proof of proposition 4.2.2. N−2, tN−1, kN) as a Fourier series which converges ˆF(t?1, . . . , t? N−2, kN−1, kN)eikN−1ωN−1tN−1 Therefore, we can write ˆF(t∗ 1, . . . , t∗ N−2, tN−1, kN) = X kN−1∈Z pointwise to it: ˆF(t?1, . . . , t? which is now equal the following double sum: X kN∈Z X kN−1∈Z ˆF(t?1, . . . , t? N−2, kN−1, kN)eikN−1ωN−1tN−1eikN ωN tN , 86 where ˆF(t∗ ωN−1ωN (2π)2 1, . . . , t∗ ωN−1Z 2π N−2.kN−1, kN) is given by ωNZ e−ikN−1ωN−1tN−1 2π 0 0 F(t∗ 1, . . . , t∗ N−2, tN−1, tN)e−ikN ωN tN dtN dtN−1. Similar to Proposition 4.2.3, we can show that if ˆF(t1, . . . , tN−1, kN) ∈ L2(Tω1 × ··· × TωN−1), then ˆF(t1, . . . , tN−2, kN−1, kN) ∈ L2(Tω1 × ··· × TωN−2) for all pairs (kN−1, kN) ∈ Z2: dtN−2 ··· dt1 Z Z (cid:12)(cid:12)(cid:12) ˆF(t1, . . . , tN−2, kN−1, kN)(cid:12)(cid:12)(cid:12)2 (cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12) ωN−1Z ωN−1 2π 2π 0 2π ωN−1Z (cid:12)(cid:12)(cid:12) ˆF(t1, . . . , tN−1, kN)(cid:12)(cid:12)(cid:12)2 0 Tω1×···×TωN−2 = Tω1×···×TωN−2 Z Z ≤ ωN−1 2π ≤ ωN−1 2π Tω1×···×TωN−2 Tω1×···×TωN−1 ˆF(t1, . . . , tN−1, kN)e−ikN−1ωN−1tN−1dtN−1 (cid:12)(cid:12)(cid:12) ˆF(t1, . . . , tN−1, kN)(cid:12)(cid:12)(cid:12)2 dtN−1 ··· dt1 dtN−1 ··· dt1 < ∞. (cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12) 2 dtN−2 ··· dt1 Repeating the above arguments, we obtain that for all (kn+1, . . . , kN) ∈ ZN−n, the inter- mediate ˆF(t1, . . . , tn, kn+1, . . . , kN) will be in L2(Tω1 × ··· × Tωn) if F ∈ L2(Tω). Using induction, we obtain F(t1, . . . , tN) = X ··· X k1∈Z kN∈Z ˆF(k1, . . . , kN)ei(k1ω1t1+···+kN ωN tN ) (4.1) where the convergence of series to F is pointwise because all intermediate ˆF’s are continu- ously differentiable. Note that for k = (k1, . . . , kN) ∈ ZN, the coefficients ˆF(k) are given by: ˆF(k) = e−ik1ω1t1 F(t1, . . . , tN)e−ikN ωN tN dtN . . . dt1. NQ ωn n=1 (2π)N Z 2π ω1 0 Z 2π ω2 0 Z 2π ωN 0 ··· 87 To be able to rearrange the terms of the series in equation 4.1, we need it to be absolutely convergent. To prove this, we investigate the coefficients ˆF(k) in the next section. We finish this section with a remark about the periodicity of the partial derivatives of the parent function which will be useful in proof of Theorem 4.2.6. Remark 4.2.5. Let f be a quasiperiodic function and let F : RN → C be its parent function. Suppose for some 1 ≤ n ≤ N and r ∈ N, the r-th partial derivative ∂r will be periodic in tn with the same period 2π ωn it will be periodic in tm with 2π ωm nF exists, then ∂r nF nF is dependent on tm, then . If for m 6= n, ∂r . Z = nk = (k1, . . . , kN) ∈ ZN(cid:12)(cid:12)(cid:12) ∀n , |kn| ≤ Z 4.2.2 Analyzing the coefficients ˆF(k) o denote the box of lengths For Z ∈ N0, let IN 2Z centered around (0, . . . , 0) ∈ ZN. Moreover, let k (cid:12) ω = (k1ω1, . . . , kN ωN) denote the Hadamard product of two vectors k and ω. The next theorem provides bounds on each coefficient ˆF(k) in terms of its corresponding coefficient in the series decomposition of a certain partial derivative. Furthermore, it concludes that the sequence of coefficients is absolutely convergent. Theorem 4.2.6. Let r ∈ N and k, l ∈ ZN. Suppose that ∂lF exist and are integrable for all ||l||1 ≤ r. Then √ N ||k (cid:12) ω||r2 where n satisfies |knωn| = ||k (cid:12) ω||∞ and d∂r (cid:12)(cid:12)(cid:12) ˆF(k)(cid:12)(cid:12)(cid:12) ≤ r nF(k)(cid:12)(cid:12)(cid:12) (cid:12)(cid:12)(cid:12) d∂r nF is the r-th (partial) derivative of F with respect to tn. As a consequence, the sequence of coefficients is absolutely convergent: (cid:12)(cid:12)(cid:12) ˆF(k)(cid:12)(cid:12)(cid:12) < ∞. X k∈ZN 88 Proof. Fix k ∈ ZN \ {0} and let n be the coordinate such that |knωn |= ||k (cid:12) ω||∞. Then kn 6= 0. Recall that NQ 2π 2π ω1Z ω2Z 2π ωNZ F(t1, . . . , tN)e−ikN ωN tN dtN . . . dt1. ˆF(k) = ωn n=1 (2π)N e−ik1ω1t1 ··· 0 0 0 Using Fubini’s theorem, we can change the order so that the integral with respect to tn is the inner most and looks like 2π ωnZ 0 F(t1, . . . , tN)e−iknωntndtn Integrating by parts with respect to tn yields 2π ωnZ 0 F e−iknωntndtn = " e−iknωntn −iknωn # 2π ωn 0 F − 2π ωnZ 0 e−iknωntn −iknωn ∂nF dtn where the first term on the right hand side vanishes. The second term can be further integrated using by parts to obtain and the first term vanishes again. After a total of r such iterations, we obtain " e−iknωntn (−iknωn)2 ∂nF # 2π ωn 0 + e−iknωntn (−iknωn)2 ∂2 nF dtn F e−iknωntndtn = (−1)r e−iknωntn (−iknωn)r ∂r nF dtn − 2π ωnZ 0 2π ωnZ 0 2π ωnZ 0 2π ωNZ 0 2π ω2Z 0 ··· which gives us upon rearrangement 1 NQ (iknωn)r d∂r ωn n=1 (2π)N 1 (iknωn)r nF(k) 2π ω1Z 0 ˆF(k) = = e−ik1ω1t1 nF(t1, . . . , tN)e−ikN ωN tN dtN . . . dt1 ∂r where the last step results from remark 4.2.5. Using the fact that ||k(cid:12)ω||2 ≤ √ √ N | knωn |, we obtain N||k(cid:12)ω||∞ = (4.2) (cid:12)(cid:12)(cid:12) ˆF(k)(cid:12)(cid:12)(cid:12) ≤ r √ ||k (cid:12) ω||r2 N (cid:12)(cid:12)(cid:12) d∂r nF(k)(cid:12)(cid:12)(cid:12) , 89 which proves the first part of the theorem. Now, we will show that (cid:12)(cid:12)(cid:12) ˆF(k)(cid:12)(cid:12)(cid:12) < ∞, X k∈ZN By equation 4.2, we obtain X k /∈IN Z (cid:12)(cid:12)(cid:12) ˆF(k)(cid:12)(cid:12)(cid:12) ≤ X k /∈IN Z r √ ||k (cid:12) ω||r2 N | d∂r nF(k)| Note that n depends on k and can be written as n(k). Using Cauchy-Schwarz theorem and Parseval’s identity, the right hand term can be bounded: X k /∈IN Z r √ |k (cid:12) ω|r| (cid:92)∂r N n(k)F(k)| ≤ √ r N  X k /∈IN Z  1/2 X k /∈IN Z 1 ||k (cid:12) ω||2r2  1/2 . | (cid:92)∂r n(k)F(k)|2 nF is continuous, so it is square integrable and the coefficients are However, for each n, ∂r square summable: k∈ZN Hence, we can rearrange terms and get  1/2 ≤ | (cid:92)∂r n(k)F(k)|2  X k /∈IN Z X  X k /∈IN Z | d∂r nF(k)|2 < ∞. (4.3) NX n=1 | d∂r nF(k)|2 1/2   NX n=1 = X k /∈IN Z 1/2  | d∂r nF(k)|2 where the last term is finite because of equation 4.3. Before proceeding further, we denote by J N Z , the box by BN Z , the ball around 0 = (0, . . . , 0) ∈ RN, and by EN , nx = (x1, . . . , xN) ∈ RN (cid:12)(cid:12)(cid:12) ||x||∞ ≤ Z o nx = (x1, . . . , xN) ∈ RN (cid:12)(cid:12)(cid:12) ||x||2 ≤ Z o !1/2 Z , the ellipsoid-ball + ··· + y2 N ω2 N y = (y1, . . . , yN) ∈ RN y2 1 ω2 1 (cid:12)(cid:12)(cid:12)(cid:12)(cid:12) ,  ≤ Z 90 that we obtain upon a change of variables ωnxn = yn for each n. Observe that 1/2  X k /∈IN Z 1/2  1 ||k (cid:12) ω||2r2 (cid:17)r dx1dx2 . . . dxN (cid:17)r dx1dx2 . . . dxN   (cid:17)r dy1dy2 . . . dyN 1/2 1/2  . 1 + ··· + x2 N ω2 N (cid:16) x2 1ω2 (cid:16) 1 1 N 1 + ··· + x2 N ω2 1ω2 x2 (cid:16) !1/2  Z y /∈EN Z 1 |ωn| 1 1 + ··· + y2 y2 N ≤ ≤ = x /∈JN Z x /∈BN Z Z Z   NQ  n=1 Z Now, let Zm := Zωmin = Z min{ω1, . . . , ωN}. Then the above is bounded by 1/2 !1/2 NQ n=1 1 |ωn| y /∈BN Zm (cid:16) 1 1 + ··· + y2 y2 N (cid:17)r dy1dy2 . . . dyN ,  which in higher dimensional spherical coordinates can be written as Z σ ∞Z Zm 1/2 1 (ρ)2r ρdρdσ NQ n=1 !1/2 1 |ωn| where dσ is the differential surface area of unit sphere SN−1 and ρ is the distance of a point from the center. Evaluating the integrals yields 1/2 1/2 1 (ρ)2r−1 dρ Zm  ∞Z Area(SN−1)(cid:17)1/2  ρ2−2r Area(SN−1)(cid:17)1/2 Area(SN−1)(cid:17)1/2 Z1−r 2 − 2r (cid:16) (cid:16) (cid:16) m√ 2r − 2. (cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12) ∞ Zm n=1 NQ NQ NQ n=1 n=1 !1/2 1 |ωi| !1/2 1 |ωi| !1/2 1 |ωi| = = 91 Summarizing, we obtain √ (cid:12)(cid:12)(cid:12) ˆF(k)(cid:12)(cid:12)(cid:12) ≤ X k /∈IN Z Area(SN−1)(cid:17)1/2 r(cid:16) !1/2 N √ ωr−1 2r − 2 min NQ |ωn| n=1  NX n=1 X k /∈IN Z 1/2  1 Zr−1 | d∂r nF(k)|2 (4.4) where the right hand side is finite if Z > 0 and r ∈ N. Since IN we obtain that Z has finitely many terms, (cid:12)(cid:12)(cid:12) ˆF(k)(cid:12)(cid:12)(cid:12) < ∞. X k∈ZN (4.5) Therefore, due to the absolute convergence of the coefficients, equation 4.1 can be rewrit- ten as: F(t1, . . . , tN) = X k∈ZN ˆF(k)ei(k1ω1t1+···+kN ωN tN ), where k = (k1, . . . , kN) ∈ ZN. Along the diagonal, we get an iterated Fourier series for the quasiperiodic function f: f(t) = F(t, . . . , t) = X k∈ZN it ˆF(k)e knωn = X k∈ZN ˆF(k)eithk,ωi (4.6) NP n=1 where ω = (ω1, . . . , ωN) ∈ RN and h·,·i is the inner product (dot product) on RN. Moreover, the series in equation 4.6 converges everywhere. Next, we move to sliding window embedding of the function f. 92 4.2.3 Approximation theorems for sliding window embeddings From Definition 2.4.4 and Equation 4.6, the sliding window embedding of a quasiperiodic function f at t with parameters d and τ is:  P P k∈ZN ˆF(k)eihk,ωit ˆF(k)eihk,ωi(t+τ) P ... ˆF(k)eihk,ωi(t+dτ) k∈ZN  = X k∈ZN ˆF(k)eihk,ωituk   f(t) f(t + τ) ... f(t + dτ) SWd,τ f(t) = = k∈ZN where uk is the vector uk =  1 eihk,ωi(τ) ... eihk,ωi(dτ)  . Remark 4.2.7. We make a few observations. 1. uk = SWd,τ eithk,ωi |t=0. 2. If k = l, then huk, uli = d + 1. 3. hk, ωi = 0 if and only if k1 = ··· = kN = 0 4. hk, ωi = hl, ωi if and only if k = l. For Z ∈ N0, we define the polynomial SZ f by truncating the series: SZ f(t) := X k∈IN Z ˆF(k)eihk,ωit, where IN Z is the box Z =nk ∈ ZN (cid:12)(cid:12)(cid:12) ||k||∞ ≤ Z IN o . 93 Then SZ f(t) converges to f(t) for each t ∈ R as Z → ∞. Since SWd,τ is a bounded linear operator (and hence, continuous) by Proposition 2.4.8, SWd,τ SZ f converges to SWd,τ f pointwise as well. Let RZ f(t) := f(t) − SZ f(t) = X ˆF(k)eihk,ωit k /∈IN Z be the remainder term of polynomial SZ f(t). Then the following result shows that the bound on the sliding window embedding of the remainder term RZ f is controlled by the regularity of the function f. In particular, the more differentiable f is, the faster is the rate of convergence. Theorem 4.2.8. Let r ∈ N \ {1}. If F ∈ Cr(cid:16)RN , C(cid:17), then for all t ∈ R 1/2 √ ||RZ(∂r nF)||2 ≤ d + 1 Zr−1 .  1/2 X k /∈IN Z 1/2 | d∂r nF(k)|2 1 Zr−1 ||RZ(∂r nF)||2 2 1 Zr−1  NX n=1 1/2 √ d + 1 Zr−1 . ||RZ(∂r nF)||2 2 Proof. We begin with the remainder term RZ f: |RZ f(t)| = n=1 (cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12) n=1 |ωn| X NQ r(cid:16) √ N √ ωr−1 2r − 2 min (cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)SWd,τ f(t) − SWd,τ SZ f(t)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)2 Area(SN−1)(cid:17)1/2  NX !1/2 (cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12) ≤ X ˆF(k)eihk,ωit Area(SN−1)(cid:17)1/2 r(cid:16) !1/2 N √ ωr−1 2r − 2 Area(SN−1)(cid:17)1/2 r(cid:16) min √ !1/2 N √ ωr−1 2r − 2 min k /∈IN Z √ k /∈IN Z |ωn| |ωn| n=1 = ≤ NQ NQ (cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)SWd,τ f(t) − SWd,τ SZ f(t)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)2 r(cid:16) √ ≤√ N √ ωr−1 2r − 2 min d + 1||RZ f||∞ ≤ n=1 Area(SN−1)(cid:17)1/2 !1/2 NQ |ωn| n=1 (cid:12)(cid:12)(cid:12) ˆF(k)(cid:12)(cid:12)(cid:12)  NX  NX n=1 n=1 94 where the second inequality comes from Equation 4.4. Therefore, Corollary 4.2.9. If X = SWd,τ f(T) and Y = SWd,τ SZ f(T) for T ⊂ R, then dB (cid:16)bcdR Area(SN−1)(cid:17)1/2 !1/2 NQ n=1 |ωn| √ r(cid:16) N √ ωr−1 2r − 2 min for ξ = i (X), bcdR i (Y )(cid:17) ≤ 2ξ  NX ||RZ(∂r n=1 1/2 √ d + 1 Zr−1 nF)||2 2 Proof. Let  > ξ, then by theorem 4.2.8, Y ⊂ X and X ⊂ Y  and therefore dH(X, Y ) ≤ . Since this is true for every  > ξ, this gives us dH(X, Y ) ≤ ξ, which from the stability theorem [19] gives us (cid:16)bcdR dB i (Y )(cid:17) ≤ 2ξ. i (X), bcdR Corollary 4.2.9 implies that the Rips persistent homology barcodes bcdR i (SWd,τ SZ f) converge to bcdR i (SWd,τ f) as Z → ∞. This suggests that one could replace the study of a quasiperiodic function f with that of its approximation SZ f. Accordingly, we study the geometric structure of the sliding window embedding of the truncated polynomial SZ f next. 4.3 The geometric structure of SWd,τ SZf We dedicate this section to showing that under appropriate conditions on d, τ, and Z, the closure of the sliding window embedding of the truncated polynomial SZ f, is homeomorphic to the N-dimensional torus. To begin, let α be the cardinality of support of the coefficient function ˆF : IN Z → C k → ˆF(k) 95 o. Observe that 0 ≤ α ≤ (2Z + 1)N. Choose Z , say k1,··· , kα. Let xZ,f(t) be a α × 1 vector where IN an enumeration of points k ∈ Supp( ˆF) ⊂ IN given by Z is the box nk ∈ ZN (cid:12)(cid:12)(cid:12) ||k||∞ ≤ Z  xZ,f(t) =  . ˆF(k1)eihk1,ωit ... ˆF(kα)eihkα,ωit. Next, we present a corollary to Theorem 2.5.2 that we will utilize to prove the main result (Theorem 4.3.5) of this section. Corollary 4.3.1 (a corollary to Kronecker’s theorem). An α-tuple β = (β1, . . . , βα) of real numbers spans a N-dimensional vector space over Q if and only if the collection {zβ | z ∈ Z} is dense in an embedding of TN in Tα, which is equivalent to n(eiβ1z,··· , eβαz)(cid:12)(cid:12)(cid:12) z ∈ Zo being dense in the image of a homeomorphism from TN to Tα. Proof. Let {β1, . . . , βα} span a N dimensional vector space over Q. Without loss of gen- erality, let us assume that the β1, . . . , βN form a basis of said vector space. Then for N + 1 ≤ j ≤ α, βj depends linearly on β1, . . . , βN, i.e. for appropriate coefficients cj,n ∈ Q, we have We want to show that {zβ | z ∈ Z} is dense in a space homeomorphic to TN = (R/2πZ)N in Tα = (R/2πZ)α. It is equivalent to showing that NX n=1 βj = cj,nβn. n(eiβ1z,··· , eiβαz)(cid:12)(cid:12)(cid:12) z ∈ Zo is dense in a space homeomorphic to TN in Tα. Observe that βj = if and only if NX n=1 cj,nβn eiβj t = (eiβ1t)cj,1 ··· (eiβN t)cj,N . 96 Define a map φ from TN → Tα by φ(z1, . . . , zN) = (z1, . . . , zN , ˜zN+1, . . . , ˜zα), (4.7) cj,1 where ˜zj = z 1 cj,2 z 2 ··· z cj,N N . Observe that the set n(eiβ1z,··· , eiβαz)(cid:12)(cid:12)(cid:12) z ∈ Zo ⊂ φ(TN) ⊆ Tα. By definition, φ is injective, continuous, and it is vacuously surjective onto its own image. The inverse from the image φ(TN) to TN is just the projection map and that is continuous. Therefore, φ is a homeomorphism. In particular, it is continuous and surjective (onto φ(TN)) and since the set is dense in TN by Theorem 2.5.2, its image under φ, n(eiβ1z,··· , eiβN z)(cid:12)(cid:12)(cid:12) z ∈ Zo n(eiβ1z,··· , eβαz)(cid:12)(cid:12)(cid:12) z ∈ Zo is dense in φ(TN). This proves the ‘if’ part of our claim. For the other direction, let {zβ | z ∈ Z} be dense in φ(TN) ⊂ Tα for some homeo- morphism φ and let (β1, . . . , βα) span an L-dimensional vector space for L 6= N. From the first part of the proof, we obtain that {zβ | z ∈ Z} is dense in ϕ(TL) ⊂ Tα for some homeomorphism ϕ. Therefore, (cid:16)TL(cid:17) = {zβ | z ∈ Z} = φ(TN) ϕ and since homeomorphism is an equivalence relation, we get that TL ’ TN, which is a contradiction. This finishes the proof. Remark 4.3.2. From the definition of φ in the proof of Corollary 4.3.1, we observe that for any two α-tuples β and ˜β spanning a N dimensional vector space over Q, the closure of Zβ and Z ˜β depends only on how the dependent βj’s (and ˜βj’s) depend on the basis of N linear 97 independent reals, instead of depending the actual values βj’s (respectively ˜βj’s). Assume that the first N reals in both tuples form linearly independent sets and for N + 1 ≤ j ≤ α, NX n=1 NX n=1 βj = cj,nβn and ˜βj = ˜βn cj,n for the same dependency coefficients cj,n ∈ Q. Then both Zβ and Z ˜β are dense in φ(TN) for cj,1 where ˜zj = z 1 cj,2 z 2 φ(z1, . . . , zN) = (z1, . . . , zN , ˜zN+1, . . . , ˜zα), cj,N N . ··· z For a better intuition of Corollary 4.3.1, see figure 4.1. We begin with four triples of real 3}, the second is a triple {√ 3}, 2, 3}, and the last is the triple {√ √ 3, π}. For each 2, numbers: the first is equivalent to a pair {√ 2, the third is a triple {√ of these tuples β, we compute Zβ: √ 2 + 2 √ 3, 3 √ 3, 2+ √ √ √ √ 2, √ Figure 4.1: The sets Zβ for tuples β = ( (second), {√ √ √ √ √ 3) ≡ ( 2, 2, 3, 0) (left), β = ( √ √ 3} (third), and β = ( 3, π) (right). 2, √ 3, 3 2 + 2 √ √ 2, 2, √ √ 3, 2+ √ 3) The next lemma shows that if Z ∈ N0 is large enough such that Supp( ˆF) contains N linearly independent vectors, then the set XZ,f = {xZ,f(s) | s ∈ Z} is dense in an embedding of TN in Tα. For general Z, if M ≤ N is the largest cardinality of a linearly independent set of vectors in Supp( ˆF), then XZ,f is dense an in embedding of TM in Tα. Lemma 4.3.3. If Z ∈ N0 is large enough such that Supp( ˆF) contains N linearly independent vectors, then the set XZ,f is dense in a space homeomorphic to a torus TN embedded in = × k∈Supp( ˆF) TαˆF S1 | ˆF(k)|. 98 Proof. Recall that the exponential functions eiat and eibt are equal if and only if a = b. Moreover, recall from Remark 4.2.7 that the inner product values hk, ωi are different for distinct vectors k. By the condition on Z, there exist N linearly independent vectors in Supp( ˆF), say k1, . . . , kN. Then for all j ∈ Supp( ˆF), for cj,n ∈ Q. Observe that the linearity of inner products implies that for all kj ∈ Supp( ˆF), kj := cj,nkn NX n=1 NX n=1 hkj, ωi = cj,nhkn, ωi. Therefore the tuple β = (hk1, ωi, . . . ,hkα, ωi) spans an N-dimensional vector space over Q. From Corollary 4.3.1, we get that the collection n(eiβ1z,··· , eβαz)(cid:12)(cid:12)(cid:12) z ∈ Zo is dense in an embedding of TN in Tα. Since the multilinear scaling given by Tα → × k∈Supp( ˆF) S1 | ˆF(k)| (z1,··· , zα) → ( ˆF(k1)z1,··· , ˆF(kα)zα) is a homeomorphism, it follows that XZ,f is dense in an embedding of TN in × k∈Supp( ˆF) Now, let ΩZ,f be the (d + 1) × α matrix eihk1,ωiτ0 ΩZ,f = ... eihk1,ωiτ d   ··· eihkα,ωiτ0 ... ··· eihkα,ωiτ d ... S1 | ˆF(k)|. (4.8) comprised of vectors ukj as its columns. Observe that for each t ∈ R, SWd,τ SZ f(t) = ΩZ,f · xZ,f(t). When we go from XZ,f to SWd,τ SZ f, the toroidal geometry is minimally perturbed if the columns ukj of ΩZ,f are mutually orthogonal. Since α > N typically, it is not possible 99 for all pairs to be orthogonal to each other. However, we can make these as orthogonal as possible by controlling their inner products. Suppose the embedding dimension d has been chosen. For any two k, l ∈ Supp( ˆF), the inner product huk, uli is computed as huk, uli = 1 + eiτhk−l,ωi + ··· + eiτhk−l,ωid. The mutual orthogonality is maximized when the following objective function G : R → R defined as G(x) = X (cid:12)(cid:12)(cid:12)1 + eixhk−l,ωi + ··· + eixhk−l,ωid(cid:12)(cid:12)(cid:12)2 k6=l G(x). There are two obstacles is minimized and ideally, we would like to choose τ = arg min x in solving this optimization problem. The first, which could be considered a blessing in disguise is that there might not be a global minimum, that is when there is a sequence of local minimas converging to G(x) = 0. The second is when the global minimum exists, but is too large to be ever useful in applications. The problem then reduces to finding a reasonable local minima, where the definition of “reasonable” depends on the size and nature of the data. In general, one can use peak finding algorithms to detect these local minima. For the purpose of this dissertation, we use the findpeaks(·) function in MATLAB. We add one more condition for τ to satisfy: G(τ) < (d + 1)2. This condition is sufficient to argue that no two vectors uk, ul will be parallel two each other, and will allow us to prove the structure theorem. Next, we provide an example for determining a good choice of τ: √ Example 4.3.4. Let the quasiperiodic function of interest be f(t) = eit + ei Clearly, the set {1, one can write it as 3+1)t. √ 3} is not incommensurate and in the language developed above, √ 3t + ei( 3, 1+ √ √ f(t) = eih(1,0),(1, √ 3)it + eih(0,1),(1, √ 3)it + eih(1,1),(1, 3)it. Then the objective function corresponding to this f is G(x) = √ (cid:12)(cid:12)(cid:12)(cid:12)1 + eix (cid:12)(cid:12)(cid:12)(cid:12)1 + eix( + √ 33(cid:12)(cid:12)(cid:12)(cid:12)2 +(cid:12)(cid:12)(cid:12)1 + eix + ··· + eix3(cid:12)(cid:12)(cid:12)2 3−1)3(cid:12)(cid:12)(cid:12)(cid:12)2 3 + ··· + eix √ √ 3−1) + ··· + eix( 100 where we have chosen the dimension d = 3, the reasons for which will be clear in Theorem 4.3.5. The graph of the objective function G in Figure 4.2 suggests several local minimas at x ∈ [0, 40]. To estimate these, we use the findpeaks(·) function in MATLAB on −G(x). While in practice we will only concern ourselves in the global minima in the chosen range [0, 40], we will analyze the top few choices for the purpose of this example. To make the process faster, one can insert a threshold on the function −G(x). In table 4.1, we find all peaks of −G that are higher than −0.5, i.e. all local minimas lower than 0.5, along with angles θk,l (in degrees) between uk and ul for each of the values of x. Figure 4.2: Example: The objective function G(x) for finding an optimal τ, for the function √ f(t) = eit + ei 3t + ei( √ 3+1)t. x 4.5623 23.5718 28.1141 29.9150 G(x) 0.3204 0.0056 0.2717 0.0791 θ(1,0),(1,1) 88.0983 89.6226 89.9883 89.0968 θ(0,1),(1,1) 84.4038 89.5993 85.4674 87.0751 θ(1,0),(0,1) 84.4327 89.0784 84.0524 87.3789 Table 4.1: Example of τ estimation: Candidates for τ, along with the corresponding local minimums, and the angles θk,l (in degrees) between uk and ul Clearly, the best choice for τ is 23.5718 out of the 4 values in the table. However, if in a scenario, it is too big to be useful, then one would have to use τ = 4.5623. We can also see that for all x in the table, G(x) (cid:28) (d + 1)2 = 16. 101 Having established how to choose the delay parameter τ, we now prove the main result of this section, that is, the structure theorem: Theorem 4.3.5. The sliding window embeddingn SWd,τ SZ f(z) | z ∈ Zo is dense in a space homeomorphic to TN in Td+1 if d + 1 ≥ α and if τ satisfies that G(τ) < (d + 1)2. and let A be the L × L upper left block of ΩZ,f. Since rank(cid:16)ΩZ,f Proof. Assume on the contrary that the matrix ΩZ,f is not full rank. Let L = min (d + 1, α) < L, we obtain that det(A) = 0. This implies that the rows of A are linearly dependent, so for some c0, . . . , cL−1 ∈ C, not all zero, we have L−1X (cid:17) cleihkj ,ωiτ l = 0 l=0 for all 1 ≤ j ≤ L. In other words, for each 1 ≤ j ≤ L, eihkj ,ωiτ is a root of the polynomial P(z) = c0 + c1z + ··· + cL−1zL−1. By remark 4.2.7, all hkj, ωi are distinct. We claim that the assumption on τ implies that all hkj, ωiτ are distinct modulo 2π, because if for some ki 6= kj, the following is true eihki,ωiτ = eihkj ,ωiτ (cid:12)(cid:12)(cid:12)(cid:12)(cid:28) (cid:29)(cid:12)(cid:12)(cid:12)(cid:12)2 uki , ukj then we would obtain G(τ) ≥ = (d + 1)2 which would contradict our as- sumption. This implies that P(z) has L distinct roots, and this further contradicts that P is a polynomial of degree L − 1. Therefore, A is invertible and hence, ΩZ,f has full rank. Concluding, if the embedding dimension d + 1 ≥ α, then the sliding window embedding SWd,τ SZ f(Z) is dense in a space homeomorphic to TN embedded inside Td+1. We would like to remark that the condition on τ in the above theorem only guarantees the topology of a N-torus. Preserving the geometric structure as much as possible requires choosing τ by optimizing G. 102 4.4 Persistent Homology In this section, we present results about the Rips persistent homology of the sliding window embedding. The strategy we use is to construct a composite Lipschitz map Ω−1 Z,f−−−→ XZ,f π−→ TN SWd,τ SZ f where the map π : XZ,f → TN is a projection onto a standard N-dimensional torus given by   π ˆF(kN)eihkN ,ωit ˆF(kN+1)eihkN+1,ωit = ˆF(k1)eihk1,ωit ... ... ˆF(kα)eihkα,ωit    eihk1,ωit ... eihkn,ωit ... eihkN ,ωit  where after reordering {k1, . . . , kN} is a linearly independent set over Q. We will first show that π is a Lipschitz function: Proposition 4.4.1. The projection map π π :(cid:16)XZ,f ,||·||∞ (cid:17) →(cid:16)TN ,||·||∞ (cid:17) is Lipschitz, with Lipschitz constant 1 | ˆF(k)min| where | ˆF(k)min| := min k∈Supp( ˆF) (cid:12)(cid:12)(cid:12) ˆF(k)(cid:12)(cid:12)(cid:12). 103 Proof. For any two s, t ∈ Z, we have (cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)π (cid:16) xZ,f(t)(cid:17) − π (cid:16) xZ,f(s)(cid:17)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)∞ = max 1 (cid:12)(cid:12)(cid:12)eihkn,ωit − eihkn,ωis(cid:12)(cid:12)(cid:12) | ˆF(k)min|| ˆF(k)min|(cid:12)(cid:12)(cid:12)eihkn,ωit − eihkn,ωis(cid:12)(cid:12)(cid:12) | ˆF(k)|(cid:12)(cid:12)(cid:12)eihkn,ωit − eihkn,ωis(cid:12)(cid:12)(cid:12) | ˆF(k)|(cid:12)(cid:12)(cid:12)eihkn,ωit − eihkn,ωis(cid:12)(cid:12)(cid:12) k1,··· ,kN = max k1,··· ,kN | ˆF(k)min| max k1,··· ,kN | ˆF(k)min| max k∈IN Z ≤ ≤ (cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)xZ,f(t) − xZ,f(s)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)∞ . 1 1 1 = This finishes the proof. | ˆF(k)min| It is important to note that the Lipschitz constant linearly independent vectors {k1,··· , kN}. 1 | ˆF(k)min| is independent of choice of Next, we will use theorem 3.4.3 and proposition 4.4.1 to prove a lower bound on the 1- dimensional Rips persistence of XZ,f. Assume without a loss of generality that {k1,··· , kN} is a linearly independent set over Q. Hence, for all 1 ≤ j ≤ α, there exist rational coefficients cj,n ∈ Q such that NX n=1 kj = cj,nkn and consequently, βj := hkj, ωi = * NX n=1 + NX n=1 = cj,nkn, ω cj,nhkn, ωi =: NX n=1 cj,nβn. Define a map from TN to TαˆF : NP n=1 i where zj = ˆF(kj)e φ : TN → TαˆF (eiβ1t1,··· , eiβN tN ) → (z1, . . . , zα) cj,nβntn. 104 Lemma 4.4.2. If the prime p in Zp satisfies 1 c2,n 1 max n lcm c1,n , ! < p, ,··· , 1 cα,n then there will be at least N bars of the type 3| ˆF(k)min| in bcdR 1 where ρn ≥ √ Proof. First, setting t2 = ··· = tN = 0 yields a closed curve (cid:17). (0, ρ1), (0, ρ2), . . . , (0, ρN) (cid:16)XZ,f ,||·||∞ (cid:18) ˆF(k1)eiβ1t1, . . . , ˆF(kα)eicα,1β1t1 (cid:18) (cid:19) γ1(t1) = (cid:19) < δ. For all 0 ≤ m ≤ M, |sm − sm+1| < δ. This implies that ||γ1(sm+1) − γ1(sm)||∞ = max ≤ max j j ≤ max j | ˆF(kj)eiβ1cj,1sm+1 − ˆF(kj)eiβ1cj,1sm| | ˆF(kj)β1cj,1(sm+1 − sm)| | ˆF(kj)cj,1β1|δ where the last term is less than 1 by equation 4.9. We obtain a 1-homology cycle in R1 given by ˜ν1 = [γ1(s0), γ1(s1)] + [γ1(s1), γ1(s2)] + ··· + [γ1(sM), γ1(s0)] 105 (cid:17) (cid:16)TαˆF . The time period of this curve is 2πQ1 ∈ N, and in TαˆF the least common multiple is taken over reciprocals of all non zero cj,1. Let δ, 1, 2 > 0 be such that β1 where Q1 = lcm c2,1 ,··· , 1, 1 1 cα,1 (cid:12)(cid:12)(cid:12) δ < 1 < 2 < √ 3. (4.9) (cid:12)(cid:12)(cid:12) ˆF(kj)cj,nβn (cid:21) 0 ≤ max (cid:20) j,n of the form 2πQ1 β1 T = {0 = s0 < s1 < ··· < sM} Let there be a finite T ⊂ 0, (cid:18) T, (cid:20) 0, (cid:21)(cid:19) 2πQ1 β1 satisfying dH and therefore, we obtain a class π∗([˜ν1]) ∈ H1 | ˆF(k)min| Now, let {0 = u0 < u1 < ··· < uM0} := T mod 2π 1 β1 and χ1 be a closed curve in TN R (cid:16)TN(cid:17). defined as (cid:20) 0, 2π β1 for u ∈ 4.4.1, (cid:21) . Let ˜m be such that u ˜m corresponds to sm modulo 2π χ1(u) = (eiβ1u, 1,··· , 1) β1 . Then by Proposition ||χ1(u ˜m+1) − χ1(u ˜m)||∞ ≤ ||˜πγ1(sm+1) − ˜πγ1(sm)||∞ ≤ 1 | ˆF(k)min| 1. This defines a 1-dimensional cycle µ1 in R (TN) given by 1 | ˆF(k)min| µ1 = [χ1(u0), χ1(u1)] + [χ1(u1), χ1(u2)] + ··· + [χ1(uM0), χ1(u0)] satisfying π∗([˜ν1]) = Q1[µ1]. By the assumptions on the prime p, Q1 is invertible in Fp and hence, ι∗π∗([˜ν1]) 6= 0. From the commutativity of the diagram (cid:16) (cid:16) ι∗ H1 R1 (cid:16) R φ π∗ (cid:16)TN(cid:17)(cid:17)(cid:17) (cid:16)TN(cid:17) H1 1 | ˆF(k)min| H1 R2 (cid:16) R φ π∗ (cid:16)TN(cid:17)(cid:17)(cid:17) (cid:16)TN(cid:17) 2 | ˆF(k)min| ι∗ H1 (4.10) we obtain that ι∗([˜ν1]) 6= 0. By denseness of XZ,f in φ(TN), we can find α > 0 and points xZ,f(t0),··· , xZ,f(tM) ∈ XZ,f such that and ||γ1(sm) − xZ,f(tm)||∞ < α ||γ1(sm+1) − γ1(sm)||∞ + 2α < 1. By an application of triangle inequality, we obtain ||xZ,f(tm+1) − xZ,f(tm)||∞ < 1 106 and this gives us another 1-homology cycle φ (cid:16)XZ,f (cid:16)TN(cid:17)(cid:17) and R1 ν1 = [xZ,f(t0), xZ,f(t1)] + [xZ,f(t1), xZ,f(t2)] + ··· + [xZ,f(tM), xZ,f(t0)] (cid:16) (cid:17). We claim that ν1 is just homologous to ˜ν1. If we in both R1 join each edge [γ1(sm), xZ,f(tm)] as well, we get ˜ν1 and ν1 as top and bottom faces of a 2-dimensional prism of height α. Through subdivision of simplices, as in [39, Theorem 2.10], we finish the argument. It is also worth noting that a different ν satisfying the same properties but built with different values of t0,··· , tM will be homologous to ν1 as well. (cid:12)(cid:12)(cid:12) ˆF(kj)cj,nβn (cid:12)(cid:12)(cid:12) ˆF(kj)cj,nβn (cid:12)(cid:12)(cid:12) δ and all 2 < (cid:12)(cid:12)(cid:12) δ and ρ1 ≥ √ This implies that ι∗([ν1]) 6= 0. Therefore, it yields a bar [‘1, ρ1) such that ‘1 ≤ 1 and 3| ˆF(k)min|, we ρ1 ≥ 2. Since this is true for all 1 > max 3| ˆF(k)min|. This entire process works for all δ get that ‘1 ≤ max satisfying the equation and therefore, as we let δ → 0, we obtain a class alive for all 1 > 0. Similarly, we can obtain N 1-homology classes [ν1], . . . , [νN] that map to Q1[µ1], . . . , QN[µN] respectively under π∗, and correspond to bars (0, ρn) such that ρn ≥ √ 3| ˆF(k)min| for all n. √ j,n j,n We will now use Lemma 4.4.2 along with cup products [39, Chapter 3] and the isomor- i phism of persistent homology and cohomology [24] to prove the following result. Theorem 4.4.3. For i ≤ N, there will be at least (cid:16)N (cid:17) bars of the type (0, ρ1), (0, ρ2), . . . , (0, ρ(N i )) (cid:16)XZ,f ,||·||∞ where ρn ≥ √ Proof. By Lemma 4.4.2, ∃ N distinct 1-dimensional Rips persistent homology classes which take birth exiting 0 and die entering ρn ≥ √ 3| ˆF(k)min|. By the isomorphism of persistent classes corresponding to (0, ρn) respectively. Pick any  ∈(cid:16)0, homology and cohomology [24], there are N distinct 1-dimensional persistent cohomology 3| ˆF(k)min|(cid:17). Then we get N 3| ˆF(k)min| in bcdR (cid:17). √ i 1-dimensional cohomology classes [ϑ1],··· , [ϑN] 107 in H1(cid:16) R (cid:16)XZ,f (cid:17)(cid:17). Using cup products and any choice of i of these N classes, we can get i-th dimensional classes Varying  and using that the cup product is functorial, we get H1(cid:16) H1(cid:16) R1 R2 ]. [ϑl1] ^ ··· ^ [ϑli (cid:16)XZ,f (cid:17)(cid:17) (cid:16)XZ,f (cid:17)(cid:17) R1 (cid:16)XZ,f (cid:17)(cid:17) × ··· × H1(cid:16) (cid:17)(cid:17) (cid:16)XZ,f (cid:17)(cid:17) × ··· × H1(cid:16) (cid:17)(cid:17) ρn and die entering 0. Therefore, there are at least (cid:16)N (cid:16)XZ,f (cid:16)XZ,f Hi(cid:16) Hi(cid:16) R2 R2 R1 (4.11) is commutative. This implies that the i-th dimensional cohomology classes are alive at √ 3| ˆF(k)min| ≤ min cohomology classes in dimension i with cohomological death at 0 and persistence at least √ 3| ˆF(k)min|. The isomorphism between persistent homology and cohomology finishes the proof. (cid:17) persistent n i We now use linear algebra to argue that Ω−1 Z,f is the conjugate transpose of ΩZ,f ΩH Z,f is Lipschitz. In the proposition below, Proposition 4.4.4. Let λmin and λmax be the minimum and the maximum eigenvalues of Z,f · ΩZ,f respectively. Then ΩH q(d + 1)λmax 1 Z,f · v(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)∞ ≤ 1√ ||v||2 ≤(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)Ω−1 ||v||2 λmin for each v ∈ Cα. Z,f is Lipschitz with the constant Therefore, the composition map π ◦ Ω−1 Theorem 4.4.5. For i ≤ N, there will be at least (cid:16)N (cid:17) bars (0, ρ1), (0, ρ2), . . . , (0, ρ(N i )) (cid:17). SWd,τ SZ f,||·||2 where ρn ≥ √ 3| ˆF(k)min|√ λmin in bcdR (cid:16) i i √ 1 λmin| ˆF(k)min|. 108 Proof. By Proposition 4.4.4, we have the following commutative diagram for each i Hi √ (d+1)λmax λmin R√ R√ Hi (cid:16) 1 SWd,τ SZ f,||·||2 (cid:16)XZ,f ,||·||∞ 1 (d+1)λmax λmin (cid:17) (cid:17) (4.12) Hi SWd,τ SZ f,||·||2 R1 (cid:16) (cid:16) R 1√ Hi λmin (cid:16)XZ,f ,||·||∞ (cid:17)(cid:17) (cid:17) (cid:16) where the downward maps are induced by Ω−1 ΩZ,f. By [53, Lemma 2.3] and Theorem 4.4.3, there are at least (cid:16)N i (cid:17) bars with length at Z,f and the upper diagonal map is induced by √ 3| ˆF(k)min|√ least λmin in bcdR i SWd,τ SZ f,||·||2 (cid:17). 4.5 Computational Example In this section, we apply the above established theory to quasiperiodic signals. We will first work through the entire pipeline for the special case where α = N, i.e. when the quasiperiodic function is just the sum of exponential functions with non-commensurate frequencies: f(t) = eiω1t + ··· + eiωN t. In general, we begin with a signal sampled from f, use Fast Fourier Transform to estimate the frequencies, which we further use to estimate a good choice of τ as discussed in section 4.3, compute the sliding window point cloud and finally, compute Rips persistent homology of SWd,τ f. One of the main challenges in computing bcdR i (SWd,τ f(T); F) for a quasiperiodic time series f is that if SWd,τ f fills out the torus at a slow rate — requiring a potentially large T ⊂ Z — then the persistent homology computation becomes prohibitively large. To combat this, we will use an alternate strategy leveraging a persistent Künneth formula introduced in [35]. The strategy is based on the categorical persistent Künneth formula (Corollary 3.2.6). 109 For our second example, we apply our theory to music. We start with a real music sample with dissonance, which is a characterization of simultaneous tones that causes un- pleasantness. We show using the developed theory that dissonance can be characterized as quasiperiodicity in the signal. 4.5.1 An approximation strategy using a persistent Künneth formula Let us revisit the Künneth approximation strategy from [35] and its comparison with the more direct technique using landmark approximation which we describe first: Landmarks: We select a set L ⊂ SWd,τ f of landmarks using maxmin sampling. That is, ‘1 ∈ SW d,τ f is chosen at random and the rest of the landmarks are selected inductively as minnkx − ‘1k2, . . . ,kx − ‘jk2 o ‘j+1 = argmax x∈SW d,τ f We endow L with the Euclidean distance in Cd, and compute the Rips barcodes bcdR i (L,k · k2), for i = 0, 1,··· , N, directly using Ripser [4]. We describe the Künneth strategy next: Künneth: For 1 ≤ n ≤ N, Let pn : CN −→ C be the projections onto the n-th coordinate. Let SWd,τ f(t) = ΩZ,f · φ(t). We select N sets of landmarks, Xn ⊂ pn ◦ φ(T) with l points each using maxmin sampling, and endow the Cartesian product X1 × ··· × XN with the maximum metric in CN. The barcodes of Xn, for each n are computed using Ripser[4], and we deduce bcdR i (X1 × ··· × XN ,k · k∞) for i = 0, 1, . . . , N using Corollary 3.4.2. 110 4.5.1.1 An example with 2 frequencies The general strategy will be illustrated with a computational example: Let c1, c2 ∈ C (cid:114) {0} with |c1|2 + |c2|2 = 1, and let ω ∈ R (cid:114) Q. If f(t) = c1eit + c2eiωt then SWd,τ f(t) = Ω · φ(t), where Ω = 1√ d + 1  1 1 eiτ ... eidτ eiωτ ... eidωτ  , √ d + 1 φ(t) =  c1eit c2eiωt  . An elementary calculation shows that if d ≥ 1 and τ = (d+1)|ω−1|, then the columns of Ω are orthonormal in Cd+1. Fix d = 1, ω = 2. Figure 4.3 below shows the real part of f (left), and a visualization (right) of the sliding window point cloud SWd,τ f = SWd,τ f(T), T = {t ∈ Z : 0 ≤ t ≤ 4, 000}, using Principal Component Analysis (PCA) [44]. √ √ 3, τ as above, and c1 = c2 = 1/ 2π Figure 4.3: (Left) real(cid:16) f(t)(cid:17) = 1√ 2 cos(t) + 1√ √ 2 cos( and (Right) a PCA projection into R3 of the point cloud SWd,τ f. 3t) for the quasiperiodic time series f, Computing the exact barcodes bcdR i (SWd,τ f), i = 0, 1, 2, for point clouds of this size is already prohibitively large (e.g., with Ripser [4]). Thus, one strategy is to choose a smaller 111 050100150200250300-2-1012200-21.50-1.5 set of landmarks L ⊂ SWd,τ f and use the stability theorem [19] (cid:16)bcdR dB i (SWd,τ f)(cid:17) ≤ 2dGH(L, SWd,τ f) i (L), bcdR to estimate the barcodes of SWd,τ f using those of L, up to an error (in the bottleneck sense) of twice the Gromov-Hausdorff distance dGH between L and SWd,τ f. Specifically, if r = dGH(L, SWd,τ f) and I = [‘I , ρI) ∈ bcdR i (L) satisfies ρI − ‘I > 4r, then there is a unique J ∈ bcdR i (SWd,τ f) with |ρI − ρJ|,|‘I − ‘J| ≤ 2r, and thus max{0 , ρI − 2r} ≤ ρJ ≤ ρI + 2r max{0 , ‘I − 2r} ≤ ‘J ≤ ‘I + 2r. (4.13) We next apply the two strategies discussed above: Landmarks: We select a set L ⊂ SWd,τ f of 400 landmarks (%10 of the data) using maxmin sampling. We endow L with the Euclidean distance in C2, and compute the barcodes bcdR i (L,k · k2), i = 0, 1, 2, directly using Ripser [4]. Künneth: We select two sets of landmarks, XL ⊂ p1 ◦ φ(T) and YL ⊂ p2 ◦ φ(T) with 70 points each using maxmin sampling, and endow the cartesian product XL × YL with the maximum metric in C2. The barcodes of XL and YL are computed using Ripser, and we deduce those of bcdR i (XL × YL,k · k∞) for i = 0, 1, 2 using Corollary 3.2.6. 4.5.1.2 Computational Results Table 4.2 shows the computational times in each approximation strategy — i.e., via the landmark set L and the persistent Künneth theorem applied to XL × YL — as well as the number of data points in each case. As these results show, the Künneth approximation strategy is almost two orders of mag- nitude faster than just taking landmarks, and as we will see below, it is also more accurate. 112 Landmarks Künneth Time (sec) # of points 15.22 400 0.20 4,900 Table 4.2: Computational times, and number of points, for the landmark and Künneth approximations to bcdR i (SWd,τ f), i ≤ 2. Indeed, the inequalities in (4.13) can be used to generate a confidence region for the ex- istence of an interval J ∈ bcdR i (L). A similar region can be estimated from bcdR i (XL × YL) as follows. Since the columns of Ω are orthonormal, then for every z ∈ C2 we have kzk∞ ≤ kzk2 = kΩzk2 ≤ √ i (SWd,τ f) given a large enough interval I ∈ bcdR 2kzk∞ and thus R(SWd,τ f,k · k2) ⊂ R(φ(T),k · k∞) ⊂ R√ 2(SWd,τ f,k · k2). Moreover, (see 3.1.21) if I ∈ bcdR i (XL × YL,k · k∞) satisfies − √ XL × YL, φ(T)(cid:17) 2‘I > 4dGH (cid:16) ρI√ 2 where λ = dGH(XL × YL, φ(T)) is computed for subspaces of (C2,k · k∞), then there exists a unique J ∈ bcdR i (SWd,τ f,k · k2) so that ) ρI − 2λ√ ) 2 ‘I − 2λ√ 2 ( ( max 0 , max 0 , ≤ ρJ ≤ √ ≤ ‘J ≤ √ 2 · (ρI + 2λ) 2 · (‘I + 2λ). (4.14) Figure 4.4 shows the resulting confidence regions for both approximation strategies. Each i (L) (4.13) and i (XL × YL) (4.14) are shown in blue and red, respectively. We compare these regions interval [‘, ρ) is replaced by a point (‘, ρ) ∈ R2, and the regions for bcdR bcdR by computing their area, and report the results in Table 4.3. i Landmarks Künneth 1 1 2 0.4680 0.4709 0.4704 i (L) (blue) and bcdR Table 4.3: Areas for confidence regions from bcdR i = 1, 2 (see Figure 4.4). A smaller area suggests a better approximation. 0.7677 0.7480 0.9072 i (XL × YL) (red), 113 Figure 4.4: Confidence regions for bcdR i (XL × YL), i = 1, 2. For a given color, each box (confidence region) contains a point (‘J , ρJ) corresponding to a unique J ∈ bcdR i (L) and bcdR i (SWd,τ f). These results suggest that the Künneth strategy provides a tighter approximation than using landmarks. Moreover, both strategies can be used in tandem — improving the quality of approximation — via intersection of confidence regions. 4.5.2 An application to music theory In music theory, consonance and dissonance are classification of multiple simultaneous tones. While the former is associated with pleasantness, the latter creates tension as experienced by the listener. Perfect dissonance occurs when the audio frequencies are irrational with respect to each other. One of such instances is that of a tritone, which a musical interval that is halfway between two octaves. Mathematically, for a base frequency ω1, the tritone is √ 2ω1. We will use the theory of sliding window embedding to quantify quasiperiodicity from a dissonant sample. For the purpose of this application, we use a 5-second audio recording of a brass horn provided by Adam Huston. It was read by audioread function in MATLAB and the signal plot is shown in Figure 4.5. 114 Figure 4.5: The audioread plot of a dissonant music sample created on a brass horn. Like before, in order to perform sliding window analysis, we need to choose appropriate parameters d and τ. The first step is to use Fast Fourier Transform in MATLAB to obtain the amplitude-frequency spectrum. We use findpeaks with thresholds MinPeakHeight = 0.06 Figure 4.6: The amplitude-frequency spectrum of the music sample plot using Fast Fourier Transform. and MinPeakDistance = 100 to detect frequencies which we will use for estimation of the embedding parameters. See Table 4.4. Angular Frequencies Frequencies (Hz) Proportion 1384.93 220.41 1 1957.83 311.59 1.4137 ≈ √ 2 2769.86 440.83 2 3911.93 622.60 √ 2.8246 ≈ 2 2 Table 4.4: List of frequencies in the amplitude-frequency spectrum: The first row is the list of frequencies that were detected. The second row is their conversion to Hertz. The third row is their ratio with respect to the first one. 115 Remark 4.5.1. While our entire theory has been developed for complex functions, it can be adjusted to work with real functions via the following identities: cos(at) = 1 2 eiat + 1 2 ei(−a)t and sin(at) = 1 2i eiat − 1 2i e−i(−a)t for any a ∈ R, t ∈ R. For the purpose of our analysis, this would mean that instead of 4 frequencies, we count 8 of them (with their negatives). By the theory, the complex embedding dimension d should be at least 8, that would imply that the real embedding dimension should be at least 8. Therefore, we choose the embedding dimension d = 9, and the delay τ = 0.02858 in accor- dance with the optimization discussion in section 4.3. We use cubic splines to compute the sliding window vectors and present the PCA representation of the point cloud, along with the persistence diagrams in Figure 4.7. We conclude the dissonance is indeed a quasiperiodic feature. Figure 4.7: (Left) PCA representation of the sliding window point cloud generated from the dissonant sample with parameters d = 9 and τ = 0.02858. (Right) Persistence Diagrams in homological dimension 1 and 2. The dotted lines separate the top 2 persistence points (sim. maximum persistence point) from the rest in dimension 1 (sim. dimension 2). 116 CHAPTER 5 STABILITY OF MULTISCALE CIRCULAR COORDINATES In this chapter, we provide a stability characterization of circular coordinates. We set up the problem of stability with respect to the choice of landmarks in section 5.1. In section 5.2, we present stability results for the geometric noise model. In section 5.3, we approach the general case and prove stability for the Wasserstein noise model. The last section 5.4 is dedicated to examples. Parts of this chapter are to appear in [34]. We begin with a description of the sparse circular coordinates algorithm [55, Section 1.2] first. 5.0.1 The sparse circular coordinates algorithm 1. Let (M, d) be a finite metric space (i.e., the dataset) and select a set of landmarks L = {‘1, . . . , ‘N} ⊂ M, e.g., randomly or via maxmin sampling. 2. Choose a prime q > 2 and compute the 1-dimensional Rips persistent cohomology P H1(R(L); Zq) on (L, d|L) with coefficients in Zq. Let bcd(L) denote the resulting persistence diagram. 3. Let rL = max x∈M min ‘∈L d(x, ‘) be the minimal cover radius. Observe that rL = dH(L, M). If there exists (a, b) ∈ bcd(L) such that max{a, rL} < b2, then let α = t · max{a, rL} + 1 2(1 − t)b for some t ∈ (0, 1) and η00 ∈ Z1(R2α(L); Zq) be a cocycle representative for the persis- tent cohomology class corresponding to (a, b). 4. Lift η00 to an integer cocycle η0 ∈ Z1(R2α(L); Z) such that η00−η0 mod q is a cobound- ary in C1(R2α(L); Zq). In practice, we use the cochain η0(σ) = η00(σ) η00(σ) − q 117 if η00(σ) ≤ q−1 2 if η00(σ) > q−1 2 . Lastly, define η = ι1η0 where ι1 : C1(R2α(L); Z) → C1(R2α(L); R) is the homomor- phism induced by the inclusion ι : Z ,→ R. 5. Choose positive weights for the vertices and edges of R2α(L) and let 2α : C1(R2α(L); R) → C0(R2α(L); R) d+ be the weighted Moore-Penrose pseudoinverse of the coboundary map d2α : C0(R2α(L); R) → C1(R2α(L); R). and define τ = −d+ 2α(η) and θ = η + d2α(τ). 6. Denote τj := τ([‘j]) and θjk := θ([‘j, ‘k]) when [‘j, ‘k] ∈ R2α(L) (it is zero otherwise). Let Bα(‘j) denote a ball of radius α centered around ‘j ∈ L and {ϕj}j denote the par- tition of unity subordinate to the collection {Bα(‘j)}j. The sparse circular coordinates are defined as follows: N[ hθ,τ : Bα(‘j) → S1 ⊂ C j=1 Bα(‘j) 3 b 7→ exp 2πi τj + NX r=1  . ϕr(b)θjr The circular coordinates algorithm can be used to reconstruct dynamical systems as in the following example: √ 2 ei 2 eit + 1√ Example 5.0.1. The quasiperiodic function f(t) = 1√ 3t in section 4.5.1.1 can be realized as an observation of the irrational winding on a 2-torus starting at (0, 0), with √ 3. The theory developed in the last chapter tells that the sliding window embedding slope of the function will be a 2-torus and persistence verifies that. Using the two 1-persistent cocycles, we can generate two sets of circular coordinates using the algorithm above, and together we reconstruct an approximation to the original winding. See figure 5.1 for the entire pipeline. 118 √ Figure 5.1: An example of reconstructed toroidal dynamics: (Left) The irrational winding 3. (Second) The sliding window embedding of the on a 2-torus starting at (0, 0) with slope observation f(t) = 1√ 3t of the winding. (Third) The Rips persistence diagram in dimension 0, 1. The two 1-persistent cocycles can be used to create two sets of circular coordinates. (Right) The pair of coordinates can be used to reconstruct the toroidal winding. The average slope is estimated to be 1.9698. 2 eit + 1√ √ 2 ei Note that the algorithm depends on a choice of landmarks L ⊂ M and as one would expect, different choices of landmarks may yield different circular coordinates. One would also expect that two landmark sets that are “close” to each other in some sense yield circular coordinates that are also “close” in some sense. In the next section, we set up the problem of stability. 5.1 The stability set-up We start with two finite landmark sets L, ˜L of the metric space (M, d) with probability weights ω and ˜ω satisfying that dW,∞((L, ω), (˜L, ˜ω)) < δ where dW,∞ is the Wasserstein-Kantorovich-Rubinstein metric as in Definition 2.5.5. The goal is to obtain results on the proximity of the associated circular valued functions in the L∞-metric. We first solve the problem for a special case, that is when L and ˜L are in a weight preserving bijective correspondence: We call this the Geometric Noise Model. We approach the general case by duplicating some landmarks in a well-defined manner to create a bijection and therefore, reducing it to the Geometric Noise Model. Next, we give explicit choices for partitions of unity and edge weights that we use in our stability analysis. 119 200-21.50-1.5 5.1.1 Partition of Unity Let φ : R → [0,∞) be increasing and Lipschitz, i.e. for all a, b ∈ R, φ(a) ≤ φ(b) if a ≤ b, and |φ(a) − φ(b)| ≤ Lφ |a − b| where Lφ is the Lipschitz constant. Moreover, let φ(a) = 0 for all a ≤ 0. For an α > 0, and the function φ defined above, the collection of functions n Proposition 5.1.1. Let L = {‘1, . . . , ‘N} ⊂ (M, d) be a finite set with weights {ω1, . . . , ωN}. ϕj : M → Ro defined as ϕj(b) = ωjφ(α − d(b, ‘j)) ωkφ(α − d(b, ‘k)) NP Bα(‘j)oN k=1 is a partition of unity subordinated to n Proof. By construction, we have NP ϕj(b) = 1. Thus, we only need to verify that Supp(ϕj) ⊂ Bα(‘j). Clearly, if b 6∈ Bα(‘j), then d(b, ‘j) ≥ α, thus α − d(b, ‘j) ≤ 0 and by construction of φ, then φ(α − d(b, ‘j)) = 0. j=1. If there is another finite set ˜L = n˜‘1, . . . , ˜‘N satisfying d(˜‘i, ‘i) < δ, then for α− δ we can define another partition of unityn o ⊂ (M, d) with weights {˜ω1, . . . , ˜ωN} ψj : M → Ro j=1 as We introduce notation: ψj(b) = ˜ωjφ(α − δ − d(b, ˜‘j)) NP ˜ωkφ(α − δ − d(b, ˜‘k)) k=1 NX NX k=1 k=1 ϕ(b) = ψ(b) = ωkφ(α − d(b, ‘k)) ˜ωkφ(α − δ − d(b, ˜‘k)). If the weights satisfy ωk = ˜ωk for all k, then the following is true: Proposition 5.1.2. If ωk = ˜ωk for all k, and d(˜‘k, ‘k) < δ for all k, then ψ(b) ≤ ϕ(b) for all b ∈ M. 120 Proof. By triangle inequality, since (cid:12)(cid:12)(cid:12)d(b, ‘k) − d(b, ˜‘k)(cid:12)(cid:12)(cid:12) ≤ d(‘k, ˜‘k) < δ, then d(b, ‘k) < δ + d(b, ˜‘k). By properties of φ, we obtain φ(α − δ − d(b, ˜‘k)) ≤ φ(α − d(b, ‘k)) for each k. Therefore, ψ(b) ≤ ϕ(b). Proposition 5.1.3. For b ∈ L(α−δ), we have NX (cid:12)(cid:12)(cid:12)ϕj(b) − ψj(b)(cid:12)(cid:12)(cid:12) ≤ 4δLφ ϕ(b) . j=1 Proof. We will proceed as follows: (cid:12)(cid:12)(cid:12)ϕj(b) − ψj(b)(cid:12)(cid:12)(cid:12) = (cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12) (cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12) − ˜ωjφ(α − δ − d(b, ˜‘j)) NP ˜ωkφ(α − δ − d(b, ˜‘k)) (cid:12)(cid:12)(cid:12)δ + d(b, ˜‘j) − d(b, ‘j)(cid:12)(cid:12)(cid:12) + ˜ωjφ(α − δ − d(b, ˜‘j)) ωjφ(α − d(b, ‘j)) NP ωkφ(α − d(b, ‘k)) k=1 ≤ ωjLφ ϕ(b) ≤ ωjLφ ϕ(b) 2δ + ˜ωjφ(α − δ − d(b, ˜‘j)) ψ(b) k=1 ψ(b) (cid:12)(cid:12)(cid:12)(cid:12)(cid:12) . (cid:12)(cid:12)(cid:12)(cid:12)(cid:12)1 − ψ(b) ϕ(b) (cid:12)(cid:12)(cid:12)(cid:12)(cid:12) where in the second step, we added and subtracted ωj φ(α−δ−d(b,˜‘j)) ωkφ(α−d(b,‘k)) , and used triangle inequality, while keeping in mind that ω and ˜ω are the same. Summing over all j yields (cid:12)(cid:12)(cid:12)ϕj(b) − ψj(b)(cid:12)(cid:12)(cid:12) ≤ 2δLφ ϕ(b) NX j=1 NX j=1 ωj + ϕ(b) + 2δLφ ϕ(b) = 4δLφ ϕ(b) . ϕ(b) (cid:12)(cid:12)(cid:12)(cid:12)(cid:12)1 − ψ(b) NP (cid:12)(cid:12)(cid:12)(cid:12)(cid:12) ≤ 2δLφ (cid:12)(cid:12)(cid:12)(cid:12)(cid:12)1 − ψ(b) ϕ(b) k=1 5.1.2 Weights on edges By a weight family on the edges of L, we mean a sequence of functions να : Rα(L)(1) → [0,∞) (parametrized by α) satisfying the following properties: • να is increasing in α, and 121 (cid:16)[‘i, ‘j](cid:17), which we call the weight of the edge [‘i, ‘j], is 0 if and only if 0 < α ≤ • να d(‘i, ‘j). For the purpose of this dissertation, we define these να in the same spirit as the partitions of unity, i.e. controlled by an increasing and Lipschitz function ρ : R → [0,∞) satisfying ρ(a) = 0 for all a ≤ 0, and by vertex weights ω in the following manner: να([‘i, ‘j]) = ωiωjρ(α − d(‘i, ‘j)). (5.1) The vertex weights ω and the weight families να define inner products h·,·iα on C0(Rα(L); R) and C1(Rα(L); R) respectively, by letting the indicator functions 1σ on k-simplices σ ∈ Rα(L) (for k = 0, 1) be orthogonal, and setting h1[‘i], 1[‘i]i = ωi and h1σ, 1σiα = να(σ). Similarly, we define vertex weights ˜ω and a weight family ˜να on the edges of ˜L ˜να([˜‘i, ˜‘j]) = ˜ωi˜ωjρ(α − d(˜‘i, ˜‘j)). and the induced inner products on C0(Rα(˜L); R) and C1(Rα(˜L); R) follow. 5.2 Geometric noise model Let L = {‘1, . . . , ‘N} and ˜L = {˜‘1, . . . , ˜LN} be subsets of M such that there is a bijection µ : ˜L → L satisfying the following conditions: 1. d(˜‘i, µ(˜‘i)) < δ 2. µ(˜‘i) = ‘i 3. ˜ωi := ˜ω(˜‘i) = ω(‘i) =: ωi for all i ∈ {1, . . . , N}. By an application of triangle inequality, d(˜‘i, ˜‘j) < 2α − 2δ ⇒ d(cid:16) (cid:17) ‘i, ‘j < 2α, 122 and therefore, µ extends to a simplicial map µ : R2α−2δ(˜L) → R2α(L), where α is chosen so that R2α−2δ(˜L), and hence R2α(L), is connected. In case of discon- nectedness, one can consider each connected component separately. Consider the induced commutative diagrams C0(R2α−2δ(˜L); R) ˜d2α−2δ C1(R2α−2δ(˜L); R) µ0 µ1 C0(R2α(L); R) d2α C1 (R2α(L); R) where ˜d2α−2δ, d2α are the coboundary maps, and µ0, µ1 are the maps induced by the sim- plicial map µ. In fact, µ0 is an isometry since it preserves norms. Let να, ˜να be the weight-families on the edges of L, ˜L respectively. Proposition 5.2.1. If the edge weights satisfy the condition in equation 5.1, then (cid:12)(cid:12)(cid:12)ν2α([‘i, ‘j]) − ˜ν2α−2δ([˜‘i, ˜‘j])(cid:12)(cid:12)(cid:12) ≤ 4ωiωjLρδ. Proof. By our choice in equation 5.1 and the assumption on vertex weights, we obtain (cid:12)(cid:12)(cid:12)ν2α([‘i, ‘j]) − ˜ν2α−2δ([˜‘i, ˜‘j])(cid:12)(cid:12)(cid:12) = ωiωj (cid:12)(cid:12)(cid:12)ρ(2α − d(‘i, ‘j)) − ρ(2α − 2δ − d(˜‘i, ˜‘j))(cid:12)(cid:12)(cid:12) ≤ Lρ (cid:12)(cid:12)(cid:12)ρ(2α − d(‘i, ‘j)) − ρ(2α − 2δ − d(˜‘i, ˜‘j))(cid:12)(cid:12)(cid:12) . (cid:12)(cid:12)(cid:12)2δ + d(˜‘i, ˜‘j) − d(‘i, ‘j)(cid:12)(cid:12)(cid:12) By Lipschitzness of ρ, we obtain which is less than Lρ4δ by triangle inequality. This finishes the proof. Now, let ( ˜d2α−2δ)+ and (d2α)+ be the weighted Moore-Penrose pseudoinverses ( ˜d2α−2δ)+ : C1(R2α−2δ(˜L); R) → C0(R2α−2δ(˜L); R) (d2α)+ : C1 (R2α(L); R) → C0 (R2α(L); R) 123 of the coboundary maps ˜d2α−2δ and d2α respectively. For the the image 0 6= η ∈ Img{C1 (R2α(L); Z) → C1 (R2α(L); R)}, let C0(R2α(L); R) 3 τ = −d+ 2α(η) C1(R2α(L); R) 3 θ = η + d2α(τ) ˜τ = −( ˜d2α−2δ)+µ1(η) ∈ C0(R2α−2δ(˜L); R) ˜θ = µ1(η) + ˜d2α−2δ(˜τ) ∈ C1(R2α−2δ(˜L); R). We want to bound the difference between the circle valued functions ˜h : ˜L(α−δ) → S1 Bα−δ(˜‘j) 3 b → exp ( 2πi ˜τj +X r !) ψr(b)˜θjr and h : L(α) → S1 Bα(‘j) 3 b → exp ( 2πi τj +X !) ϕr(b)θjr r on their common domain ˜L(α−δ) ⊂ L(α), where the partitions of unity {ϕr}r and {ψr}r are as defined above. Lemma 5.2.2. The functions ˜h and h defined as above differ on their common domain by |h(b) − ˜h(b)| ≤ 2π where ||ϕ(b) − ψ(b)||1 =P r φ(α − δ) |ϕr(b) − ψr(b)|. ψ(b) ||µ0(τ) − ˜τ||ω + ||ϕ(b) − ψ(b)||1||θ||∞ , ! Proof. From the definitions of θ and ˜θ, we have that (cid:17) = µ1(η)jr = ηjr = θjr −(cid:16) ˜θjr −(cid:16)˜τr − ˜τj (cid:17), it is indeed the case and therefore, (cid:16) if and only if the index pair (j, r) represents an edge in both R2α−2δ(˜L) and R2α(L). If b ∈ Bα−δ(˜‘j) ⊂ Bα (cid:12)(cid:12)(cid:12)(cid:12)(cid:12)exp ( ( |h(b) − ˜h(b)| = (cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:16) τj +X ϕr(b)θjr (cid:16) (cid:17) +X ϕr(b)θjr − ψr(b)˜θjr ˜τj +X !)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12) ψr(b)˜θjr 2πi (cid:17)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12) τr − τj − exp ≤ 2π τj − ˜τj !) 2πi (cid:17) r ‘j r r 124 We rewrite τj as P ψr(b)τj. Observe that if ψr(b) 6= 0, then Bα−δ(˜‘r) ∩ Bα−δ(˜‘j). This is equivalent to saying that the index (j, r) represents an edge in both R2α−2δ(˜L) and R2α(L). Therefore, r ϕr(b)θjr − ψr(b)˜θjr (cid:17)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12) (cid:12)(cid:12)(cid:12)(cid:12)(cid:12) |h(b) − ˜h(b)| ≤ 2π = 2π ≤ 2π ≤ 2π ≤ 2π (cid:17) +X (cid:16) r r (cid:12)(cid:12)(cid:12)(cid:12)(cid:12)X ψr(b)(cid:16) τr − ˜τr + ˜θjr − θjr (cid:12)(cid:12)(cid:12)(cid:12)(cid:12)X ψr(b) (τr − ˜τr) +X X ψr(b) · |τr − ˜τr| +X X ψ(b)φ(α − δ) · |τr − ˜τr| +X φ(α − δ) ωr r r r r r r (ϕr(b) − ψr(b)) θjr ! |θjr| · |ϕr(b) − ψr(b)| ! |θjr| · |ϕr(b) − ψr(b)| ! ||µ0(τ) − ˜τ||ω + ||ϕ(b) − ψ(b)||1||θ||∞ . ψ(b) where the last step comes from Hölder’s inequality. The ‘1 bound on the difference of partitions of unity was proved in lemma 5.1.3. The rest of this section is dedicated to finding an upper bound for ||µ0(τ) − ˜τ||ω. By definition, we have (˜τ − µ0(τ)) = ( ˜d2α−2δ)+µ1(η) − µ0d+ 2α(η). Using that η + d2α(τ) = θ, the commutativity relations, and the properties of the Moore- Penrose pseudoinverse, we get ( ˜d2α−2δ)+µ1(η) = ( ˜d2α−2δ)+ (−µ1d2α(τ) + µ1 (θ)) = −( ˜d2α−2δ)+ ˜d2α−2δµ0(τ) + ( ˜d2α−2δ)+µ1 (θ) = −PrKer( ˜d2α−2δ)⊥ (µ0(τ)) + ( ˜d2α−2δ)+µ1 (θ) where we have used that ( ˜d2α−2δ)+ ˜d2α−2δ projects surjectively onto the orthogonal comple- ment of Ker( ˜d2α−2δ). Using the connectedness of R2α−2δ(˜L), we get (˜τ − µ0(τ)) = −PrKer( ˜d2α−2δ)⊥ (µ0(τ)) + ( ˜d2α−2δ)+µ1 (θ) + µ0(τ) = PrKer( ˜d2α−2δ) (µ0(τ)) + ( ˜d2α−2δ)+µ1 (θ) = ( ˜d2α−2δ)+µ1 (θ) 125 where the last step is true because µ0(τ) ⊥ Ker( ˜d2α−2δ). Hence, it is enough to bound the 0-cochain ( ˜d2α−2δ)+µ1 (θ) ∈ C0(R2α−2δ(˜L); R). First, since the Moore-Penrose pseudoinverse satisfies A+ = A+AA+ for any matrix A, we obtain (cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)( ˜d2α−2δ)+µ1 (θ)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)2 ω ≤(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)( ˜d2α−2δ)+(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)2(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)( ˜d2α−2δ)( ˜d2α−2δ)+µ1 (θ)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)2 2α−2δ (5.2) where the first norm is the weighted operator norm. We will bound both the norms sepa- rately. Let ( ˜d2α−2δ)∗ : C1(cid:16) R2α−2δ(˜L); R(cid:17) → C0(cid:16) R2α−2δ(˜L); R(cid:17) be the adjoint of ˜d2α−2δ with respect to the inner products defined by the weights ˜ν2α−2δ and the probability measure ˜ω = ω. Then it satisfies the following proposition: Proposition 5.2.3. Let K be a simplicial complex with edge weights νK : K(1) → [0,∞) If d : C0 (K, R) → C1 (K, R) is the coboundary operator, let d∗ : C1 (K, R) → C0 (K, R) be its adjoint corresponding to the inner product on 1−chains induced by νK, then d∗d is the graph Hodge Laplacian on K(1). An application of the spectral theorem to the graph Hodge Laplacian operator ∆H = ( ˜d2α−2δ)∗ ˜d2α−2δ yields an orthonormal eigenbasis ˜x1, . . . , ˜xN for C0(R2α−2δ(˜L); R) with eigenvalues 0 = (λ1)2 < (λ2)2 ≤ ··· (λN)2. The eigenvalue 0 has multiplicity 1 because R2α−2δ(˜L) is connected. Let B be another orthonormal basis of C0(R2α−2δ(˜L); R) defined as ( 1√ B = [˜‘j] ωj (cid:12)(cid:12)(cid:12)(cid:12)(cid:12) j = 1, . . . , N ) . 126 Then with the respect to the basis B, the matrix LH of ∆H can be computed as LH(j, k) = = = ωj ! + [˜‘j] [˜‘k] 1√ ωk , * ∆H 1√ ωjωk 1√ D ˜d2α−2δ([˜‘j]), ˜d2α−2δ([˜‘k])E P 1≤i≤N √ ˜ν2α−2δ([˜‘i, ˜‘j]) 1 ωj − ˜ν2α−2δ([˜‘j ,˜‘k])  if j = k if j 6= k. ω ωj ωk 2α−2δ Note that since change of basis doesn’t change the eigenvalues of the matrix, the smallest non-zero eigenvalue of LH is also (λ2)2. This will be used while proving the Wasserstein stability later in this Chapter. We are now ready to bound the operator norm. Lemma 5.2.4. The weighted pseudoinverse of the coboundary map ˜d2α−2δ satisfies (cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)( ˜d2α−2δ)+(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)2 = 1 !2 λ2 Proof. Since the eigenvalues of ( ˜d2α−2δ)∗ ˜d2α−2δ are 0 = (λ1)2 < (λ2)2 ≤ ··· (λN)2, we get that λ2 is the maximum eigenvalue of the pseudoinverse ( ˜d2α−2δ)+. Therefore, (cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)( ˜d2α−2δ)+(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12) = 1 ! . λ2 Lemma 5.2.5. The weighted norm of ( ˜d2α−2δ)( ˜d2α−2δ)+µ1 (θ) satisfies Proof. First, let v = µ−1 0 ( ˜d2α−2δ)+µ1(θ) ∈ C0(R2α(L); R). Then (cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)( ˜d2α−2δ)( ˜d2α−2δ)+µ1 (θ)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)2 (cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)( ˜d2α−2δ)( ˜d2α−2δ)+µ1 (θ)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)2 2α−2δ 2α−2δ . (cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)( ˜d2α−2δ)+µ1(θ)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)ω ≤ 4δLρ ||θ||∞ =D µ1 (θ) , ( ˜d2α−2δ)( ˜d2α−2δ)+µ1 (θ)E = hµ1 (θ) , µ1d2α(v)i2α−2δ . 2α−2δ 127 The last inner product can be computed as ˜ν2α−2δ(e)θ(e)d2α(v)(e) e X =X = X e 1≤j 0, let dβ = d + βdδ be a metric on M × N and let ω and ˜ω be measures on (M, d) supported on L, ˜L respectively. If dW,∞((L, ω), (˜L, ˜ω)) < δ , then there exist functions m : L → N and ˜m : ˜L → N and measures ωm and ˜ωm on (M, dβ) with supports Lm = {(‘, k) ∈ L × N : 1 ≤ k ≤ m(‘)} ˜Lm =n(˜‘, s) ∈ ˜L × N : 1 ≤ s ≤ ˜m(˜‘)o such that m(‘)P 1. ω(‘) = ωm(‘, k) for all ‘ ∈ L and ˜ω(˜‘) = ωm(˜‘, s) for all ˜‘ ∈ ˜L. 2. There is a bijection ϑ : Lm → ˜Lm such that ωm(‘, k) = ˜ωm(ϑ(‘, k)) and k=1 ˜m(˜‘)P s=1 dβ((‘, k), ϑ(‘, k)) < δ + β for all (‘, k) ∈ Lm. Proof. Since dW,∞((L, ω), (˜L, ˜ω)) < δ, there exists µ ∈ M(ω, ˜ω) such that sup (a,b)∈R(µ) d(a, b) < δ 132 where R is the relation associated to the coupling measure µ as in section 2.5.3. Let M0 be the N × ˜N matrix where mj,k = µ(‘j, ˜‘k) for ‘j ∈ L and ˜‘k ∈ ˜L. An application of Lemma 5.3.1 to M0 yields a matrix M1 such that • M1 has size N0 × ˜N where N0 is the number of non-zero entries in M0, • M1 has at most one non-zero entry per row and • the non-zero entries in each column of M0 and M1 are the same. Remark 5.3.3 showcases the fact that we can index the entries in M1 as m1 (i,ik),j, where 1 ≤ i ≤ N, 1 ≤ j ≤ m and 1 ≤ k ≤ ni where ni is the number of non-zero elements in the i-th row of M0. We now apply Lemma 5.3.1 to (M1)T to obtain a matrix M2 such that • M2 has size ˜N0 × N0 where ˜N0 is the number of non-zero entries in (M1)T , • M2 has at most one non-zero entry per row, and • the non-zero entries in each column of (M1)T and M2 are the same. Observe that ˜N0 is the number of non-zero entries in M1, and by Remark 5.3.2, it is the same as the number of non-zero entries in M0. Thus ˜N0 = N0, making M2 a square matrix. Since the sets of non-zero entries for each column of M2 and (M1)T coincide and M1 has at most one non-zero entry per row, we conclude that M2 has at most one non-zero entry in each column and row. By using the convention in 5.3.3, we can index the elements of M2 as m2 (j,js),(i,ik) with 1 ≤ j ≤ ˜N, 1 ≤ s ≤ ˜nj, where ˜nj is the number of non-zero elements in the j-th column of M and 1 ≤ i ≤ N, 1 ≤ k ≤ ni where ni is the number of non-zero elements in the i-th row of M. If we define {(‘i, k) ∈ M × N : 1 ≤ k ≤ ni} o n(˜‘j, s) ∈ M × N : 1 ≤ s ≤ ˜nj 133 N[ ˜N[ i=1 Lm = ˜Lm = j=1 then M := (M2)T defines a measure on (M × N) × (M × N) supported on Lm × ˜Lm. Let ωm(‘i, k) = X ˜ωm(˜‘j, s) = X 1≤j≤ ˜N 1≤i≤N X 1≤s≤˜nj X 1≤k≤nj m(i,ik),(j,js) m(i,ik),(j,js). Notice that the projection on the first component π1 : M × N → M is such that π1(Lm) = 1 (‘i) = {‘i ∈ M : 1 ≤ i ≤ N} = L and π1(˜Lm) =n˜‘j ∈ M : 1 ≤ j ≤ ˜N {li} × N, then π−1 o = ˜L. And since π−1 1 (‘i) ∩ Lm = {(‘i, k) ∈ M × N : 1 ≤ k ≤ ni} which implies that niX m(i,ik),(j,js) m(i,ik),(j,js) {z entries in the i-th row of M k=1 1≤k≤ni ωm(‘i, k) = X = X = X 1≤j≤ ˜N 1≤j≤ ˜N 1≤j≤ ˜N X X 1≤s≤˜nj X  X 1≤s≤˜nj | 1≤k≤ni mi,j = ω(‘i).  } An analogous argument shows that ˜niX s=1 ˜ωm(˜‘i, s) = ˜ω(˜‘j). Furthermore since M has only one non-zero entry per row and column, it defines a bijection ϑ between Lm and ˜Lm such that ωm(‘i, k) = ˜ωm(ϑ(‘i, k)). Finally, consider the following metric on M × N: dβ((x, s), (y, t)) = d(x, y) + βdδ(s, t). Using this metric we obtain, dβ((‘i, k), (˜‘j, s)) = d(‘i, ˜‘j) + βdδ(k, s) < δ + β. This finishes the proof. Remark 5.3.5. Index convention for M2 as defined in theorem 5.3.4. 134 i-th block  ··· . . . ... ... ... . . . ... ... s ... ... j-th block ··· ··· . . . ··· m2 . . . ··· k ··· ... ... ··· (j,js),(i,ik)  ··· . . . ... ... ... . . . ··· ··· . . . ··· . . . ··· Notation 5.3.6. From this point on we will denote the element (‘j, k) ∈ Lm as ‘j,k ∈ M. of (M, d). Furthermore d(cid:16) This notation allows us to make explicit the fact that we will be treating Lm as a multiset (cid:17) = d(‘j, ‘j) = 0 for any ‘j ∈ L and k, k0 ∈ N. ‘j,k, ‘j,k0 Using the projection π1 in Theorem 5.3.4 we have well defined maps ι : L → Lm ‘j 7→ ‘j,1 p : Lm → L ‘j,s 7→ π1(lj, s) = ‘j. Moreover, they induce simplicial maps for the Rips complex at scale α > 0 ι : Rα(L) → Rα(Lm) and p : Rα(Lm) → Rα(L). Definition 5.3.7. Given simplicial maps s, t : K → K0, they are said to be contiguous if for any simplex σ ∈ K then s(σ) ∪ t(σ) ∈ K0. Proposition 5.3.8. Let s, t : K → K0 be contiguous simplicial maps between simplicial complexes K and K0. Then s∗ = t∗ : Hq(K) → Hq(K0) for all q ≥ 0. Proof. See [51, Theorem 12.5]. Proposition 5.3.9. ιp : Rα(Lm) → Rα(Lm) is contiguous to IRα(Lm) : Rα(Lm) → Rα(Lm). And pι : Rα(L) → Rα(L) is contiguous to IRα(L) : Rα(L) → Rα(L). 135 Proof. Observe that pι IRα(L). On the other hand (cid:16)[‘j1, . . . , ‘jq](cid:17) = p (cid:16)[‘j1,s1,··· , ‘jq,sq](cid:17) = ι (cid:16)[‘j1,1, . . . , ‘jq,1](cid:17) = [‘j1, . . . , ‘jq]. Thus, pι = (cid:16)[‘j1,··· , ‘jq](cid:17) = [‘j1,1,··· , ‘jq,1]. ιp We want to show that [‘j1,1,··· , ‘jq,1, ‘j1,s1,··· , ‘jq,sq] ∈ Rα(Lm). Since both ‘j1,s1 and ‘j1,1 are copies of ‘j1, we have d(‘j1,s1, ‘j1,1) = 0. Then diam(cid:16)n o(cid:17) = diam(cid:16)n since [‘j1,s1,··· , ‘jq,sq] ∈ Rα(Lm). This finishes the proof. ‘j1,1,··· , ‘jq,1, ‘j1,s1,··· , ‘jq,sq o(cid:17) ‘j1,s1,··· , ‘jq,sq < α Proposition 5.3.9 together with Proposition 5.3.8 implies that ι∗p∗ = IH∗(Rα(Lm)) and p∗ι∗ = IH∗(Rα(L)), thus H∗(Rα(Lm)) ∼= H∗(Rα(L)) for all α > 0. We end this part with a Corollary: Corollary 5.3.10. If Lm is the augmented version of a landmark set L ⊂ M, then their Rips persistent homology satisfy bcdR n (Lm) = bcdR n (L) in all dimensions n. 5.3.2 Coordinates old and new We show next that (L, ω) and (Lm, ωm) create the same coordinates. For brevity, we will # i be the cochain map from Ci(Rα(L); R) to denote by ωjs, the weight ωm(‘j,s). Let p Ci(Rα(Lm); R) induced by p : Lm → L. Then for a η ∈ C1(Rα(L); R), its image p 1 (η) ∈ # C1(Rα(Lm); R) is (cid:16)[‘j, ‘j0](cid:17) η 0 if j 6= j0 if j = j0, # 1 (η)(j,s),(j0,t) := p # 1 (η)([‘j,s, ‘j0,t]) = p 136 and for a ζ ∈ C0(Rα(L); R), its image p 0 (ζ) ∈ C0(Rα(Lm); R) is # (cid:16)[‘j](cid:17) # 0 (ζ)([‘j,s]) = ζ # 0 (ζ)(j,s) := p p for all 1 ≤ s ≤ Mj and j. If ω is the probability weight on the set L, then the induced weights ωm on Lm are defined as in Section 5.3.1. Let να be the weight family on the edges of L. This induces the weight family νm ωjsωj0t ωj ωj0 να([‘j, ‘j0]) ωjsωjtρ(α) if j 6= j0 if j = j0 and s 6= t α on the edges of Lm defined as α (‘j,s, ‘j0,t) = νm  . These weight families induce inner products on C0(Rα(Lm); R) and C1(Rα(Lm); R) respec- tively. Recall that both τ = −d+ # 1 (η)) are minimum norm solu- tions to minimization problems. In particular, they minimize the pairs of objective functions (F, N) and (Fm, Nm) respectively: α (η) and τm = −(dm α )+(p να([‘j, ‘j0])(cid:16) ηj,j0 − dαχj,j0 (cid:17)2 F(χ) = X N(χ) =X [‘j ,‘ ‘j j0] ωj(χj)2 and α ([‘j,s, ‘j0,t])(cid:16) 1 (η)(j,s),(j0,t) − dm # α χ(j,s),(j0,t) p (cid:17)2 νm Fm(χ) = X Nm(χ) = X [‘j,s,‘ ] j0,t ωjs(χ(j,s))2 ‘j,s Lemma 5.3.11. For every ζ ∈ C0 (Rα(L); R), the objective functions F(ζ) and N(ζ) are equal to Fm(p # 0 (ζ)) respectively. # 0 (ζ)) and Nm(p Proof. For any ζ ∈ C0 (Rα(L); R), the objective function Fm is evaluated at its image 137 p # Fm(p 0 (ζ) ∈ C0 (Rα(Lm); R) as # α ([‘j,s, ‘j0,t])(cid:16) i νm  MjX ωjωj0 να([‘j, ‘j0])(cid:16) Mj0X 0 (ζ)) = Xh = X ‘j,s,‘j0,t ωjsωj0t s=1 t=1 p [‘j ,‘j0] 1 (η)(j,s),(j0,t) − (p # 0 (ζ)(j0,t) − p # ηj,j0 − (ζj0 − ζj)(cid:17)2  0 (ζ)(j,s))(cid:17)2 # where the outermost sum is over all distinct edges [‘j, ‘j0] and the contribution of all terms of the form p # 0 (ζ)(j,s) is zero. The above sum becomes 0 (ζ)(j,t) − p # # 1 (η)(j,s),(j,t) and p X [‘j ,‘j0] να([‘j, ‘j0])(cid:16) ηj,j0 − (ζj0 − ζj)(cid:17)2 which is just F(ζ). Similarly, Nm(p which is just N(ζ). 0 (ζ)) = X # ‘j,s 0 (ζ)(j,s))2 = X # ‘j,s ωjs(ζj)2 =X ‘j ωj(ζj)2 ωjs(p Proposition 5.3.12. The solution τm to the minimization of Fm is just p # 0 (τ). That is, (τm)(j,s) := (τm)([‘j,s]) = τ (cid:16)[‘j](cid:17) for all j and 1 ≤ s ≤ Mj. Consequently, θm = p # 1 (η) + (dm α )(τm) is (θm)(j,s),(j0,t) := θm([‘j,s, ‘j0,t]) = (cid:16)[‘j, ‘j0](cid:17) θ 0 if j 6= j0 if j = j0. Proof. To show that they are the same, we need to show that the two minimization problems are equivalent. Recall that τm = argmin χ∈C0(Rα(Lm);R) X [‘j,s,‘j0,t] α ([‘j,s, ‘j0,t])(cid:16) νm 1 (η)(j,s),(j0,t) − (χ(j0,t) − χ(j,s))(cid:17)2 # p . 138 For each χ ∈ C0(Rα(Lm); R), observe that the objective function evaluation (cid:17)2 1 (η)(j,s),(j0,t) − dm # 1 (η)(j,s),(j0,t) − (χ(j0,t) − χ(j,s))(cid:17)2 ηj,j0 − (χ(j0,t) − χ(j,s))(cid:17)2 Fm(χ) = X = X ≥ X α χ(j,s),(j0,t) [‘j,s,‘j0,t] [‘j,s,‘j0,t] νm # p p  νm ωjsωj0t α ([‘j,s, ‘j0,t])(cid:16) α ([‘j,s, ‘j0,t])(cid:16)  MjX Mj0X να([‘j, ‘j0])(cid:16)  MjX να([‘j, ‘j0]) s=1 t=1 ηj,j0 ωjωj0 να([‘j, ‘j0])(cid:16) (cid:17)2 Mj0X  MjX ωjsωj0t ωjωj0 Mj0X s=1 t=1 s=1 t=1 να([‘j, ‘j0])2ηj,j0 [‘j ,‘j0] X [‘j ,‘j0] + X − X [‘j ,‘j0] [‘j ,‘j0]   . (χ(j0,t) − χ(j,s))2 ωjsωj0t ωjωj0 (χ(j0,t) − χ(j,s)) Expanding the square term give us Now for the second term, we use Lyapunov’s inequality; in particular, that the expected value of a squared random variable is at least the square of the expected value of the random variable. ωjs ωj s=1  MjX MjX 139 να([‘j, ‘j0])(cid:16) να([‘j, ‘j0]) ηj,j0 (cid:17)2  MjX s=1 j0] [‘j ,‘ ≥ X + X − X [‘j ,‘ j0] [‘j ,‘ j0] χ(j,s) − j0X M t=1 2  ωj0t ωj0 χ(j0,t) j0X ωj0t ωj0 χ(j0,t) t=1 M  να([‘j, ‘j0])2ηj,j0 χ(j,s) − ωjs ωj where the third term is a mere rearrangement. Define a 0-cochain ζ ∈ C0 (Rα(L); R) as ζj := ζ([‘j]) = ωjs ωj χ(j,s). s=1 Then its image p 0 (ζ) ∈ C0 (Rα(Lm); R) is # # 0 (ζ)(j,s) := p p 0 (ζ)(cid:16)[‘j,s](cid:17) = # MjX s=1 ωjs ωj χ(j,s) for all j and 1 ≤ s ≤ Mj. Therefore, for each χ, we have a found a ζ satisfying Fm(χ) ≥ Fm(p 0 (ζ)) = F(ζ) ≥ F(τ) = Fm(p # # 0 (τ)) where the two equalities follow from lemma 5.3.11. Since p χ, it is indeed the minimizer of Fm. Furthermore, # 0 (τ) is independent of choice of ωjs(χ(j,s))2 =X ωj ‘j  MjX s=1  . ωjs ωj (χ(j,s))2 ‘j,s Nm(χ) = X  MjX ωj ωjs ωj s=1 2 (χ(j,s)) By Lyapunov’s inequality, Nm(χ) ≥X ‘j =X ‘j ωj(ζj)2 = N(ζ) ≥ N(τ) = Nm(p # 0 (τ)) where ζ is as defined above. Thus, p # 0 (τ) indeed minimizes Nm as well. Therefore, τm := (dm α )+p # 1 (η) = p # 0 (τ). Consequently, as desired. (θm)(j,s),(j0,t) = p # 1 (η)(j,s),(j0,t) + dm α (τm)(j,s),(j0,t) # 1 (dα(τ))(j,s),(j0,t) = ηj,j0 + p = ηj,j0 + dα(τ)j,j0 = θj,j0 We define a partition of unity {ϕm(j,s)}(j,s) subordinate to the cover the same fashion the original partition {ϕj}j was defined: (cid:26) (cid:27) in (j,s) (‘(j,s)) B α2 ϕm(j,s)(b) = NP j=1 ωjsφ(α − d(‘j,s, b)) MjP ωjsφ(α − d(‘j,s, b)) s=1 . 140 for all j and 1 ≤ s ≤ Mj. Note that if the increasing Lipschitz function used here is the # same as the one in ϕj, the right hand side is just ωjs 1 (η), τm, θm, ωj and partition of unity {ϕm(j,s)}(j,s), we get circular coordinates: ϕj(b). With cocycle p (‘(j,s)) 3 b → exp B α2 ϕm(r,t)(b)(θm)(j,s),(r,t) 2πi (τm)(j,s) + X (r,t)  .  We conclude in the next theorem that these coordinates agree with the coordinates generated from the landmark set L. Theorem 5.3.13. For all b ∈ B α2 (‘j), every j, and every 1 ≤ s ≤ Mj we have that 2πi (τm)(j,s) + X (r,t) exp ϕm(r,t)(b)(θm)(j,s),(r,t) (  = exp  τj +X r 2πi !) ϕr(b)θj,r That is, the circular coordinates induced by the landmark sets L and Lm are equal. Proof. By Proposition 5.3.12, (τm)(j,s) = τj and (θm)(j,s),(j0,t) = θj,j0. By our choices of partition of unity, we have that X ϕm(r,t)(b)(θm)(j,s),(r,t) =X MrX ϕr(b)θj,r =X r ωrt ωr ϕr(b)θj,r t=1 for all r and 1 ≤ t ≤ Mr. This finishes the proof. (r,t) r 5.3.3 Wasserstein stability In this section, we combine the previous results to prove Wasserstein stability theorem 5.3.15 for circular coordinates. We begin this section with a lemma relating the Hodge Laplacian matrix LH to another such matrix defined as: MiP ˜νm2α−2δ([˜‘i,t, ˜‘j,s]) Lm H((j, s), (k, t)) =  P √ ωjsωkt 1 ωjs − ˜ν2α−2δ([˜‘j,s,˜‘k,t]) 1≤i≤N t=1 if j = k if j 6= k. For any matrix A, let e(A) denote the set of distinct eigenvalues. 141 Lemma 5.3.14. Let Lm be the augmented landmark set associated to any L. If LH and Lm are Hodge Laplacians for C0(Rα(L); R) and C0(Rα(Lm); R) respectively for any α, then H e (Lm H) ⊂ e (LH) . Proof. Let Λ be an eigenvalue of Lm H. Then Lm HX = ΛX for some X =  x11 ... x1M1 ... xN1 ... xN MN  , (5.5) where X is an eigenvector for Λ. Therefore, for all 1 ≤ j ≤ N, and 1 ≤ s ≤ Mj, and i = M1 + ··· + Mj−1 + s, (Lm HX)i = (ΛX)i = Λxjs. (5.6) By definition of Lm H and X, we obtain that Λxjs is equal to the terms on the left hand side: (cid:16) MkX MkX α − d(‘j,s, ‘k,t)(cid:17) xjs +X (cid:17)1 2 ρ (α) xjt − X + X (cid:16) 2 ρ (cid:17)1 α − d(‘j,s, ‘k,t)(cid:17) xkt −X ωjtρ (α) xjs. ωjsωkt ωjsωjt k6=j t=1 ωktρ t6=s (cid:16) (cid:16) k6=j t=1 t6=s Adding and subtracting the term xjsωjsρ(α), the above can be compactly written as − NX MkX (cid:16) k=1 t=1 (cid:17)1 2 ρ (cid:16) α − d(‘j,s, ‘k,t)(cid:17) xkt + ωjsωkt NX MkX k=1 t=1 (cid:16) α − d(‘j,s, ‘k,t)(cid:17) xjs ωktρ 142 . Multiplying this term by ωj ωjs !1 2 MjX s=1 ωj Algebraic rearrangement allows the right hand side to be written as Λxjs = + (cid:16) 2 ωjs ωj 1 2 (cid:16) (cid:16) (cid:16) xjs xkt xkt t=1 2 ρ s=1 ωj s=1 ωj 2 2 2 ρ 2 ρ ωktρ   k=1 t=1 k=1 t=1 ωjsωkt !1 2  (cid:18) ωjs (cid:19)1 2 and adding for all 1 ≤ s ≤ Mj, we obtain ωjs !1 MjX ωjs !1 MjX α − d(‘j,s, ‘k,t)(cid:17)  ωkt − NX (cid:17)1 MkX  NX α − d(‘j,s, ‘k,t)(cid:17) MkX MkX !1 α − d(‘j,s, ‘k,t)(cid:17) (ωk) (cid:16)   α − d(‘j,s, ‘k,t)(cid:17)MkX (cid:16) MkX α − d(‘j,s, ‘k,t)(cid:17) (ωk) (cid:16) α − d(‘j,s, ‘k,t)(cid:17)MkX  NX (cid:18) ωjs (cid:19)1 2 for each j, makes this α − d(‘j,s, ‘k,t)(cid:17) (cid:16) α − d(‘j,s, ‘k,t)(cid:17) ωjs (cid:17)1 ωjs !1   NX  ωjs !1 MkP α − d(‘j,s, ‘k,t)(cid:17) (ωk) α − d(‘j,s, ‘k,t)(cid:17) (cid:16) ωkt   ωkt = ωk, letting yj := 1 2 yk + NX yj = (LHY)j MjP NX  !1 2 yk +  yjρ (cid:16) ωkρ k=1 k=1 xjs s=1 ρ k=1 xkt t=1 ωkt t=1 ωkt t=1 t=1 (cid:16) ωk ωk ρ 2 ωk ωj 1 2 xjs ωj ωjs 1 (ωj) 2 xjs ωj s=1 This is equal to MjX MjX s=1 − + k=1 k=1  NX  NX  MjX  MjX s=1 s=1 − + MjP Since NX ωjs = ωj and (cid:16) (cid:17)1 s=1 − (ωj) (cid:16) = − X k=1 ωjωk 1 2 ρ 2 ρ k6=j where Y is the N × 1 vector This yields  MjX s=1 (LHY)j = Λ (5.7)  = Λyj = ΛYj k=1  .  y1 ... yN Y = ωjs !1 2 ωj xjs 143 which implies that Λ is an eigenvalue for LH. Therefore, e (Lm H) ⊂ e (LH) . Now, we prove the Wasserstein stability theorem for circular coordinates. Theorem 5.3.15. If (L, ω) and (˜L, ˜ω) are two weighted landmarks sets satisfying dW,∞((L, ω), (˜L, ˜ω)) < δ, and if h and ˜h are the associated circular valued functions, then (cid:17) Lρ (λ2)2 +  φ(α − δ) (cid:16) ||h − ˜h||∞ ≤ )δ ( φ α − δ − r˜L min 8πkθk∞ min j ωj, min j ˜ωj  . Lφ φ (α − rL) Proof. By theorem 5.3.13, we have |h(b) − ˜h(b)| = |hm(b) − ˜hm(b)| for each b ∈ M. The new landmark sets (Lm, ωm) and (˜Lm, ˜ωm) are in a weight preserving bijective correspondence. Hence, by equation 5.4 in the proof of the geometric stability theorem 5.2.7, φ(α − δ) ψm(b) where Λ2 is the smallest non-zero eigenvalues of Lm H. Recall that ||θm||∞ = ||θ||∞, and observe that ϕm(b) = ϕ(b) and ψm(b) = ψ(b). Moreover, by Lemma 5.3.14, if Λ2 are λ2 are the smallest non-zero eigenvalues of Lm H and LH respectively, then Λ2 ≥ λ2. Combining the above, we obtain |hm(b) − ˜hm(b)| ≤ 8πkθmk∞δ (Λ2)2 + Lφ ϕm(b) ! Lρ An argument analogous to the proof of Theorem 5.2.7 yields uniform bounds for all b |h(b) − ˜h(b)| ≤ 8πkθk∞δ ||h − ˜h||∞ ≤ min This finishes the proof. ( 8πkθk∞ min j ωj, min j ˜ωj ! ψ(b) φ(α − δ)  φ(α − δ) (cid:16) φ α − δ − r˜L Lρ (λ2)2 + Lφ ϕ(b) (cid:17) Lρ (λ2)2 + . )δ  Lφ φ (α − rL) 144 5.4 Example & Discussion In this section, we demonstrate circular coordinates through examples. The first example compares circular coordinates generated from two landmark sets that are close in the Wasser- stein sense, while the second example is designed to clearly motivate the use of Wasserstein distance to compare landmarks sets. Example 5.4.1. We start with a dataset X with 1000 points sample around a unit circle with Gaussian noise of 0.5. We first select the “blue” landmark set with 40 points by maxmin sampling. We define the “red” landmark set by choosing the respective nearest neighbours of the “blue” landmarks. These two landmark sets can be used to create the two associated circle-valued functions hred and hblue. See Figure 1.4 for the setup and the results. In the rightmost figure, we plot the pair (hred(b), hblue(b)) for each b ∈ X.The closer the curve is to the perfect diagonal, the closer the two functions are. Figure 5.2: An example demonstrating stability of Circular Coordinates: (Left) The data set X of 1000 points sampled around a circle, with two different sets of 40 landmarks (Middle). For each of these sets, we obtain a function that assigns to each data point in X a circular coordinate. (Right) We see a comparison of the two coordinate functions. Example 5.4.2. To demonstrate the drawbacks of comparing landmarks with Hausdorff distance, we present a simple example in which landmarks are replicated at a single spot, so as to have zero Hausdorff distance. Our dataset is generated to lie uniformly around the unit o16 circle, perturbed by some small Gaussian noise. See Figure 5.3. The first set of landmarks j=1. The second set of landmarks ˜L is created the L is selected via maxmin, say L = n ‘j 145 following way: ˜‘j = ‘j for j = 1, ..., 15 ˜‘j = ‘16 for j = 16, ..., 15 + n that is, the final landmark ‘16 is replicated n − 1 times. For each of the landmark sets, we construct circular coordinates in two fashions to compare them. In the first case, we simply ignore any notion of weights and calculate the circular coordinates as originally described in [55]. In the second case, landmarks are weighted so that Wasserstein distance dW,∞((L, ω), (˜L, ˜ω)) is 0. In particular, ωj = 1/16 for every landmark ‘j, while ˜ωj = 1/16 for j = 1, ...15 and ˜ωj = 1/(16n) for i = 16, ..., 15 + n. In both cases, the circular coordinates built on L are the same, but the coordinates on ˜L change between the two scenarios. In Fig. 5.3, we see that the first case yields growing error between the pair of circular coordinates, while in the second case the circular coordinates remain static regardless of how many replicated landmarks are made. Figure 5.3: Comparison between Hausdorff and Wasserstein noise: (Left) Example of the dataset in black and 16 landmarks shown in blue. (Right) Comparison of the number of replicates against the incurred error between the circular coordinates. Red shows the ini- tial ‘Zero-Hausdorff-distance’ pair, while green shows the second ‘Zero-Wasserstein-distance’ pair. Example 5.4.2 demonstrates that Wasserstein distance is the appropriate way to compare landmarks. 146 BIBLIOGRAPHY 147 BIBLIOGRAPHY [1] Michał Adamaszek and Henry Adams. The vietoris–rips complexes of a circle. Pacific Journal of Mathematics, 290(1):1–40, 2017. [2] John C Baez and James Dolan. Higher-dimensional algebra and topological quantum field theory. Journal of Mathematical Physics, 36(11):6073–6105, 1995. [3] Michael Barr and Charles Wells. Category theory for computing science, volume 1. Prentice Hall New York, 1990. [4] Ulrich Bauer. Ripser. URL: https://github.com/Ripser/ripser, 2016. [5] Ulrich Bauer, Michael Kerber, and Jan Reininghaus. Clear and compress: Computing persistent homology in chunks. In Topological methods in data analysis and visualization III, pages 103–117. Springer, 2014. [6] Ulrich Bauer, Michael Kerber, and Jan Reininghaus. Distributed computation of persis- tent homology. In 2014 proceedings of the sixteenth workshop on algorithm engineering and experiments (ALENEX), pages 31–38. SIAM, 2014. [7] Ulrich Bauer and Michael Lesnick. Induced matchings and the algebraic stability of persistence barcodes. Journal of Computational Geometry, 6:162–191, 2015. [8] Hans J. Baues and Ronald Brown. On relative homotogy groups of the product filtration, the james construction, and a formula of hopf. Journal of pure and applied algebra, 89(1- 2):49–61, 1993. [9] Jean-Daniel Boissonnat and Clément Maria. Computing persistent homology with var- ious coefficient fields in a single pass. Journal of Applied and Computational Topology, 3(1-2):59–84, 2019. [10] Glen E Bredon. Topology and geometry, volume 139. Springer Science & Business Media, 2013. [11] Ronald Brown. A new higher homotopy groupoid: the fundamental globular omega- groupoid of a filtered space. Homology, Homotopy and Applications, 10(1):327–343, 2008. [12] Peter Bubenik and Nikola Milicevic. Homological algebra for persistence modules. arXiv preprint arXiv:1905.05744, 2019. [13] Peter Bubenik and Jonathan A. Scott. Categorification of persistent homology. Discrete & Computational Geometry, 51(3):600–627, 2014. [14] Gunnar Carlsson and Benjamin Filippenko. Persistent homology of the sum metric. Journal of Pure and Applied Algebra, 224(5):106244, 2020. 148 [15] Gunnar Carlsson, Tigran Ishkhanov, Vin De Silva, and Afra Zomorodian. On the local behavior of spaces of natural images. International journal of computer vision, 76(1):1– 12, 2008. [16] Gunnar Carlsson, Gurjeet Singh, and Afra Zomorodian. Computing multidimensional persistence. In International Symposium on Algorithms and Computation, pages 730– 739. Springer, 2009. [17] Gunnar Carlsson and Afra Zomorodian. The theory of multidimensional persistence. Discrete & Computational Geometry, 42(1):71–93, 2009. [18] Frédéric Chazal, David Cohen-Steiner, Marc Glisse, Leonidas J Guibas, and Steve Y In Proceedings of the Oudot. Proximity of persistence modules and their diagrams. twenty-fifth annual symposium on Computational geometry, pages 237–246. ACM, 2009. [19] Frédéric Chazal, Vin De Silva, Marc Glisse, and Steve Oudot. The structure and stability of persistence modules. Springer, 2016. [20] Chao Chen and Michael Kerber. Persistent homology computation with a twist. In Proceedings of the 27th European Workshop on Computational Geometry, volume 11, pages 197–200, 2011. [21] René Corbet and Michael Kerber. The representation theorem of persistent homology revisited and generalized. arXiv preprint arXiv:1707.08864, 2017. [22] William Crawley-Boevey. Decomposition of pointwise finite-dimensional persistence modules. Journal of Algebra and its Applications, 14(05):1550066, 2015. [23] Vin De Silva and Robert Ghrist. Coverage in sensor networks via persistent homology. Algebraic & Geometric Topology, 7(1):339–358, 2007. [24] Vin De Silva, Dmitriy Morozov, and Mikael Vejdemo-Johansson. Dualities in persistent (co) homology. Inverse Problems, 27(12):124003, 2011. [25] Vin De Silva, Dmitriy Morozov, and Mikael Vejdemo-Johansson. Persistent cohomology and circular coordinates. Discrete & Computational Geometry, 45(4):737–759, 2011. [26] Alireza Dirafzoon, Alper Bozkurt, and Edgar Lobaton. Geometric learning and topo- logical inference with biobotic networks. IEEE Transactions on Signal and Information Processing over Networks, 3(1):200–215, 2016. [27] Daniel Dugger. A primer on homotopy colimits. http://pages.uoregon.edu/ddugger/, 2008. preprint available at [28] Herbert Edelsbrunner, David Letscher, and Afra Zomorodian. Topological persistence and simplification. In Proceedings 41st annual symposium on foundations of computer science, pages 454–463. IEEE, 2000. [29] RE Edwards. Fourier Series: A Modern Introduction, volume 1. Springer Science & Business Media, 2012. 149 [30] Samuel Eilenberg and Saunders MacLane. Acyclic models. American journal of math- ematics, 75(1):189–199, 1953. [31] Samuel Eilenberg and Norman Steenrod. Foundations of algebraic topology, volume 2193. Princeton University Press, 2015. [32] Samuel Eilenberg and Joseph A Zilber. On products of complexes. American Journal of Mathematics, 75(1):200–204, 1953. [33] Saba Emrani, Thanos Gentimis, and Hamid Krim. Persistent homology of delay em- IEEE Signal Processing Letters, beddings and its application to wheeze detection. 21(4):459–463, 2014. [34] Hitesh Gakhar, Joshua L. Mike, Jose A. Perea, and Luis Polanco. Stability of multiscale K(G,1) coordinates. In preparation, 2020. [35] Hitesh Gakhar and Jose A. Perea. Künneth formulae in persistent homology. arXiv preprint arXiv:1910.05656, 2019. [36] Hitesh Gakhar and Jose A. Perea. Sliding window embeddings of quasiperiodic func- tions. In preparation, 2020. [37] Jerry P Gollub and Harry L Swinney. Onset of turbulence in a rotating fluid. Physical Review Letters, 35(14):927, 1975. [38] Loukas Grafakos. Classical fourier analysis, volume 2. Springer, 2008. [39] Allen Hatcher. Algebraic topology. Cambridge University Press, 2005. [40] Peter J Hilton and Urs Stammbach. A course in homological algebra, volume 4. Springer Science & Business Media, 2012. [41] Morris W Hirsch. Differential topology, volume 33. Springer Science & Business Media, 2012. [42] Edmund Hlawka, Johannes Schoissengeier, and Rudolf Taschner. Geometric and ana- lytic number theory. Springer Science & Business Media, 2012. [43] Dale Husemoller. Fibre bundles, volume 5. Springer, 1966. [44] Ian Jolliffe. Principal component analysis. Springer, 2011. [45] Firas A Khasawneh and Elizabeth Munch. Chatter detection in turning using persistent homology. Mechanical Systems and Signal Processing, 70:527–541, 2016. [46] Firas A Khasawneh, Elizabeth Munch, and Jose A Perea. Chatter classification in IFAC-PapersOnLine, turning using machine learning and topological data analysis. 51(14):195–200, 2018. [47] Edward N Lorenz. Deterministic nonperiodic flow. Journal of the atmospheric sciences, 20(2):130–141, 1963. 150 [48] Saunders Mac Lane. Categories for the working mathematician, volume 5. Springer Science & Business Media, 2013. [49] Facundo Mémoli. Gromov–wasserstein distances and the metric approach to object matching. Foundations of Computational Mathematics, 11:417–487, 08 2011. [50] John Milnor. Construction of universal bundles, ii. Annals of Mathematics, pages 430–436, 1956. [51] James R. Munkres. Elements of Algebraic Topology. Addison Wesley Publishing Com- pany, 1984. [52] Steve Y Oudot. Persistence theory: from quiver representations to data analysis, volume 209. American Mathematical Society Providence, RI, 2015. [53] Jose A. Perea. Persistent homology of toroidal sliding window embeddings. In 2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 6435–6439. IEEE, 2016. [54] Jose A Perea. Multiscale projective coordinates via persistent cohomology of sparse filtrations. Discrete & Computational Geometry, 59(1):175–225, 2018. [55] Jose A Perea. Sparse circular coordinates via principal Z-bundles. arXiv preprint arXiv:1809.09269, 2018. [56] Jose A. Perea. A brief history of persistence. Morfismos, 23(1):1–16, 2019. [57] Jose A. Perea. Topological time series analysis. Notices of the American Mathematical Society, 66(5), 2019. [58] Jose A Perea, Anastasia Deckard, Steve B Haase, and John Harer. Sw1pers: Sliding windows and 1-persistence scoring; discovering periodicity in gene expression time series data. BMC bioinformatics, 16(1):257, 2015. [59] Jose A. Perea and John Harer. Sliding windows and persistence: An application of topological methods to signal analysis. Foundations of Computational Mathematics, 15(3):799–838, 2015. [60] Luis Polanco and Jose A Perea. Coordinatizing data with lens spaces and persistent cohomology. arXiv preprint arXiv:1905.00350, 2019. [61] Leonid Polterovich and Egor Shelukhin. Autonomous hamiltonian flows, hofer’s geom- etry and persistence modules. Selecta Mathematica, 22(1):227–296, 2016. [62] Leonid Polterovich, Egor Shelukhin, and Vukašin Stojisavljević. Persistence modules with operators in morse and floer theory. Moscow Mathematical Journal, 17(4):757–786, 2017. [63] Graeme Segal. Classifying spaces and spectral sequences. Publications Mathématiques de l’IHÉS, 34:105–112, 1968. 151 [64] Lewis Shilane. Filtered spaces admitting spectral sequence operations. Pacific Journal of Mathematics, 62(2):569–585, 1976. [65] David I Spivak. Category theory for the sciences. MIT Press, 2014. [66] Jeffrey Strom. Modern classical homotopy theory, volume 127. American Mathematical Society, 2011. [67] Floris Takens. Detecting strange attractors in turbulence. In Dynamical systems and turbulence, Warwick 1980, pages 366–381. Springer, 1981. [68] Christopher J Tralie and Matthew Berger. Topological eulerian synthesis of slow motion In 2018 25th IEEE International Conference on Image Processing periodic videos. (ICIP), pages 3573–3577. IEEE, 2018. [69] Christopher J Tralie and Jose A Perea. (quasi)-periodicity quantification in video data, using topology. SIAM Journal on Imaging Sciences, 11(2):1049–1077, 2018. [70] Michael Usher and Jun Zhang. Persistent homology and floer–novikov theory. Geometry & Topology, 20(6):3333–3430, 2016. [71] James W Vick. Homology theory: an introduction to algebraic topology, volume 145. Springer Science & Business Media, 2012. [72] Hubert Wagner, Chao Chen, and Erald Vuçini. Efficient computation of persistent homology for cubical data. In Topological methods in data analysis and visualization II, pages 91–106. Springer, 2012. [73] Volkmar Welker, Günter M Ziegler, and Rade T Živaljević. Homotopy colimits– comparison lemmas for combinatorial applications. Journal für die reine und ange- wandte Mathematik (Crelles Journal), 1999(509):117–149, 1999. [74] Inka Wilden, Hanspeter Herzel, Gustav Peters, and Günter Tembrock. Subharmonics, biphonation, and deterministic chaos in mammal vocalization. Bioacoustics, 9(3):171– 196, 1998. [75] Boyan Xu, Christopher J Tralie, Alice Antia, Michael Lin, and Jose A Perea. Twisty takens: A geometric characterization of good observations on dense trajectories. Journal of Applied and Computational Topology, 3(4):285–313, 2019. [76] Afra Zomorodian and Gunnar Carlsson. Computing persistent homology. Discrete & Computational Geometry, 33(2):249–274, 2005. 152