Optimization, Algebra, and Geometry Seminar
I am organizing the Optimization, Algebra, and Geometry seminar on Thursdays at 2:30 PM (EDT) in Fall 2022. We either meet in person or on Zoom, and record the seminars in the latter case. The recordings will be available on our Youtube Channel.
Fall 2022
Date: Sept. 15, 2022
Time: 2:30 PM (EDT)
Location: Virtual, Zoom
Speaker: Timothy Duff, Department of Mathematics, University of Washington
Title: An Atlas for the Pinhole Camera
Abstract: Projective space, rational maps, and other notions from algebraic geometry appear naturally in the study of image formation and various applications of computer vision such as 3D reconstruction. In the algebraic study of vision, polynomial constraints encoded in the multiview ideal have so far been the stars of the show, owing in large part to their application to the task of triangulation. However, the analogous constraints associated with other tasks, namely resectioning and bundle adjustment, have not received such systematic attention. In joint work with Sameer Agarwal, Max Lieblich, and Rekha Thomas, we seek to remedy this situation by introducing an Atlas of the Pinhole Camera which catalogues a rich network of algebraic varieties and their vanishing ideals connected to these various tasks. To show the utility of this framework, we characterize various “generalized multiview ideals” associated with the bundle adjustment problem, which are interesting objects in their own right. Some nice previous results about multiview ideals also fall out as corollories from our framework. For example, we give a new proof of a result by Aholt, Sturmfels, and Thomas that the multiview ideal has a universal Groebner basis consisting of k-focals (also known as k-linearities in the vision literature) for k in {2,3,4}. Time-permitting, I will end with a few words about resectioning ideals (current work in progress, joint with Erin Connelly and Jessie Loucks-Tavitas.)
Date: Sept. 22, 2022
Time: 2:30 PM (EDT)
Location: Virtual, Zoom
Speaker: Alexander Strang, Department of Statistics, University of Chicago
Title: A Functional Theory for Principle Trade-off Analysis
Abstract: Principal Trade-off Analysis (PTA) is a data visualization technique that simplifies complicated extensive form games. PTA represents a complex game as a combination of simpler games via the real Schur form. It satisfies a close analogy with Principal Component Analysis (PCA). Like PCA, PTA produces a sequence of embeddings in a low dimensional latent space, the sequence is low rank optimal, and each embedding is orthogonal to the others. The embeddings encode strategic information as low dimensional geometry, enabling visualization. Here we explore the functional theory underpinning PTA. To develop a functional theory, we search for the set of embeddings that best approximate the desired game, given a chosen function space and distribution representing the available information. We solve this optimization problem, show that the solution satisfies a universal approximation theorem, and study the convergence and stability of the solution. We conclude by showing how the differential geometry of each embedding map can be mined for useful information regarding the original game or decision problem.
Date: Sept. 29, 2022
Time: 2:30 PM (EDT)
Location: Virtual, Zoom (Cancelled-Rescheduled for Spring 2023)
Date: Oct. 06, 2022
Time: 2:30 PM (EDT)
Location: Hybrid, Wean 8220
Speaker: Joseph Alameda, Department of Mathematics, United States Naval Academy,
Title: Optimizing cooperative interdependent attack graphs to compromise network infrastructures
Abstract: As infrastructures in our society become increasingly interdependent on one another, the possibility of attacks on these infrastructures utilizing these interdependencies also increases. In this paper, we consider attacks from multiple attackers working fully-cooperatively to reach their goals. Moreover, we model the possibility that more than one exploit may have to be used by an attacker to reach their objective. We provide a mixed-integer program for this attacker model, and we provide an algorithm that gives us an optimal solution. Furthermore, we provide preliminary analysis showing the computational effectiveness of our algorithm when compared to the MIP.
Date: Oct. 13, 2022
Time: 2:30 PM (EDT)
Location: Virtual, Zoom (Cancelled-Rescheduled for Spring 2023)
Speaker: Saugata Basu, Department of Mathematics, Purdue University
Date: Oct. 27, 2022
Time: 2:30 PM (EDT)
Location: Hybrid, Wean 8220
Speaker: Joseph Landsberg, Department of Mathematics, Texas A&M University
Title: Geometry and the complexity of matrix multiplication
Abstract: In 1968 Strassen discovered the way we usually multiply n x n matrices, which uses on the order of n^3 arithmetic operations, is not the best possible. That discovery inspired a tremendous amount of research and led to the astounding conjecture that as the size of the matrices increases, it becomes almost as easy to multiply matrices as it is to add them! That is, one can get as close as one wants to the order of n^2 arithemetic operations. After giving a history of the problem, I will explain how one can approach the problem using algebraic geometry and representation theory.
Date: Nov. 03, 2022
Time: 2:30 PM (EDT)
Location: Virtual, Zoom
Speaker: Serkan Hosten, Department of Mathematics, San Francisco State University
Title: Gram Spectrahedra of Symmetric Binary Forms
Abstract: I will report on the geometric and combinatorial structure of symmetry adapted Gram spectrahedra of symmetric polynomials. I will focus on symmetry adapted Gram spectrahedra of symmetric binary forms. In particular, I will present a characterization of extreme points of these spectrahedra for symmetric binary forms that are of rank two. This is complementary to a classical result in the non-symmetric case. I will also report what we know about the facial structure and combinatorics of the same spectrahedra.
Date: Nov. 10, 2022
Time: 2:30 PM (EDT)
Location: Virtual, Zoom
Speaker: Elizabeth Gross, Department of Mathematics, University of Hawai`i at Mānoa
Title: Model Selection for Gaussian Mixtures with Numerical Algebraic Geometry
Abstract: Gaussian mixture models are collections of continuous probability distributions used for clustering and density estimation with applications in a variety of fields in science and engineering. Model parameters for Gaussian mixture models are typically estimated from training data using the iterative expectation-maximization (EM) algorithm, which requires knowing the number of Gaussian components a priori. In this study we propose an approach using numerical algebraic geometry to identify the optimal number of Gaussian components in a Gaussian mixture model. The proposed approach transforms a Gaussian mixture model into equivalent polynomial regression splines and uses homotopy continuation methods to find the model, or, equivalently, the number of components that is most compatible with the training data.
Date: Nov. 17, 2022
Time: 2:30 PM (EDT)
Location: Virtual, Zoom
Speaker: Botong Wang, Department of Mathematics, University of Wisconsin Madison
Title: Topological aspects in algebraic optimizations
Abstract: We will survey some recent works relating the algebraic degree of optimization problems and the topological Euler characteristics. More specifically, the topological formulas for Maximum likelihood degree and Euclidean distance degree will be discussed. We will also explore deeper relations between the algebraic bidegrees in optimization problems and Chern classes. Finally, we will mention some of the conjectures that are resolved by using our topological formulas. The results are joint works with Laurentiu Maxim, Jose Rodriguez and Lei Wu.
Date: Dec. 01, 2022
Time: 2:30 PM (EDT)
Location: Virtual, Zoom
Title: Feature Sizes and Bottlenecks for Algebraic Manifolds
Abstract: In computational topology and geometry, theoretical guarantees for algorithms often take the following form: Start with a finite sample of points from a subspace of \mathbb{R}^n. If the sample is "dense enough" with respect to the subspace, then the algorithm outputs a quantity of interest for the subspace, for example its Betti numbers. The quantities associated to a subspace which determine how dense of a sample is necessary are well studied by computational geometers: the reach, local feature size, and weak feature size of a subspace. Rather than a set of points, an algebraic space X is specified by a system of polynomial equations. To apply the above methods in a theoretically sound way, one must use the space's defining equations both to compute its feature sizes and subsequently a dense point sample from the space. In this talk, I will discuss new theory and algorithms to compute feature sizes of algebraic manifolds using numerical algebraic geometry methods. The corresponding theory investigates the differential critical point/value theory of a particular class of optimization problems, namely the constrained optimization distance-to-X function d_X:\mathbb{R}^n \to \mathbb{R}, from an algebraic geometry perspective. This is joint with Sandra Di Rocco, David Eklund, Oliver Gävert, and Jonathan Hauenstein.
Date: Dec. 08, 2022
Time: 2:30 PM (EDT)
Location: Virtual, Zoom
Speaker: Thorsten Theobald, Mathematical Institute of the Goethe University in Frankfurt Am Main
Title: Sublinear circuits and constrained signomial optimization
Abstract: Relative entropy programs belong to the class of convex optimization problems. Within techniques based on the arithmetic-geometric mean inequality, they facilitate to compute nonnegativity certificates of polynomials and of signomials (i.e., exponential sums). While the initial focus was mostly on unconstrained certificates and unconstrained optimization, recently, Murray, Chandrasekaran and Wierman developed conditional techniques, which provide a natural extension to the case of convex constrained sets. The goal of this talk is to explain the geometry of the resulting cone ("conditional SAGE cone"). To this end, we introduce and study the sublinear circuits of a finite point set in R^n, which generalize the simplicial circuits of the affine-linear matroid induced by a set A to a constrained setting. Based on joint work with R. Murray and H. Naumann.
Spring 2023
Date: Jan. 26, 2023
Time: 2:30 PM (EDT)
Location: Virtual, Zoom
Speaker: Martin Helmer, Department of Mathematics, North Carolina State University
Title: Conormal Spaces and Whitney Stratifications
Abstract: In this talk I will describe a new algorithm for computing Whitney stratifications of complex projective varieties. The main ingredients are (a) an algebraic criterion, due to Lê and Teissier, which reformulates Whitney regularity in terms of conormal spaces and maps, and (b) a new interpretation of this criterion which can be practically implemented on a computer. This algorithm improves upon the existing state of the art by several orders of magnitude, even for relatively small input varieties. This algorithm gives rise to related algorithms for efficiently stratifying affine varieties, flags on a given variety, and algebraic maps. This is joint work with Vidit Nanda (Oxford).
Date: Apr. 06, 2023
Time: 2:30 PM (EDT)
Location: Virtual, Zoom
Title: How do exponential size solutions arise in semidefinite programming?
Abstract: A striking pathology of semidefinite programs (SDPs) is illustrated by a classical example of Khachiyan: feasible solutions in SDPs may need exponential space even to write down. Such exponential size solutions are the main obstacle to solve a long standing, fundamental open problem: can we decide feasibility of SDPs in polynomial time?
The consensus seems that SDPs with large size solutions are rare. However, here we prove that they are actually quite common: a linear change of variables transforms every strictly feasible SDP into a Khachiyan type SDP, in which the leading variables are large. As to ``how large", that depends on the singularity degree of a dual problem. Further, we present some SDPs in which large solutions appear naturally, without any change of variables. We also partially answer the question: how do we represent such large solutions in polynomial space?
Joint work with Alex Touzov