Spring 2017

Thursdays, 515pm-615pm, 891 Evans Hall

toric varieties

Image by Courtney Gibbons

Dinner afterwards

The Applied Algebra Seminar is an interdisciplinary seminar on applications of algebra to fields outside mathematics. Our goal is to connect mathematicians with researchers from other fields using algebraic tools in their work.

Talks are aimed at an interdisciplinary graduate student audience including mathematicians, computer scientists, engineers, biologists, economists, statisticians, and more.

Mailing List

Please sign up for the seminar mailing list to receive information about applied algebra happenings around campus. You can also contact the organizers to be added to the mailing list.


Please contact David Dynerman or Martin Helmer if you are interested in giving a talk! Both mathematicians and scientists in other fields are warmly invited to present.


Upcoming Speakers

January 19 - Bernd Sturmfels, UC-Berkeley (Math)

Bernd Sturmfels

Does Antibiotic Resistance Evolve in Hospitals?

We present a joint paper with Anna Seigal, Portia Mira and Miriam Barlow, aimed at addressing the question in the title. Nosocomial outbreaks of bacteria and the heavy usage of antibiotics suggest that resistance evolves in hospital environments. To test this assumption, we studied resistance phenotypes of bacteria collected from patient isolates at a community hospital. A graphical model analysis shows no association between resistance and patient information other than time of arrival. This allows us to focus on time course data. Our main contribution is a statistical hypothesis test called the Nosocomial Evolution of Resistance Detector (NERD). It calculates the significance of resistance trends occurring in a hospital. It can help detect clonal outbreaks, and is available as an R-package. This lecture offers a glimpse into the use of mathematics and statistics in a bio-medical project.

January 26 - Joe Kileel, UC-Berkeley (Math)

Joe Kileel

Using algebraic geometry for computer vision

In computer vision, 3D reconstruction is a fundamental task: starting from photographs of a world scene, taken by cameras with unknown positions and orientations, how can we best create a 3D model of that world scene? Algorithms that do this built Street View (Google) and are instrumental in autonomous robotics. In 2004, David Nister (Tesla) used Grobner bases to build a solver for robust reconstruction given just two photographs. This is a key routine in much larger-scale reconstructions today. In this talk, I will discuss reconstruction given three photographs, where efforts to replicate Nister have so far proven elusive. My approach relies on applied algebraic geometry. In particular, I shall introduce an algebraic variety whose points are 3x3x3 tensors in correspondence with configurations of three calibrated cameras. Special linear sections of this variety recover camera configurations from image data. The main result is the determination of the algebraic degree of minimal problems for this recovery. These comprise interesting enumerative geometry problems; the solution is by way of homotopy continuation calculations.

February 2 - Nick Ryder, UC-Berkeley (Math)

Nick Ryder

Bivariate Real Stability Testing

We give a strongly polynomial time algorithm which determines whether or not a bivariate polynomial is real stable. As a corollary, this implies an algorithm for testing whether a given linear transformation on univariate polynomials preserves real-rootedness. The proof exploits properties of hyperbolic polynomials to reduce real stability testing to testing nonnegativity of a finite number of polynomials on an interval.

February 9 - Daniel Lowengrub, UC-Berkeley (Math)

Daniel Lowengrub

Scene reconstruction and a resolution of the multiview variety

The multiview variety associated to a collection of $N$ cameras records which sequences of image points in $PP^{2N}$ can be obtained by taking pictures of a given world point $xinPP^3$ with the cameras. In order to reconstruct a scene from its picture under the different cameras it is important to be able to find the critical points of the function which measures the distance between a general point $uinPP^{2N}$ and the multiview variety. In this paper we calculate a specific degree $3$ polynomial that computes the number of critical points as a function of $N$. In order to do this, we construct a resolution of the multiview variety, and use it to compute its Chern-Mather class.

February 16 - Avi Wigderson, Institute for Advanced Study

Avi Wigderson

Commutative and non-commutative rank of symbolic matrices

Our object of study are matrices whose entries are linear forms in a given set of variables. We will be interested in their rank, both when variables commute and when they do not. I will discuss the importance of understanding these, and some structural and computational problems and results regarding them.

This talk will directly follow the departmental colloquium on a related topic. Attending it may be beneficial, but I will not assume you did.

March 2 - Yong Sheng Soh, California Institute of Technology

Yong Sheng Soh

Learning Regularizers from Data

Regularization techniques are widely employed in the solution of inverse problems in data analysis and scientific computing due to their effectiveness in addressing difficulties due to ill-posedness. In their most common manifestation, these methods take the form of penalty functions added to the objective in optimization-based approaches for solving inverse problems. The purpose of the penalty function is to induce a desired structure in the solution, and these functions are specified based on prior domain-specific expertise. For example, regularization is useful for promoting smoothness, sparsity, low energy, and large entropy in solutions to inverse problems in image analysis, statistical model selection, and the geosciences.

We consider the problem of learning suitable regularization functions from data in settings in which precise domain knowledge is not directly available; the objective is to identify a regularizer to promote the type of structure contained in the data. The regularizers obtained using our framework are specified as convex functions that can be computed efficiently via semidefinite programming, and they can be employed in tractable convex optimization approaches for solving inverse problems. Our approach for learning such semidefinite regularizers is based on computing certain structured factorizations of data matrices. We propose a method for this task that combines recent techniques for rank minimization problems along with the Operator Sinkhorn iteration. We discuss some of the theoretical properties of our algorithm as well as its utility in practice. (Joint work with Venkat Chandrasekaran)

March 9 - Yun Song, University of Pennsylvania & UC-Berkeley

Yun Song

Decomposition and unfolding of higher-order tensors

Recently, tensors of order 3 or greater, known as higher-order tensors, have attracted increased attention in many fields across science and engineering. A common paradigm in tensor-related algorithms advocates unfolding (or flattening) the tensor into a matrix and applying classical methods developed for matrices. In this talk, I will consider all possible unfoldings of a tensor into lower order tensors and present general inequalities between their operator norms. I will then describe an application of these theoretical results to tensor decomposition and present a new algorithm built on Kruskal's uniqueness theorem. This tensor decomposition method provably handles a greater level of noise compared to previous methods and achieves a high estimation accuracy. Numerical results demonstrate that our algorithm is robust to various noise distributions and that it performs especially favorably as the order increases. If time permits, I will describe applications of our method to multi-way clustering. (Joint work with Miaoyan Wang, Khanh Dao Duc, and Jonathan Fischer.)

March 16 - Bernd Sturmfels, UC Berkeley & MPI Leipzig

Bernd Sturmfels

Gaussian Mixtures and their Tensors

Mixtures of Gaussians are ubiquitous in data science. We give an introduction to the geometry of these statistical models, with focus on the tensors that represent their higher moments. The familiar theory of rank and borderrank for symmetric tensors is recovered when all covariance matrices are zero. Recent work with Carlos Amendola and Kristian Ranestad characterizes the circumstances under which Gaussian mixtures are identifiable from their moments.

March 23 - David Dynerman, UC-Berkeley

David Dynerman

Estimating the covariance of a protein

In biological electron microscopy, experimentalists produce 2D images of unknown 3D objects (proteins) in unknown orientations, and process these images to recover the unknown 3D object. If we consider these unknown objects and orientations as random variables, the images produced by an experiment can be modeled by

I = PX,

where X is a random variable representing the 3D object and P is a random linear operator producing an image of X.

In this situation, a natural question is: what statistics of X (the object biologists would like to find) can we determine from samples of the random variable I (the data available from experiment)?

This question also has biological motivation - for example, in certain situations the covariance matrix of X can reveal biologically relevant information about the different shapes of a protein.

In this talk we will survey three recent papers by Amit Singer's (Princeton University, Applied Mathematics) group on this problem. We will present work of Katsevich, Katsevich and Singer [1] on estimating the mean and covariance of X, and briefly discuss two other related papers [2], [3].

[1] E. Katsevich, A. Katsevich, A. Singer, Covariance Matrix Estimation for the Cryo-EM Heterogeneity Problem

[2] J. Andén, E. Katsevich, A. Singer, Covariance estimation using conjugate gradient for 3D classification in Cryo-EM

[3] T. Bhamre, T. Zhang, A. Singer, Denoising and Covariance Estimation of Single Particle Cryo-EM Images

April 6 - Jesus De Loera, UC-Davis

Jesus De Loera

Statistical Commutative Algebra

Randomness is an important algorithmic tool in algebra and analysis. Monomial ideals play a key role in computational commutative algebra, and they give a strong link to algebraic combinatorics e.g., through Stanley-Reisner ideals of simplicial complexes. Inspired by results on random graphs and random simplicial complexes, we develop a theory of random monomial ideals. We present theorems about the probability distributions, expectations and thresholds for events of monomial ideals with given Hilbert function, Krull dimension, first graded Betti numbers. We also discuss conjectures about regularity, depth, and Cohen-Macaulayness.

Our new results are joint with Sonja Petrovic, Despina Stasi, Lily Silverstein, Dane Wilburne.

April 20 - Abdul Salam Jarrah, American University of Sharjah & MSRI

Abdul Salam Jarrah

Algebraic Methods for the Inference of Gene Regulatory Networks

Inferring the topology and dynamic of gene regulatory networks from expression time-course data is one of the challenging problems in systems biology. Given time course experimental data, the objective is to identify the structure of the network as well as the rules of interaction among the genes of the network. However, even within the Boolean network framework, there usually are many Boolean networks that explain the available data, and identifying most-likely networks is of great interest. The so-called threshold Boolean networks (TBNs) have been used to model a variety of gene regulatory networks. In a TBN, the future state of each node is determined by a linear inequality of the current states of its neighbors in the network and a threshold. In this talk, I will present an algebraic framework to study the inference problem, and will discuss a new method for inferring all threshold Boolean networks from available time-course data.

April 26 - Alisha Zachariah, University of Wisconsin, Special Day

Note: Special day (Wednesday), 515-615pm, 891 Evans

Alisha Zachariah

Low Complexity (RADAR) Channel Estimation

Several forms of wireless communication involve estimating the channel through which signals are sent. In this talk we will focus on the RADAR channel. My main motivation in this talk is to present an algebraic channel model that has a sophisticated underlying structure. I will present an existing algorithm that uses this and then develop a low complexity improvement that the structure suggests. The lecture should be accessible to any undergraduate student who took a course in linear algebra.

May 4 - Zachary Charles, University of Wisconsin

Zachary Charles

Algebraic Approaches to the Belgian Chocolate Problem

Control theory is concerned with systems that have built-in feedback that regulates their behavior. Control theorists study when the resulting feedback loop is stable. We will present the Belgian Chocolate Problem, a famous open problem concerning the stabilization of such systems. The problem asks for which values of a process parameter we can stabilize a specific feedback loop. In contrast to previous methods that use optimization to search over parameter spaces, we will discuss recent algebraic methods that have led to largest known parameter for which the system can be stabilized. We will present a theorem linking these algebraic "limiting cases" to stable feedback loops. We will also discuss connections between this method and optimization on semi-algebraic varieties.

This is joint work with Nigel Boston.