SIAM News Blog
SIAM News
Print

Applied Algebra and Geometry: A SIAGA of Seven Pictures

By Anna Seigal

The new SIAM Journal on Applied Algebra and Geometry (SIAGA).
SIAM’s brand-new journal, the SIAM Journal on Applied Algebra and Geometry, will feature exceptional research on the development of algebraic, geometric, and topological methods with strong connections to applications. The cover of the new journal shows seven pictures. By describing these pictures and discussing the topics they represent, we hope to give readers a glimpse into the world of algebraic, geometric, and topological problems of interest to applied mathematicians.

This article is part II of a three-part series. Stay tuned for the final part in our next issue.

3. Polyhedral Geometry

The Context

A polyhedron is a combinatorial object that crops up in many places. For example, it is the shape of the feasible region for a linear optimization problem. It is a convex shape in \(d\)-dimensional space \(\mathbb{R}^d\) described by an intersection of finitely many closed half-spaces

\[ P = \Big \{ \textbf{x} \in \mathbb{R}^n : A \textbf{x} \le b \Big \}, \]

where \(A\) is a \( d \times n\) matrix describing the angles of the half spaces and \( b \in \mathbb{R}^d\) encodes their translational information.

A polyhedral complex is an object consisting of a compatible collection of polyhedra. The association of a polyhedral object to an algebraic variety paves the way for the use of combinatorial tools to gain understanding. A typical way to do this is via toric geometry. This approach has been used in many areas of applied mathematics, including phylogenetics, economics, integer programming, biochemical reaction networks, and computer vision (from where this particular figure arose).

Tropical geometry offers one method, called tropicalization, for obtaining a polyhedral complex from an algebraic variety. Features of the new object provide useful information. For example, the dimension of the original variety equals that of the new polyhedral complex, and the dimension of the polyhedral object is far easier to compute.

The Figure

Figure 1 depicts one example of the use of polyhedral tools to understand an algebraic-geometric object. This provides us with an understanding of the application from which the variety arose.

Figure 1. A polyhedral complex from an algebraic variety.
In the field of computer vision, and in the real world, ‘taking a photo’ maps the three-dimensional world to a two-dimensional photograph. As any good photographer knows, the resulting features of the photo depend heavily on the angle and location of the camera.

We consider our pictures to be photographs of three-dimensional projective space \( \mathbb{P}^3.\) Each camera, \(A\), is a \(3 \times 4\) matrix which determines a map \(\textbf{x}\:1 \mapsto A\textbf{x}\) to two-dimensional projective space \(\mathbb{P}^2\). This map tells us where each point of the original world ends up in the photograph.

Considering multiple cameras \((A_1, A_2, A_3)\) at different locations yields more information. Now we have a map:

\[ \phi : \mathbb{P}^3 --\to (\mathbb{P}^2)^3 \]

\[ \textbf{x} \longmapsto (A_1 \textbf{x}, A_2 \textbf{x}, A_3 \textbf{x}).\]

The closure of the image of this map is an irreducible variety. For example, if \(A_i\) are the coordinate projections, this variety in \((\mathbb{P}^2)^3\) is cut-out by the Gröbner basis

\[ \{z_0y_2 - x_0z_2, z_1x_2 - x_1z_2, z_0y_1 - y_0z_1, x_0y_1x_2 - y_0x_1y_2\}. \]

When we take the initial monomials of these generators, their zero-set decomposes into seven pieces: one copy of \(\mathbb{P}^1 \times \mathbb{P}^1 \times \mathbb{P}^1\) and six copies of \(\mathbb{P}^1 \times \mathbb{P}^2.\) To illustrate these three-dimensional spaces, we identify each projective space \(\mathbb{P}^i\) with the \(i\)-simplex.

For example, \(\mathbb{P}^2\) corresponds to the two-dimensional simplex \(\Delta_2,\) the triangle, under the map

\[ \mathbb{P}^2 \ni (x_0 : x_1 : x_2) \longleftrightarrow \frac {1}{x_0 + x_1 + x_2}(x_0, x_1, x_2) \in \: \Delta_2,\] and we identify each copy of \(\mathbb{P}^1\) with the one-dimensional simplex \(\Delta_1,\) the unit-length line.

So our initial ideal represents a collection of polytopes which are faces of \((\Delta_2)^3.\) Our copy of \(\mathbb{P}^1 \times \mathbb{P}^1 \times \mathbb{P}^1\) corresponds to the polytope \(\Delta_1 \times \:  \Delta_1 \times \:  \Delta_1.\) This is the dark blue cube. The remaining six pieces \(\mathbb{P}^2 \times \mathbb{P}^1\) correspond to copies of \(\Delta_2 \times \:  \Delta_1.\) These six triangular prisms are the remaining pieces of the figure. The pieces are separated a little so they are easier to see, but the adjacent parallel faces show how the different pieces meet. Meeting along a triangle \(\Delta_2\) means the projective spaces meet at a copy of \(\mathbb{P}^2.\) If their shared facet is a square \(\Delta_1 \times \:  \Delta_1,\) then the projective spaces meet at a copy of \(\mathbb{P}^1 \times \mathbb{P}^1.\) The original figure, along with similar ones, can be found in [1]. The figure was created using Michael Joswig’s software ‘Polymake’ [3].

4. Topology of Data

The Context

Topology offers a set of tools that can be used to understand the shape of data. The techniques detect intrinsic geometric structures that are robust to many common sources of error, including noise and arbitrary choice of metric. For an introduction, see [2, 4]. 

Figure 2. Topological features from data points.
Say we have noisy data points arriving from some unknown space \(X,\) which we believe possesses an interesting shape. We are interested in using the data to capture the topological invariants of the unknown space; these are its holes of different dimensions, unchanged by continuous squeezing and stretching.

The holes of different dimensions are the homology groups of the space \(X\). They are denoted by \(H_k(X),\) where \(k\) is some non-negative integer. The zeroth homology group discloses the number of zero-dimensional holes, or more intuitively, the connectedness of the space. For a space \(X\) with \(n\) connected components, the zeroth homology group is 

\[H_0(X) = \mathbb{Z}^n,\]

the free abelian group with \(n\) generators. One-dimensional holes are counted by \(H_1(X).\) For example, a circle \(X = S^1\) has a single one-dimensional hole, so \(H_1(S^1) = \mathbb{Z}.\)

The connectedness properties of sampled data reveal a lot about the underlying space from which they are sampled. In some situations, such as for structural biological information, knowing the structure of the holes is also indispensable. These structures remain unchanged regardless of the metric we use or the space into which we embed the points. The higher homology groups \(H_k(X)\) for \(k \ge 2\) similarly offer such summarizing features.

But there’s a problem: sampling \(N\) points from a space gives us a collection of zero- dimensional pieces, which—unless two points land in exactly the same place—are all unconnected. Let’s call this data space \(D_0.\) The space \(D_0\) has homology groups

\[ H_k(D_0)= \begin{cases}
\mathbb{Z}^N & k=0 \\
0 & \text{otherwise.}
\end{cases} \]

Usually many points are very close together, and should be treated as coming from the same connected component. To measure this we use persistent homology. We take balls of increasing size centered at the original data points, and measure the homology groups of the space occurring as the union of these balls. We call this space \(D_\epsilon,\) where \(\epsilon\) is the radius of the balls. The important structural features are those that persist for large ranges of values of \(\epsilon.\)

The Figure

Figure 2 shows data points sampled from a torus, which we imagine to live in three-dimensional space. It was created by Dmitriy Morozov of Lawrence Berkeley National Lab. He applies topological methods to cosmology, climate modeling, and materials science.

The sampled points in Figure 2 lie on the torus, specifically in a more specialized, slinky-shaped zone. Topological methods capture this important feature of the shape.

The original data consists of 5,000 points, and our persistent homology approach involves taking three-dimensional balls \(B_\epsilon(d_i)\) of radius \(\epsilon\) at each data point \((d_i).\) When the radius \(\epsilon\) is extremely small, none of the balls will be connected, and the data’s shape is indistinguishable from any other collection of 5,000 points in space.

Before long, the radius will exceed half the distance to all the points’ nearest neighbors. The 5,000 balls connect to form a curled-up circular piece of string. Topological invariants do not notice the curling, so topologically, the shape obtained is a thickened circle with a one-dimensional hole \(H_1(D_\epsilon) = \mathbb{Z}.\) When the radius is large enough for the adjacent curls of the slinky to meet, but not large enough to reach the opposite side of each curl, we get a hollow torus with \(H_1(D_\epsilon) = \mathbb{Z}^2\) and \(H_2(D_\epsilon) = \mathbb{Z}.\) Finally, the opposite sides of each curl of the slinky will meet up, and they will meet with the slinky-curls on the other side of the torus. The shape then becomes three-dimensional with no holes, and \(H_1(D_R) = 0.\)

In this example, we can visualize the data points, confirming that our intuition for the important structure of the shape agrees with the homological computations. For higher-dimensional examples, where visualizing the data is not possible in this way, it is the persistent features that will guide our understanding of the data’s shape.

References

[1] Aholt, C., Sturmfels, B., & Thomas, R. (2013). A Hilbert Scheme in Computer Vision. Canadian Journal of Mathematics, 65, 961-988.

[2] Carlsson, G. (2009). Topology and Data. Bulletin of the American Mathematical Society, 46, 255-308.

[3] Gawrilow, E., & Joswig, M. (2000). Polymake: a Framework for Analyzing Convex Polytopes. Polytopes–Combinatorics and Computation, 29, 43-73.

[4] Ghrist, R. (2014). Elementary Applied Topology (1st ed.). Createspace.

Anna Seigal is a graduate student at the University of California, Berkeley, working in applied algebra. Her interests lie in tensors and applications to biological data. She enjoys writing about mathematics in terms of pictures, and blogs on this subject at https://picturethismaths.wordpress.com/.  
blog comments powered by Disqus