Tuesday, October 29, 2013 - 4:05pm - 6:00pm
- Bottleneck Loops
Yiying Tong (Michigan State University)
We present a method for computing a set of bottleneck oops that describe the narrowing of the volumes inside/outside of the surface and extend the notion of surface homology and homotopy loops. The intuition behind their definition is that such a loop represents the boundary of a membrane within a given distance from the surface that separates the inside volume. Our definition is based on persistent homology theory, which gives a measure to topological structures, thus providing resilience to noise and a well-defined way to determine topological feature size. More precisely, the persistence computed here is based on the lower star filtration of the interior or exterior 3D domain with the distance field to the surface being the associated 3D Morse function.
- Cohomology in Low Frequency Electrodynamics
Pawel Dlotko (University of Pennsylvania)
In the middle of '70 Tonti (following the works of Branin and Kron
from '50 and '60) discovered that the discrete counterparts of
physical laws of electromagnetism can be written up by using the
language of algebraic topology. They involve cochains on a pair of
cell complexes, one dual to the other, and (co)boundary operators.
As a result a system of algebraic equations instead of a system of
standard PDE's is obtained. Therefore, for a given complex, no
discretization step is needed and physical laws are enforced exactly
in the given mesh.
The discrete counterparts of the laws of electromagnetism are usually
enforced locally, for each cell of the complex. Therefore, there
exists the problem of ensuring that the laws still hold considering an
arbitrary collection of cells. In some of the standard formulations,
this trivially holds as nonlocal laws are a linear combination of
local laws. However, this does not hold in case of the numerically
efficient scalar potential based method, which requires the
information about topology of the insulating region to be computed in
form of the so called cuts.
Engineering community spent more than two decades trying to define and
compute the cuts in a simple and fast way. They did not succeed. Only
recently we shown that the cuts are a first cohomology basis of the
insulating subcomplex. In this poster we will give an idea of the
considered formulation and explain why cohomology generators are
needed to make it work. Later we will present the ideas we use to
efficiently compute the cohomology basis for industrial sized meshes.
This enables to effectively solving what has been considered an open
problem for more than twenty-five years.
- Online HodgeRank on Random Graphs for Crowdsourceable QoE Evaluation
Qianqian Xu (Peking University)
We propose an online ranking/rating scheme based on stochastic approximation of HodgeRank on random graphs for Quality of Experience
(QoE) evaluation, where assessors and rating pairs enter the system in a sequential or streaming way.
Two particular types of random graphs are studied in detail, i.e., Erdos-Renyi random graph and preferential attachment random graph.
The former is the simplest I.I.D. (independent and identically distributed) sampling and the latter may
achieve more efficient performance in ranking the top-k items due to its Rich-get-Richer property.
- An Algebraic-Topological Skeleton for Advanced Topological Analysis
Pedro Real-Jurado (University of Sevilla)
This work deals with combinatorial structures installed on cell complexes, allowing fast computation for a great variety of algebraic topological invariants. Within a cell or digital context and using some relevant examples up to four dimension, we show some algorithms for computing a Homological Spanning “Forest” (or HSF, for short) for an object. Such graph-based structure is a kind of topological “dense” skeleton, installed on the 1-skeleton of the first subdivision of the cell complex. From such a sort of “veinerization”, it is possible to compute different algebraic topological invariants: not only Betti number and representative elements of homology generators but also advanced algebraic relations between homology generators (cup-product, (co)homology operations, A(infty)-coalgebra structure of the homology,….). HSF-structures are a well adapted to homotopical analysis and to control geometric evolution of curves and surfaces within the object. Finally, a theoretical framework for digital image topological processing based on these new concepts is proposed.
- From Structured Discretization of Port-Hamiltonian Systems to Data Analysis
Marko Seslija (Katholieke Universiteit Leuven)
Geometry as the study of observable symmetries and dynamical invariants is de facto the lingua franca of the Hamiltonian theories. The prevailing paradigm in modeling of the complex large-scale physical systems is network modeling. In many problems arising from modern science and engineering, such as multi-body systems, electrical networks and molecular dynamics, the port-based network modeling is a natural strategy of decomposing the overall system into subsystems, which are interconnected to each other through pairs of variables called ports and whose product is the power exchanged between the subsystems. The formalism that unifies the geometric Hamiltonian and the port-based network modeling is the port-Hamiltonian, which associates with the interconnection structure of the network a geometric structure given by a Poisson, or more generally, a Dirac structure.
In this poster I address (i) the issue of structure-preserving discretization of distributed-parameter port-Hamiltonian systems on bounded domains, and (ii) consider the avenues that lead towards more data-driven analysis of complex systems.
- HodgeRank on Random Graphs for Subjective Video Quality Assessment
Bowei Yan (Peking University)
We propose a novel framework, HodgeRank on Random Graphs, based on paired comparison, for subjective video quality assessment. Two types of random graph models are studied, i.e., Erdös–Rényi random graphs and random regular graphs. Hodge decomposition of paired comparison data may derive quality scores of videos and inconsistency of participants’ judgments. We demonstrate the effectiveness of the proposed framework on LIVE video database. Both of the two random designs are promising sampling methods without jeopardizing the accuracy of the results. In particular, due to balanced sampling, random regular graphs may achieve better performances when sampling rates are small. However, when the number of videos is large or when sampling rates are large,Erdös–Rényi random graphs could provide good approximations to random regular graphs.
- Topological Strata of Weighted Complex Networks
Giovanni Petri (ISI Foundation)
We introduce a novel method to detect particular non-local structures, akin to weighted holes within the link-weight network fabric, invisible to existing methods. These divide weighted networks in two broad classes: one characterized by small hierarchically nested holes, and a second displaying larger and longer living inhomogeneities. These classes cannot be reduced to known local network properties, due of the mesoscopic nature of homological properties. Finally, we show that the classification finds a correlate in the adjacency and Laplacian spectral gaps, linking topological and dynamical network properties. This is work with M. Scolamiero, I. Donato and F. Vaccarion ( PLoS ONE 8(6): e66506.)
- Towards Postural Synergies for Caging Grasps
Mikael Vejdemo-Johansson (Royal Institute of Technology (KTH))
with Johannes A. Stork, Florian T. Pokorny, and Danica Kragic (all from KTH Royal Institute of Technology)
Caging grasps of unknown objects is a difficult area in robotic grasping and motion planning. We use shortest homology generators to find likely grasp sites, and explore possible grasping plans using topological invariants to verify expected performance of a grasp attempt.
- Segmentation and Analysis with Topological Information
Chao Chen (Rutgers, The State University Of New Jersey )
Image segmentation is to label a region of the image as an object. However, thin structures are often missed due to noise. We present a method to capture such structures using a priori information of the object topology. Based on persistent homology, our method also provides a confidence measure of whether the restored structures are from the true signal. We apply the method to vision, graphics and medical imaging.
- Laplacian-Based Methods for Geometrical Analysis of
John Steenbergen (Duke University)
This poster presents recent research on the theoretical foundation for using Hodge Laplacians on simplicial complexes for data analysis. In the past, the graph Laplacian has been successfully used for clustering and dimension
reduction, with these applications motivated by certain theoretical
advances in spectral graph theory. Our main result provides a partial
theoretical foundation for understanding the spectrum of the highest-order
Hodge Laplacian on a simplicial complex. A simple algorithm is devised
and applied to a toy example to demonstrate how this result might be used
for data analysis.
- An Introduction and a New Text Representation for Natural Language Processing
Xiaojin (Jerry) Zhu (University of Wisconsin, Madison)
This is a poster presented at IJCAI 2013, a major artificial intelligence conference, with the goal of introducing persistent homology to a broader audience including computer scientists. While the first part of the poster presents a tutorial on persistent homology, the second part contains one of the first applications of persistent homology to natural language processing. Specifically, our Similarity Filtration with Time Skeleton (SIFTS) algorithm identifies holes that can be interpreted as semantic tie-backs in a text document, providing a new document structure representation. We illustrate our algorithm on documents ranging from nursery rhymes to novels, and on a corpus with child and adolescent writings.
- Evasion Paths in Mobile Sensor Networks
Henry Adams (University of Minnesota, Twin Cities)
Suppose that ball-shaped sensors wander in a bounded and contractible domain. A sensor doesn't know its location but does know when it overlaps a nearby sensor. We say that an evasion path exists in this sensor network if a moving evader can avoid detection. Vin de Silva and Robert Ghrist give a necessary condition, depending only on the time-varying connectivity graph of the sensors, for an evasion path to exist. Can we sharpen this result? We show that the existence of an evasion path depends not only on the fibrewise homotopy type of the region covered by sensors but also on its embedding in spacetime. Furthermore, we study the entire space of evasion paths using a homotopy spectral sequence for diagrams of spaces.
- A General Learning Framework in Vector-Valued Reproducing Kernel Hilbert Spaces
Minh Ha Quang (Istituto Italiano di Tecnologia)
Reproducing kernel Hilbert spaces (RKHS) have recently emerged as a powerful mathematical framework for many problems in machine learning, statistics, and their applications.
This poster is based on work presented at the International Conference on Machine Learning (ICML 2013). It gives a formulation in vector-valued RKHS that provides a unified treatment of several important machine learning approaches. Two of these are: (i) vector-valued Manifold Regularization, which seeks to exploit the geometry of the input data via unlabeled examples using vector-valued graph Laplacian, and (ii) Multi-view Learning, which attempts to integrate different features and modalities in the input data. The mathematical formulation will be accompanied by numerical results on several challenging multi-class classification problems.
- An Efficient Computation of Handle and Tunnel Loops via Reeb Graphs
Tamal Dey (The Ohio State University)Yusu Wang (The Ohio State University)
A special family of non-trivial loops on a surface called handle and tunnel loops associates closely to geometric features of “handles” and “tunnels” respectively in a 3D model. The identification of these handle and tunnel loops can benefit a broad range of applications. Many of the existing efficient algorithms for computing non-trivial loops cannot be used to compute these special type of loops. The two algorithms known for computing handle and tunnel loops provably have a serious drawback that they both require a tessellation of the interior and exterior spaces bounded by the surface, which is both hard and expensive. We present an efficient algorithm to compute a basis for handle and tunnel loops without requiring any 3D tessellation. This saves time considerably for large meshes making the algorithm
scalable while computing the loops on the original input mesh and not on some refined version of it. We use the concept of the Reeb graph which together with several key theoretical insights on linking number provide an initial set of loops that provably constitute a handle and a tunnel basis.
This work is done by Tamal Dey, Fengtao Fan and Yusu Wang.
- Topological Signatures of the Coding Space Hypothesis
Correlations in neural spiking activity are an important tool for understanding neuronal populations. Pairwise correlations can be organized into graphs, with edges reflecting the levels of correlation between pairs of neurons. In brain areas with convex receptive fields or place fields, the structure of the neural code has strong implications for the structure of cliques in these graphs. For example, for hippocampal place cell activity during spatial exploration, pairwise correlation graphs are expected to have low-dimensional topology, due to the arrangement of receptive fields in a low-dimensional environment. However, during more general activities, there is no reason to expect low-dimensional topology to appear in network activity. Using topological data analysis we found that, remarkably, under a variety of behavioral conditions (open field exploration, wheel running, and sleep) we found hippocampal correlation graphs to carry low dimensional topology by comparing their clique structure to that of geometric random graphs with matching parameters. This suggests that neural activity in hippocampus codes intrinsically low-dimensional structures.
- Persistent Cohomology & Periodic Systems
Mikael Vejdemo-Johansson (Royal Institute of Technology (KTH))
Primoz Skraba (Jozef Stefan Institute)
Vin de Silva (Pomona College)
Florian T. Pokorny (KTH Royal Institute of Technology)
We present techniques developed to analyze periodic, quasi-periodic and recurrent systems using circular coordinates computed using persistent cohomology. In particular, we present applications to weather data, to dynamical systems, and to human motion.
- Eigenvalues of the 1-Laplacian
Mark Schubel (University of Illinois at Urbana-Champaign)
A planar dumbbell shaped domain splits into two components if the connecting neck vanishes. This is reflected in the eigenvalues of the scalar Laplacian on such domains. On the original dumbbell the scalar Laplacian has one 0 eigenvalue, however without the neck it has two. Calabi, Cheeger, and Buser studied what happens as the neck becomes thinner. Buser showed that the smallest nonzero eigenvalue is bounded above by a polynomial in the Cheeger constant which is proportional to the width of the neck (as the neck becomes small). Thus the smallest nonzero eigenvalue anticipates the arrival of a topological change (one component changing to two). We create a solid dumbbell by rotating the planar dumbbell and observe that the smallest eigenvalue of the 1-Laplacian goes to zero as the middle is made thinner. Thus that eigenvalue anticipates the arrival of a different type of topological change (a solid ball changing to a solid torus). Furthermore, we find an upper bound on the rate that the eigenvalue approaches zero as thickness of the middle goes to zero. This work is done as part of an investigation into generalizing the Cheeger-Buser inequality for higher Laplacians. Joint work with Douglas Arnold, Anil N. Hirani, and Sayan Mukherjee.
- Cohomologous Harmonic Cochains
Kaushik Kalyanaraman (University of Illinois at Urbana-Champaign)
We describe methods for finding any discrete harmonic forms and those forms in a specified cohomology class (cohomologous to a given element). We demonstrate the eigenvector method for finding a basis for the space of discrete harmonic forms. For cohomologous harmonic forms, we illustrate our work in formulating a weighted least squares method by proving a discrete Hodge-deRham theorem on the isomorphism between the space of harmonic cochains and cohomology. We also outline two projection methods that given a harmonic basis can project it to the required cohomology class. However, they either require representative elements from all cohomology classes or from all homology classes. These discrete harmonics forms have potential applications in the solution of partial differential equations in exterior calculus, computational topology and computer graphics. We show an application in finite element exterior calculus and data analysis. Joint work with Anil N. Hirani, Seth Watts and Han Wang.
- Robust Ranking on Graphs
Jiechao Xiong (Beijing (Peking) University)
The problem of ranking based on pairwise comparisons, as an uni-dimensional scaling, is a fundamental problem which can be traced back at least to the 18th century. Recently there is a rapid growth of paired comparison data which are imbalanced, incomplete, and distributed on graphs, e.g. from the crowdsourcing experiments on Internet. It is important to monitor the quality of such data where the existence of outliers may cause instability to the inference of global ranking. To reach a robust ranking, in this paper a systematic study is carried out on a general linear model in the presence of sparse outliers and Gaussian-type noise. Various conditions and algorithms are presented with which outliers can be detected and the underlying global ranking function can be recovered, exactly or approximately. In particular, one can benet from the exploitation of Erdos-Renyi random graphs in crowdsourcing experiments to reach nearly optimal rates in the exact recovery of global ranking by LAD (L1) against sparse symmetric outliers, and help consistent outlier detections by LASSO against a mixture of sparse outliers and Gaussian noise. The validity of proposed methods is further conrmed by experimental studies on both simulated examples and real-world data.
- Multipersistent Homology and Betti numbers in a Homological Algebra setting.
Martina Scolamiero (Royal Institute of Technology (KTH))
Multipersistent Homology is a natural generalization of Persistent Homology introduced by G.Carlsson and A.Zomorodian. Using this method a point cloud can be analyzed through more than one filtration parameter. For example one can investigate a point cloud through ellipsoids instead of balls in the Vietoris-Rips complex. A filtration of simplicial complexes is substituted by a multifiltration, that is a family of simplicial complexes indexed by r- uples of natural numbers. Because of the algebraic structure underlying multipersistence, a complete discrete invariant generalizing the barcode is not possible. Up to now the most common computable invariant is the rank invariant. In this poster we will recast multidimensional persistence in a homological algebra setting. In particular, we describe multipersistence modules as compact objects in the category of functors from r-uples of natural numbers to vector spaces. We give a constructive way of building minimal resolutions and locally calculate multigraded Betti numbers.
- Free Online Course on Applied Algebraic Topology
Isabel Darcy (The University of Iowa)
This Fall 2013 I am teaching a free online course MATH:7450 (22M:305)
Topics in Topology: Scientific and Engineering Applications of
Algebraic Topology offered through the Mathematics Department and
Division of Continuing Education at University of Iowa.
Goal: To prepare students and other researchers for the IMA Thematic
Year on Scientific and Engineering Applications of Algebraic Topology,
but all interested participants are welcome
Target Audience: Anyone interested in topological data analysis
including graduate students, faculty, industrial researchers in
bioinformatics, biology, business, computer science, cosmology,
engineering, imaging, mathematics, neurology, physics, statistics,
If you are interested in helping to teach a similar course in the
spring, please let me know.
More information about the Fall 2013 course can be found at
- A Discrete Uniformization Theorem for Polyhedral Surfaces
Jian Sun (Tsinghua University)
A discrete conformality for polyhedral metrics on surfaces is
introduced in this paper which generalizes earlier work on the subject.
It is shown that each polyhedral metric on a surface is discrete
conformal to a constant curvature polyhedral metric which is
unique up to scaling. Furthermore, the constant curvature metric
can be found using a discrete Yamabe flow with surgery.