Topological Data Analysis, CPSC 531F Page, Spring 2025

This page concerns CPSC 531F, Winter 2024-25, Term 2. This is a topics course in TDA (Topological Data Analysis).

This page has the most up-to-date information on the course(s) and supersedes any other document.

Materials below may have errors! Errors will be corrected either here or in class. If you are not attending my classes: use these materials at your own risk!

This entire webpage is currently (December 2024) UNDER CONSTRUCTION.

News March 27, 2025: I've just posted a short document with some comments on the homework and handout(s). The handout An Introduction to Simplicial Homology now has an exercise on Δ-complexes, and will include a section on barcodes.
Feb 28, 2025: The latest version of An Introduction to Simplicial Homology has a new Chapter 9 on topological spaces, and singular homology. Exercises are being added.
Feb 12, 2025: New problems for February added to notes; some clarifications and corrections to the January problems.
Feb 3, 2025: UBC is open, but in-person classes have been cancelled. Class today and office hours will be given via Zoom only, which you can access on UBC Canvas.
Feb 1, 2025: Diversity News: February is Black History Month in Canada. For example, currently within Canada you can watch I Am Not Your Negro (based on a manuscript of James Baldwin), by creating an account (just the free version) on CBC Gem.
Jan 31, 2025: The latest version of An Introduction to Simplicial Homology now has an Appendix C where I am collecting all the facts from linear algebra that we will use. I've rewritten the notes to follow what we did in class more closely this week; as of today we began the proof of the Mayer-Vietoris sequence, Section 5.4.
Jan 22, 2025: The homework problems in Appendix A of An Introduction to Simplicial Homology are now numbered A.1, A.2, etc., instead of 1,2, etc. The problems and their order is unchanged.
Jan 12, 2025: Some homework problems from last week have been gathered in Appendix A of An Introduction to Simplicial Homology.
Jan 5, 2025: Our class has been moved to Math Building, Room 203. It has plenty of room for all registered and currently waitlisted students.
Jan 2, 2025: Happy New Year! Some students have been waitlisted because the current classroom size is too small. I'm requesting a larger classroom. [I currently can't find a reasonable way to contact all the waitlisted students.]
In-Person and Remote Learning Classes will be given in-person, except when UBC requires us to teach remotely.
Generally speaking, classes will not be recorded. Board scans will be posted below.
Remote teaching will be given via Zoom, the links will be available at Canvas at UBC.
TDA (topological data analysis) This is a "topics course" in TDA (topological data analysis). TDA is an umbrella term for a number of methods to analyze data that use algebraic topology. One idea is that if you have a point cloud of data in a metric space (e.g., ℝⁿ), then you can build a sequence of simplicial complexes C(d) depending on a distance parameter, d, between pairs of points (the so-called Vietoris-Rips complex). You can then look for "persistent" homology group elements (i.e., elements in H_i(C(d)), for some i and for d "small," whose image in H_i(C(d')) for d' "large" is nonzero and therefore "persists" from d to d').

One bizarre aspect of some otherwise excellent articles in this field is that they contain a long and needless review of standard homological algebra, discrete Hodge theory, etc. (which will probably make sense to you only if you already know this material). Hence there seems to be a large gap (or at least perceived gap) between those who might apply TDA and those who have a good mathematical understanding of TDA's foundations. This course intends to fill this gap, providing an introduction to some of the mathematical foundations of TDA.

However, I am currently (as of December 2024) unfamiliar with many practical aspects of TDA, including the algorithms, the common datasets, etc. A secondary goal of this course is to figure out some of this stuff together.
Prerequisites I assume you have seen or are willing to quickly teach yourself the following topics: linear algebra (abstract vector spaces, the spectral theorem for symmetric matrices, and both the above in the context of inner product spaces); some graph theory and combinatorics.

We will review what is meant by a topological space, a metric space, continuous maps, etc. Usually there is no harm in viewing everything taking place in subsets of ℝⁿ (where n is generally much larger than the dimension of spaces of interest).

We will review Jordan canonical form for matrices whose only eigenvalue is 0 (i.e., for nilpotent matrices). We will also review any other aspects of linear algebra needed; at some point we may need tools such as tensor products and wedge products.

I do not assume that you've seen (co)homology, homological algebra, or discrete Hodge theory. Introducing these ideas and providing intuition for the tools involved is part of the point of the course.
References I don't know of any good single reference for all the topics we will cover. However, at times we will recommend some parts of various books and articles. The references for this course have now been moved to our References and Resources webpage.
Handouts UNDER CONSTRUCTION!! I may give some handouts; some of these are my own notes to myself, and are therefore quite skeletal. THESE DOCUMENTS MAY DRASTICALLY CHANGE IN THE NEAR FUTURE, INCLUDING THE NOTATION AND SECTION STRUCTURE.
TDA Resources TDA Resources have now been moved to our References and Resources webpage.
Possible Topics Here is a "wish list" of topics; we will probably only cover a small subset, and we may add to this list.
  • Topological Spaces and Examples: metric spaces and topological spaces. Examples. (Continuous and smooth) n-manifolds. Differential forms in ℝⁿ; differential forms and de Rham cohomology. Δ-complexes and simplicial complexes. Simplicial homology and (some remarks about) singular homology. Divide and conquer: Mayer-Vietoris sequences, relative homology, etc. Isomorphism and homotopy equivalence.
  • The Barcode Theorem.
  • Graph Laplicians, both on vertices and on edges (brief mention of: applications to expanders, mixing on Markov chains), Mayer-Vietoris sequence for homology groups of graphs; classifying reversible Markov chains.
  • (Co)homology and Hodge theory on chains of finite dimensional inner product spaces:
  • Applications to Point Clouds:
  • Applications to something else:
Boards Scans The board scans will give you an idea of what we covered and how we are covering it.
  • Simplicial Complexes and Abstract Simplicial Complexes: Section 1 of TDA, Point Clouds, and Some Point Set Topologoy, and all of (the document in progress) An Introduction to Simplicial Homology. The textbook Elements of Algebraic Topology by Munkres has a lot of great examples for this first part of the course.
    Board scans: 01_06: Admin stuff. Simplices in R^N. Simplicial complexes in R^N. The rough idea of point clouds in TDA.
    01_08: Corrected definition of simplicial complex. Examples of vectors any 4 of which are in general position in R^3. Barycentric coordinates. Abstract simplicial complexes. Graphs and abstract simplicial complexes. Theorem (statement): any graph is the abstract simplicial complex of a simplicial complex in R^3 (not true in R^2 for the complete graph on 5 vertices).
    01_10: Every graph is the abstract simplicial complex of a simplicial complex in R^3: Proof: Fact 1: if K and K' are simplicies, then K intersect K' = span of vertices that lie in both, provided that any (two,three,four) vertices are mapped to vertices in R^3 that are in general position. Fact 2: Any vectors of the form (1,n,n^2,n^3) satisfy the general position requirements in Fact 1. Question: Why are simplicial complexes interesting? Answer 1: if simplicial complexes are allowed to "degenerate," then their homology won't agree with their simplicial homology. Next time: define simplicial homology.
    01_13: Graphs and abstract simplicial complexes. Formal R-linear combinations. 0-forms and 1-forms on a graph; definition of homology groups as the cokernel and kernel of the boundary operator. Betti numbers. Intuition that b_1(G)=dim(H_1(G)) is the number of "independent" cycles in a graph. Graph theoretic definition of cycle in a graph. Next time: b_0(G) = # connected components, and b_0-b_1 equals chi(G)=|V|-|E|.
    01_15: Summary of what we will do in graph theory with H_0 and H_1 (likely on Friday). Simplicial homology for complexes of dimension 2: intuition of H_1 as "number of 1-holes" in R^2 for planar simplicial complexes. Definition of ∂_2 on (abstract 2-simplicies). ∂_1 ∂_2 = 0. H_2,H_1,H_1 for 2-dim simplicial complexes. General definition of ∂_i .
    01_17: Some examples of simplicial complexes. Cones and (statement regarding) their homology groups. Begin discussion of simplicial H_0 of a graph and of simplicial complexes.
    01_20: Simplicial homology of K_4, and statement of Homework Problem 6: tedious calculations to show you that it is worth having some easier ways and tools to compute homology groups rather than doing things by hand. Idea of Homework Problem 7: Z_1(G) = ker(∂_1) really comes from cycles in a graph. ∂_1 for the complete graph. Remark ∂_1∂_1^T is the ``graph Laplacian,'' and connection to adjacency matrix; example in this case. Formal computations regarding ∂_1(K_4).
    01_22: Simplicial homology of <{A,B,C}>, via brute force linear algebra. Reminder about quotient spaces W/U and "mod U" notation. Simplicial homology of a cone: statement and outline of proof.
    01_24: Explanation about i-forms and homology groups "factoring through" connected components. Picture of a cone of an abstract simplicial complex. Defined suspension. Proof that cones have H_i=0 for i >= 1. Example: K = <{A},{B,C},{D}> , and L = Cone_P(K). Note that tau = [B,P]+[P,C]+[C,B] is a cycle. First step: clear out "non-P" terms: write [C,B] as equal to ∂_2[P,C,B] plus tau', where tau' has terms with only P's. Step 2: [B,P]+[P,C]+tau' is already = 0 (!). Remark: When we speak of homotopy equivalence, we will "demystify" this method.
    01_27: Brief discussion of Path Topology in Molecular and Materials Science (by Chen et al., 2023) (which has many nice references such as this one on molecular structures, TDA and ML and this one on biomolecular data, and gives some "big picture" explanations). (The recent textbook Topological Data Analysis with Applications, by Carlsson and Vejdemo-Johansson, gives more applications. There is a regular meeting: TopoInVis (TDA in Visualization) of interest; the UBC library has some earlier (pre-IEEE) proceedings.) Review the algorithm from 01_24 (the theorem that H_i(cone)=0 is really an algorithm to take a closed i-form and find an (i+1)-form whose boundary it equals). Euler-characteristic. Start Mayer-Vietoris.
    01_29: More on Mayer-Vietoris: exact sequences; review of direct sums; R[S] (formal R-linear combinations of a set, S) lies in R[T] whenever S is a subset of T. The short exact sequence 0 to R[S_1 cap S_2] to R[S_1] oplus R[S_2] to R[S_1 cup S_2] to 0. What this has to do with i-forms.
    01_31: Verifying that the sequence 0 to R[S_1 cap S_2] to R[S_1] oplus R[S_2] to R[S_1 cup S_2] to 0 is actually exact. Define short exact sequence, exactness in first (last) position equivalent to first arrow is injective (surjective). Statement that the resulting diagrams of 0-forms and 1-forms for G_1 cap G_2, G_1,G_2, G is commutative.
    02_03: Due to a technical issue, this lecture was given to an empty class (while students were in another Zoom room with the same id). Hence I will not assume that you've seen this class... Construction of the Mayer-Vietoris sequence for graph homology from two short exact sequences.
    02_05: Construction of the commutative diagram for the Mayer-Vietoris sequence. The first two maps in the long exact sequence, mapping H_1 values. The last two mappings, mapping H_0 values; mapping of quotient spaces.
    02_07: More on mapping of quotient spaces: generalities and examples in modular arithmetic.
    02_10: Maps of quotient spaces associate with graph homology, with an example. A "diagram chasing" approach to maps between quotient spaces. A more general commutative square, and its induced maps on cokernels.
    02_12: The "delta" map in the Mayer-Vietoris sequence for graphs, with examples, including a number of "diagram chases."
    02_14: The Mayer-Vietoris sequence for abstract simplicial complexes. Review of cones. The suspension of a complex. Computing the Betti numbers of a suspension via Mayer-Vietoris.
    02_24: Begin thinking "geometrically" about simplicial complexes. Define continuous maps and (wide-sense) neighbourhoods for subsets of R^n. Continuity and inverse images of neighbourhoods.
    02_26: More thinking "geometrically": cones and contractible sets. Open subsets in R^n and relatively open subsets. Topological spaces.
    02_28: Examples of topological spaces: the topological space constructed from an equivalence relation on a space X. RP^2 (projective space), and RP^2. The torus, T, as a quotient of [0,1]^2.
    03_03: Our goal: use maps Δ^n->X to build singular homology groups H_n^(sing)(X) defined for any topological space, that agree with simplicial homology of abstract simplicial complexes. Topology induced on a subspace; the product of two topological spaces. The geometric realization of a simplicial complex depends only on the abstract complex (a homework problem...).
    03_05: Singular homology: outline of main properties. Remarks on Homework in Appnedix B. Singular homology: singular n-simplicies of a topological space: maps Δ^n->X. Ordered n-simplicies. (n+1) faces of a map Δ^n->X, as maps Δ^(n-1)->X. Boundary of a singular simplex. The boundary map, ∂_n. Sample computation: ∂_1 ∂_2 = 0. Singular homology groups.
    03_07: Review of simplicial homology groups. f from X to Y gives map f_# on chains and f_* on homology groups. If X,Y are homeomorphic, then H_i(X) and H_i(Y) are isomorphic (via a homeomorphism). The Betti numbers of spheres and disks. The Brouwer fixed point theorem, and start of proof: if f from D^n to D^n has no fixed points, then we get a map g from D^n to Sphere^(n-1) that is the identity on Sphere^(n-1). So...
    03_10: Careful proof that g from last time is continuous. β_(n-1)(Sphere^{n-1}) >= β_(n-1)(D^n), hence there is no continuous g from D^n to Sphere^(n-1) such that (inclusion followed by g) is the identity on Sphere^(n-1). Generalization to when A subset of X is a retraction. Start: application to Markov matrices and stationary distribution.
    03_12: Δ^n and D^n are homeomorphic. Stochastic vectors and scaling vectors with non-negative components to be stochastic. The Brouwer fixed point theorem implies the existence of a Perron-Frobenius eigenvector and eigenvalue for non-neg matrices with non-zero columns. If M is irreducible, then claim: the P-F eigenvector bounds the absolute value of any other eigenvalue.
    03_14: Review directed graphs and adjacency matricies. The Fibonacci graph, the complete directed graph, the directed cycle, the path. If A has non-negative entries and A^k has all positive entries for some k, then for all i,j, the Perron-Frobenius eigenvalue = lim as m-> infinity of ((A^m)_(ij))^(1/m}.
    03_17: The (2,4)-RLL (run length limited) code and the (2,4)-RLL digraph. More generally, the (d,k)-RLL code. The justification of RLL codes from magnetic storage. The significance of the Perron-Frobenius eigenvalues for RLL codes, and Shannon's definition of capacity. Begin: linear, one-player games and equilibrium.
    03_19: Next few topics and comments on the homework. Some 2-player games. k-player games, mixed strategies, and Nash equilibrium. 1-player games and "Reward to Switch" vectors.
    03_21: 1-player games and "Reward to Switch" vectors: examples, intuition as iterative algorithms. Variants of Nash's Reward To Switch vectors. Main results for 1-player games, and proofs.
    03_24: The Betti numbers of a cartesian product (statement of theorem). Delta-complexes and their simplicial homology. Computation of the Betti numbers of a torus via Delta-complexes.
  • Topological Barcodes.
    Board scans:
    03_26: Point clouds; basic examples from Topological Persistence and Simplification, by Edelsbrunner, Letscher, and Zomorodian, 2002; (here is the preliminary FOCS 2000 version). Barcodes: examples of increasing cell complexes: which H_1 element is the "most persistent"? Example where there is "bad news."
    03_28: The point of "simplification" and "persistence" via some examples. Abstraction: strings of vector spaces, (i,j)-bars, direct sums, and isomorphisms of strings of vector spaces. Examples of non-uniqueness in (i,j)-bar decomposition.
    03_31: The "forward sweep" method: first consider the image of V^0 in all other vector spaces. First step: find a set of (0,n)-bars: assuming that such a bar decomposition exists, how to identify the (0,n)-bars; proof that these bars are linearly independent. Second step: find the (0,n-1)-bars.
    04_02: Homework dates. Example to illustrate ambiguity in choosing longest bar. Choosing (0,n)-bars, and general lemma regarding linear maps taking a set of vectors to independent vectors. Kernels K_{0,q} and general method to choose (0,q)-bars for all q. Surjectivity of maps V^{0 -> n-1} to V^{0 -> n} and number of (0,n-1)-bars.
    04_04: Construction of all (0,q)-bars for a string of vector spaces. Defining V^{n+1}=0 for the sake of uniformity of notation.
    04_07: Moving from (0,q)-bars to (1,q)-bars. "Phases" of the algorithm. Abstractly: a basis of a vector space relative to one of its subspaces. Independence of (0,q)- and (1,q)-bars in V^j for all j. Brief discussion of barcodes on pages 157 and 158 (in Chapter 2) of: Topological Data Analysis for Genomics and Evolution
Homework and Grades Homework will be assigned during lectures and organized into two or three sets, to be collected at regular interval(s) during the term. The third homework set may essentially be a small research project.

In my topics courses, grades have the following meaning (this is based on UBC Math guidelines):
  • 95% or higher (A+): student is strongly encouraged to pursue research in the area; the instructor will write a very strong letter of recommendation for the student.
  • 90% or higher (A+): the student is encouraged to pursue research in the area or a related one; the instructor will write an enthusiastic letter of recommendation for the student.
  • 85% to 89% (A): the student will be able to use some of the course material in another field of research; research in the area is not encouraged without significantly more background and study.
  • 80% to 84% (A-): the student has fulfilled department expectations of the graduate student.
  • 79% or below (B+ or below): the student has not fulfilled department expectations of the graduate student.
Piazza There may be an online discussion of this course on www.piazza.com. Details to come...
Diversity and Equity UBC is trying in earnest to encourage diversity and alleviate biases and inequities to which some members of its community are subjected; this includes, for example, UBC's Indian Residential School History and Dialogue Centre, privileged to work with the Musqueam First Nation; this also includes the Computer Science Department's various programs described on its Diversity in CS webpage.
I try to act reasonably free of bias; for example, I do not view sexual orientation or gender as set in stone from birth or as classified by some fixed, finite set of choices; I try to use language accordingly. I will undoubtedly goof upon occasion, and I welcome feedback on these and related matters.
Relevant Dates (Our) Class Starts: Monday, Jan 6. Drop/Withdrawl: Jan 17. Family Day + Feb Break: Feb 17-21. Last day of (our) class: Monday, April 7.
All homework, etc. is due on the last day of classes, Tuesday, April 8.

UBC CS Home| Joel Friedman Home| Course Materials