Topological data analysis
- how one infers high-dimensional structure from low-dimensional representations; and
- how one assembles discrete points into global structure.
The human brain can easily extract global structure from representations in a strictly lower dimension, i.e. we infer a 3D environment from a 2D image from each eye. The inference of global structure also occurs when converting discrete data into continuous images, e.g. dot-matrix printers and televisions communicate images via arrays of discrete points.
The main method used by topological data analysis is:
- Replace a set of data points with a family of simplicial complexes, indexed by a proximity parameter.
- Analyse these topological complexes via algebraic topology — specifically, via the theory of persistent homology.
- Encode the persistent homology of a data set in the form of a parameterized version of a Betti number which is called a persistence diagram or barcode.
Point cloud data
Data is often represented as points in a Euclidean n-dimensional space En. The global shape of the data may provide information about the phenomena that the data represent.
One type of data set for which global features are certainly present is the so-called point cloud data coming from physical objects in 3D. E.g. a laser can scan an object at a set of discrete points and the cloud of such points can be used in a computer representation of the object. Point cloud data is any collection of points in En or a (perhaps noisy) sample of points on a lower-dimensional subset.
For point clouds in low-dimensional spaces there are numerous approaches for inferring features based on planar projections in the fields of computer graphics and statistics. Topological data analysis is needed when the spaces are high-dimensional or too twisted to allow planar projections to faithfully represent the features of the point cloud.
To convert a point cloud in a metric space into a global object, use the point cloud as the vertices of a graph whose edges are determined by proximity, then turn the graph into a simplicial complex and use algebraic topology to study it. An alternative approach is the minimum spanning tree-based method in the geometric data clustering. If a group of data points forms a cluster, then the geometry of this point cloud can be determined.
Topological data analysis includes different methods and representations whose purpose is to cluster variegated data via a point cloud stated above. The following are various methods to do so.
- Cech complex. The Cech complex is the nerve of the cover of balls of radius around each point in a set. Since balls are convex and convex sets are contractible, its nerve captures the topology of the cover. The Cech complex is not computed in practice due to its computational complexity. The uniform ball radii imply an assumption of uniform sampling on the input, which is not valid in a real world dataset. Non-uniform radii methods can also be used, such as in the case of the alpha simplex.
- Alpha complex. The Voronoi diagram is the set of all Voronoi regions for the points in . This diagram is considered a closed cover for . The Delaunay complex is the nerve of the Voronoi diagram. The Voronoi cover and its nerve are fundamental geometric objects and have been extensively studied within computational geometry. Alpha complexes are constructed by first building the Delaunay complex. For each simplex of the Delaunay complex, we compute the minimum scale at which each simplex enters the alpha complex. Then the simplices are sorted by their minimum scale to get a partial order of simplices. The alpha complex is not formed with any scale using this ordering. Efficient algorithms and software exist for computing Delaunay complexes, and in turn, alpha complexes in 2 and 3 dimensions. However, the construction of the Delaunay complex is difficult in higher dimensions.
- Vietoris–Rips complex
- Multifiltration model. Morse theory enables one to analyze the topology of a manifold by studying differentiable functions on that manifold. According to the basic insights of Marston Morse, a typical differentiable function on a manifold will reflect the topology quite directly. Morse theory allows one to find CW structures and handle decompositions on manifolds and to obtain substantial information about their homology.
- Persistent homology. See homology for an introduction to the notation.
Persistent homology essentially calculates homology groups at different spatial resolutions to see which features persist over a wide range of length scales. It is assumed that important features and structures are the ones that persist. We define persistent homology as follows: Let be a filtration. The p-persistent kth homology group of is .
Let be a nonbounding -cycle created at time by simplex and let be a homologous -cycle that becomes a boundary cycle at time by simplex . Then we can define the persistence interval associated to as . We call the creator of and the destroyer of . If does not have a destroyer, its persistence is . Instead of using an index-based filtration, we can use a time-based filtration. Let be a simplicial complex and be a filtration defined for an associated map that maps simplices in the final complex to real numbers. Then for all real numbers , the -persistent kth homology group of is . The persistence of a -cycle created at time and destroyed at is . 
There are various software packages for computing persistence intervals of a finite filtration, such as javaPlex, Dionysus, Perseus (which uses discrete Morse theory to simplify the matrix algebra), and PHAT.
- Dimensionality reduction
- Data mining
- Computer vision
- Computational topology
- Digital topology
- Digital Morse theory
- Shape analysis
- Size theory
- Structured data analysis (statistics)
- Gunnar Carlsson (April 2009). "Topology and data". BULLETIN (New Series) OF THE AMERICAN MATHEMATICAL SOCIETY 46 (2): 255–308. doi:10.1090/s0273-0979-09-01249-x.
- C. T. Zahn (1971): "Graph-theoretical methods for detecting and describing gestalt clusters", IEEE Transactions on Computers, pp. 68–86, Vol. 20, No. 1
- Afra J. Zomorodian (2005): Topology for Computing. Cambridge Monographs on Applied and Computational Mathematics.
- Topological Methods in Scientific Computing, Statistics and Computer Science Stanford group
- BARCODES: THE PERSISTENT TOPOLOGY OF DATA
- Topological Data Analysis: the algebraic topology of point data clouds?
- Sanjay Rana (2004). Topological Data Structures for Surfaces. John Wiley and Sons. ISBN 978-0-470-85151-7.
- TOPOLOGY AND DATA, GUNNAR CARLSSON, BULLETIN (New Series) OF THE AMERICAN MATHEMATICAL SOCIETY, Volume 46, Number 2, April 2009, Pages 255–308, Article electronically published on January 29, 2009
- Computational Topology: An Introduction, Herbert Edelsbrunner, John L. Harer, AMS Bookstore, 2010, ISBN 978-0-8218-4925-5
- Topological Methods in Data Analysis and Visualization: Theory, Algorithms, and Applications, Editors Valerio Pascucci, Hans Hagen, Xavier Tricoche, Julien Tierny, Springer, 2010, ISBN 978-3-642-15013-5
- Weinberger, Shmuel (2011), What Is . . . Persistent Homology?, AMS Notices 58 (01): 36–39.
- Ayasdi Resources on Topological Data Analysis for Big Data
- Software packages for computing persistent homology: javaplex and Perseus.
- Seminar on applied topology and TDA at UPenn.