All posts by Mikael Vejdemo-Johansson

ATMCS7 Torino July 25-29

ATMCS7: 25-29 July 2016 -- Torino, Italy

We are excited to announce the 7th edition of Algebraic Topology: Computation, Methods, and Science (ATMCS), scheduled from 25-29 July 2016 in Torino, Italy! This conference is a joint effort of the Polytechnic University of Turin (Politecnico di Torino) and the ISI Foundation, to be hosted at the Politecnico.

We are now welcoming submissions for our Contributed sessions. For more information, please visit:
http://atmcs7.appliedtopology.org

The website is continually being updated with more logistical information, so be sure to check back often for updates. Don't hesitate to contact us if you have any questions, we are available at atmcs7@appliedtopology.org

Looking forward to seeing you in Torino in July!
- The ATMCS Team

Main Organizers for ATMCS7:
Vin de Silva, Pomona College, USA
Anthea Monod, Duke University, USA

Local Organizers:
Giovanni Petri, ISI Foundation, Italy
Francesco Vaccarino, ISI Foundation & Politecnico di Torino, Italy

PhD position at Queen Mary, University of London

PhD Studentship in Mathematics

We invite applications for a fully funded 3 years’ PhD studentship commencing in January 2016. The research project will deal with developing new topological and geometric algorithms for video data compression and with other problems of analysis of large data. The project will be sponsored by the Queen Mary, University of London and by the Penteract 28 and will be supervised by representatives of both institutions. The candidates must have basic knowledge of pure and applied mathematics; it is desirable that the candidates are familiar with geometry, topology, statistics, elements of computer science and data analysis.

The deadline for applications is: November 16, 2015.

The application procedure is described at
http://www.qmul.ac.uk/postgraduate/research/subjects/mathematical-sciences/index.html

For further enquiries please contact Prof. Michael Farber (M.Farber@qmul.ac.uk) or Dr Danijela Horak (danijela.horak@gmail.com)

Women in Computational Topology

Brittany Fasy writes:

Recently, a listserv for women in Computational Topology was initiated. The idea is that we can use this mailing list to remind each other about upcoming deadlines, find out who is going to SoCG or CCCG next year, etc. Feel free to encourage others (men or women) to join our network too! If you are interested in joining, send a blank email to <WinCompTop+subscribe@googlegroups.com>. If you have any trouble joining or posting to the listserv, please email Brittany <brittany@fasy.us>.

AATRN Seminar: Robert Ghrist

Today, the promised AATRN seminar series got started with Robert Ghrist as the inaugural speaker. His lecture, through WebEx, builds up the cellular sheaf perspective on networks with capacity, Max Flow / Min Cut, and the work done by Ghrist, Yasu Hiraoka, and Sanjeevi Krishnan on categorifying and sheafifying MF/MC.

Among the novel insights coming from this talk even if one has been following the UPenn developments for a while was the connection to Poincare Duality: “Flow duality is a form of Poincare duality” — S. Krishnan

The approach detailed by Krishnan in his preprint (on http://www.math.upenn.edu/~sanjeevi/papers/mfmc.pdf ) encodes a flow network as a sheaf of semi-modules of capacities over a semi-ring over the directed graph of the network. Flows correspond to homology, cuts to cohomology.

MF/MC translates to:

Theorem (S. Krishnan)

Given a network X, a distinguished (virtual) edge e and a capacity sheaf F, (all) flowvalues at e of flows on F correspond to the homotopy limit over all cuts of cutvalues of cuts on F.

This approach, and connecting flows and cuts to a lattice structure on the constraints produces a setting where multi-kind flows can easily be analyzed with the same tools as ordinary flows, and where the algebra fixes the duality gaps that show up when naively searching for minima and maxima.

The talk culminated in a primer on the homology and cohomology of directed sheaves, to set us up to read Krishnan's paper, constructing compact support cohomology and Borel-Moore homology for sheaves over directed spaces.

The added abstraction levels seem to enable MF/MC theorems for, for instance, probability distributions. It also carries a promise for insights into duality gaps in MF/MC type problems.

Applied Algebraic Topology Research Network

Peter Bubenik writes:

[…] Robert Ghrist, Konstantin
Mischaikow, Fadil Santosa and I are starting a Research Network in Applied Algebraic Topology. To start, the main activity of the network will be a weekly interactive online seminar. We have plans to expand our activities in the future.

Rob Ghrist will give the first talk on Tue Sept 23.

Please check out our web site at https://www.ima.umn.edu/topology/ and become a member.

Wasserstein barycenters and Frechet means

At this past year at the IMA, there has been some attention spent on a number of interesting aspects in bringing persistent homology closer to statistical methods.

One core step in this process has been to figure out what we mean by an average persistence diagram, a question that has an answer proposed by Munch, Bendich, Turner, Mukherjee, Mattingly, Harer and Mileyko in various constellations.

The details on Frechet means for persistent homology is not what this post is about, however. Instead, I want to bring up something I just saw presented today at ICML. Marco Cuturi and Arnaud Doucet got a paper entitled Fast Computation of Wasserstein Barycenters accepted to this large machine learning conference.

In their paper, Cuturi-Doucet present work on computing the barycenter (or average, or mean) of N probability measures using the Wasserstein distance: they articulate the transport optimization problem of finding a measure minimizing Wasserstein distance to all the N given measures, and present a smoothing approach that allows them to bring the problem onto a convex optimization shape. In the talk — though not present in the paper — the authors argue that they can achieve quadratic running times through these approximation steps. Not only that, but their approach ends up amenable for GPGPU computation and significant parallelization and vectorization benefits.

Their approach works anywhere that the Wasserstein metric is defined, and so in particular should work (and most likely give the same results) on the persistence diagram setting studied by the persistent statistician constellations mentioned above.

I for one would be excited to hear anything about the relations between these (mostly) parallel developments.

ATMCS 6: Day 4

Today's summaries are provided by Isabel Darcy.

Omer Bobrowski talked about Topological Estimation for Super Level Sets.  The goal is to determine the homology of an unknown space from a sample of noisy data points.  Super-level sets of a density function f correspond to dense regions: {x | f(x) > L}.  In general, the density function is not known but can often be estimated.  One can try to reconstruct the homology by looking at U_n(L, r) = the union of balls of fixed radius r around each point in a super level set, {x | f(x) > L}.

But if not enough points are chosen (i.e., L large), then the space may not be adequately covered by U_n(L, r).  If too many points are chosen (i.e., L small), then more noise may be picked up.  However one can obtain the correct homology with high probability by looking at how U_n(L_1, r) includes into U_n(L_2, r) for L_2 < L_1.  This induces a map on their homologies.  The image of this map is the homology estimator, which equals the correct homology of the space of interest with high probability.

Elizabeth Munch talked about The Interleaving Distance for Reeb Graphs. Reeb graphs provide an efficient description to understand the properties of a real-valued function on a topological space and are useful in many applications.  Thus it would be very useful to have a method for comparing two Reeb graphs.  Interleavings (and interleaving distances) have been used to compare persistence modules.  Interleavings can be applied to Reeb graphs by defining a generalization of a Reeb graph as a functor.  One consequence is a concrete algorithm for smoothing a Reeb graph in order to remove noise.

Peter Bubenik talked about Generalized Persistence Modules and Stability.  Generalized persistence modules is an abstract formulation of persistence modules using category theory which includes many forms of persistence modules that are currently studied.  One consequence of this formulation is that one can give simpler common proofs for many standard results such as stability.

Yuliy Baryshnikov talked about Integral Operators in Euler World. One can integrate functions that take on a finite number of values using the Euler characteristic as the measure.  For example if f(x) = 4 for x in [0, 1] and 0 elsewhere, then the integral of f with respect to the Euler characteristic = 4 times the Euler characteristic of [0, 1] = 4(-1 + 2) = 4.  In applications, sometimes it is easier to solve a problem by transforming it into a simpler problem using an integral transform.

An example of an integral transform is convolution: Given functions f and g, one can create a new function, f*g, where the value f*g(x) is obtained from f and g by integrating the product f(t)g(x-t) with respect to the euler characteristic.  Given f and f*g, one would like to be able to reconstruct g: that is one would like to calculate the inverse of the Euler integral transform.  Cases where one can calculate the inverse transform were discussed.

ATMCS 6: Day 3

Summaries for Day 3 are contributed by Rachael Phillips.

Jeff Erickson talked about efficiently hex-meshing things with topology. With a hex mesh, a polyhedra with six quadrilateral facets, there can be a quadrilateral mesh that can be extended to a hexahedral mesh of the interior volume. This can only happen when there are an even amount of quadrilaterals and none of the cycles are odd for the hex mesh. If such a mesh exists, then a polyhedron in 3-dimensional Euclidean space with quadrilateral facets can be constructed in polynomial time. These are extended to domains that have disconnected boundaries and are continued from Thurston, Mitchell, and Eppstein, where the odd cycle criteria is trivial. The idea is to look at a quadrilateral figure and extend that figure to the interior. So, the importance is not in the shape of that figure, since we are not looking at the geometry of this figure, but the topology.

 Jose Perea talked about Obstructions to Compatible Extensions of Mappings. From Betti numbers in 1994 to Zig-Zag persistence in 2009, there have been several classic invariants in algebraic topology. The basic ones being from a point cloud, constructing a filtration and using that filtration to compute Betti numbers, which tell us about the number of k-dimensional holes within a metric space. Instead of this, it would be useful to come up with new ways of encoding multi-scale information from data. The main goal is to be able to fit our data into a model for the best methods. Using extending sections and the retraction problem, Mumford data is used to fit the model. The question is, how far do you have to go for the model to be good? From local to global, the model tells us the death-like events, where an example would be compatible extensions. The birth-like events where the filtration of each level extends to the next. Once these models are found, it extends compatibility once the model has been extended. The main goal being to extend the previous invariant methods to new invariant methods for data analysis.

Donald Sheehy talked about Nested Dissection and (Persistent) Homology. Using nested dissection, this is a way of solving systems of linear equations. This method is an improvement of the naive Gaussian elimination. The reason that it is important to improve Gaussian elimination is because it is a long process that takes a lot of computer memory. It is a method that needs to be improved when using computers to solve it. By building a filtered simplicial complex and computing the persistent homology, we can try to speed up the process of elimination. Normally, Gaussian elimination has a running time of O(n^3), or even worse using Strassen it is a running time of O(n^{\log_27}). Nested Dissection removes a random column in a matrix and separates the graph into two pieces. When a matrix is separated in two pieces, it improves the matrix multiplication and using topology, while doing Gaussian on the boundary. The nested dissection computes the persistent homology of the space of the matrix. Using four methods such as Mesh Filtrations, Nested Dissection, Geometric Separation and Output sensitive persistence algorithm, there is a theorem that improves the asymptotic running time of the persistence algorithm.

Shmuel Weinberger talked about Complex and Simple "Topological" invariants. It is common in the study of topological data analysis that the values of topological invariants are discussed. When you calculate homology it does not always give you enough information. The goal is not to look at the dynamics, but learn about dynamics. It is possible to look at the persistent homology of any data set, unfortunately, conditions on the noise, "invariance" with high-probability. It is important is to find examples of Probability Approximately Correct (PAC) computable ideas. Knowing when noise is a problem and when it is not is the main goal of this talk.

ATMCS 6: Day 2

For day 2, Sara Kalisnik and Andrew Blumberg are giving summaries of the talks we heard:

Gunnar Carlsson: Persistence barcodes are natural invariants of finite metric spaces useful for studying point cloud data. However, they are not well adapted to standard machine learning methods. One approach to this problems is to equip the set of barcodes with a metric, but an even simpler would be to provide coordinates for the set of barcodes. Gunnar Carlsson talked about coordinatizations of barcode spaces and their properties. He also proposed some ways in which they could be used to obtain information from multidimensional persistence profiles.

Vanessa Robins focused on on-going work about applications of discrete Morse theory and persistent homology to analyzing images of porous materials.  She explained specific connections between the physical structure of the material and the patterns of persistence diagrams.  The results presented were particularly exciting insofar as they represented a very serious and thorough application of computational topology to large quantities of real data.

Radmila Sazdanovic introduced categorification and provided several examples in pure mathematics, especially knot theory. Among others, categorifications of Jones and chromatic polynomials.

Sayan Mukherjee had two distinct themes.  In the first part of the talk, he discussed results (with Boyer and Turner) on the "persistent homology transform" and "Euler characteristic transform", which roughly speaking are invariants of an object in \mathbb{R}^2 or \mathbb{R}^3 obtained by taking the ensemble of persistent homology or Euler characteristic of slices (relative to some fixed orientation vector).  It turns out these are sufficient statistics and moreover seem quite successful in classification problems (e.g., for primate bones).  The second part of the talk focused on the problem of manifold learning in the context of mixtures of hyperplanes of different dimensions.  The key insight is that a Grassmanian embedding due to Conway, Hardin, and Sloane allows the use of distributions on the sphere to carry out statistical procedures on spaces of hyperplanes.

ATMCS 6: Day 1

Day 1 of ATMCS 6 is now (mostly) over. Small groups of applied topologists are roaming the streets of Vancouver looking for sights, food or drink, while the less hardy of us have already eaten and retired to our rooms for a quiet night, or a night full of last-minute preparations.

Vin de Silva talked about his currently ongoing research into interesting new perspectives on persistence stability theorems and foundational models for persistence modules. One thing that really caught my attention was the idea of metric certificates: many metrics are defined as the supremum or infimum over a range of potential comparison points. The certificates idea summarizes all these approaches under a common header - a comparison point is a certificate, and the metric is produced by optimizing across certificates.

This is put to use to produce extension theorems of the form
If A is a subspace of B, and there is a 1-Lipschitz map A \to M, then we can construct a 1-Lipschitz map B \toM.
These theorems turn out to hold in a bunch of situations, and to be highly relevant for persistent homology.

Amit Patel talked about his work on Quillen 2-categories and their relationship to persistent homology. It turns out there are ways of talking about persistent homology that pull in some sheaf-theoretic perspectives and naturally produce a Quillen 2-category that encodes much of the structure.

Sarah Day talked about Conley index theory and symbolic dynamics; with some research geared towards using symbolic dynamics approximations of dynamical systems to discover models and pick out cycles and stable behaviors. Within this project, Conley indices turn out to be useful tools.

Tamal Dey talked about the Graph induced complex, and work with Fengtao Fan and Yusu Wang on data sparsification by building topological models and simplifying the computational complexity of generating topological inferences.

I'll see if I can recruit volunteers from the audience to keep a stream of conference updates flowing here.