Applied Algebra Seminar Fall 2021

When: 11am, Thursdays

Where: Virtual: https://uwmadison.zoom.us/j/93664753217

List: to join email mathaas+join@g-groups.wisc.edu and subscribe to the google group

Contact: Julia Lindberg (Lead) and Jose Israel Rodriguez

Remark: This seminar is held virtually on the first and third Thursday of the month.

Fall 2021 Schedule

date	speaker	title	host(s)
September 16	Jeroen Zuiddam (University of Amsterdam)	Geometric rank of tensors and applications	Virtual
October 7	Timo de Wolff (TU Braunschweig)	Certificates of Nonnegativity and Maximal Mediated Sets	Virtual
October 21	Jesús A. De Loera (UC Davis)	TBD	Virtual
November 4	Kevin Shu (Georgia Tech)	TBD	Virtual
November 18	Angélica Torres (KTH Stockholm)	TBD	Virtual
December 2	Papri Dey (Missouri)	TBD	Virtual

Spring 2021 Schedule

date	speaker	title	host(s)
February 25	Greg Blekherman (Georgia Tech)	Locally Positive Semidefinite Matrices	Virtual
March 25	James Saunderson (Monash University)	Lifting For Simplicity: Concise Descriptions of Convex Sets	Virtual
April 22 (At the new 11am time!)	Hamza Fawzi (Cambridge)	Semidefinite representations, and the set of separable states	Virtual
May 13 (At the new 11am time!)	Anna Seigal (University of Oxford)	Invariant Theory for Maximum Likelihood Estimation	Virtual

Spring 2020 Schedule

date	speaker	title	host(s)
February 20	Carla Michini (UW Madison)	Short simplex paths in lattice polytopes	Local
March 5	Alisha Zachariah (UW Madison)	Efficient Estimation of a Sparse Delay-Doopler Channel	Local
March 19	Spring Break
March 26	(Seminar on Hiatus because of Covid-19)

Timo De Wolff

Certificates of Nonnegativity and Maximal Mediated Sets

In science and engineering, we regularly face polynomial optimization problems, that is: minimize a real, multivariate polynomial under polynomial constraints. Solving these problems is essentially equivalent to certifying of nonnegativity of real polynomials -- a key problem in real algebraic geometry since the 19th century. Since this problem is notoriously hard to solve, one is interested in certificates that imply nonnegativity and are easier to check than nonnegativity itself. In particular, a polynomial is nonnegative if it is a sums of squares (SOS) of other polynomials. In 2014, Iliman and I introduced a new certificate of nonnegativity based on sums of nonnegative circuit polynomials (SONC), which I have developed further since then both in theory and practice joint with different coauthors.

A canonical question is: When is a nonnegative circuit polynomial also a sums of squares. It turns out that this question is purely combinatorial and is governed by sets of particular (integral) lattice points called maximal mediated sets, which where first introduced by Reznick. In this talk, I will give a brief introduction to nonnegativity, SOS, and SONC, and then discuss recent results on maximal mediated sets.

Jeroen Zuiddam

Geometric rank of tensors and applications

There are several important problems in computational complexity and extremal combinatorics that can naturally be phrased in terms of tensors. This includes the matrix multiplication problem, the cap set problem and the sunflower problem. We present a new geometric method in this area, called Geometric Rank (Kopparty–Moshkovitz–Zuiddam, 2020). Geometric Rank is a natural extension of matrix rank to tensors. As an application, we use Geometric Rank to solve a problem of Strassen about matrix multiplication tensors.

Anna Seigal

Invariant Theory for Maximum Likelihood Estimation

Maximum likelihood estimation is an optimization problem over a statistical model, to obtain the parameters that best fit observed data. I will focus on two settings: log-linear models and Gaussian group models. I will describe connections between maximum likelihood estimation and notions of stability from invariant theory. This talk is based on joint work with Carlos Améndola, Kathlén Kohn and Philipp Reichenbach.

Hamza Fawzi

Semidefinite representations, and the set of separable states

The convex set of separable states plays a fundamental role in quantum information theory as it corresponds to the set of non-entangled states. In this talk I will discuss the question of semidefinite programming representations for this convex set. Using connections with nonnegative polynomials and sums of squares I will show that except in the low-dimensions, this semialgebraic set has no semidefinite representation. As a consequence this set furnishes a counter-example to the Helton-Nie conjecture. The proof I will present is elementary and relies only on basic results about semialgebraic sets and functions.

James Saunderson

Lifting For Simplicity: Concise Descriptions of Convex Sets

This talk will give a selective overview of the theory and applications of lifts of convex sets. A lift of a convex set is a higher-dimensional convex set that projects onto the original set. Many interesting convex sets have lifts that are dramatically simpler to describe than the original set. Finding such simple lifts has significant algorithmic implications, particularly for associated optimization problems. We will consider both the classical case of polyhedral lifts, which are described by linear inequalities, as well as spectrahedral lifts, which are defined by linear matrix inequalities. The talk will include discussion of ways to construct lifts, ways to find obstructions to the existence of lifts, and a number of interesting examples from a variety of mathematical contexts. (Based on joint work with H. Fawzi, J. Gouveia, P. Parrilo, and R. Thomas).

---

Greg Blekherman

Locally Positive Semidefinite Matrices

The cone of positive semidefinite matrices plays a prominent role in optimization, and many hard computational problems have well-performing semidefinite relaxations. In practice, enforcing the constraint that a large matrix is positive semidefinite can be expensive. We introduce the cone of k-locally posiitive semidefinite matrices, which consists of matrices all of whose k by k principal submatrices are positive semidefinite. We consider the distance between the cones of positive and locally positive semidefinite matrices, and possible eigenvalues of locally positive semidefinite matrices. Hyperbolic polynomials play a role in some of the proofs. Joint work with Santanu Dey, Marco Molinaro, Kevin Shu and Shengding Sun.

---

Carla Michini

Short simplex paths in lattice polytopes

We consider the problem of optimizing a linear function over a lattice polytope P contained in [0,k]^n and defined via m linear inequalities. We design a simplex algorithm that, given an initial vertex, reaches an optimal vertex by tracing a path along the edges of P of length at most O(n^6 k log k). The length of this path is independent on m and is the best possible up to a polynomial function, since it is only polynomially far from the worst case diameter. The number of arithmetic operations needed to compute the next vertex in the path is polynomial in n, m and log k. If k is polynomially bounded by n and m, the algorithm runs in strongly polynomial time. This is a joint work with Alberto Del Pia.

---

Alisha Zachariah

Efficiently Estimating a Sparse Delay-Doppler Channel

Multiple wireless sensing tasks, e.g., radar detection for driver safety, involve estimating the ”channel” or relationship between signal transmitted and received. In this talk, I will focus on a certain type of channel known as the delay-doppler channel. This channel model starts to be applicable in high frequency carrier settings, which are increasingly common with recent developments in mmWave technology. Moreover, in this setting, both the channel model and existing technologies are amenable to working with signals of large bandwidth, and using such signals is a standard approach to achieving high resolution channel estimation. However, when high resolution is desirable, this approach creates a tension with the desire for efficiency because, in particular, it immediately implies that the signals in play live in a space of very high dimension N (e.g., ~10^6 in some applications), as per the Shannon-Nyquist sampling theorem.

To address this, I will propose a randomized algorithm for channel estimation in the k-sparse setting (e.g., k objects in radar detection), with sampling and space complexity both on the order of k(log N)^2, and arithmetic complexity on the order of k(log N)^3+k^2, for N sufficiently large.

While this algorithm seems to be extremely efficient -- to the best of our knowledge, the first of this nature in terms of complexity -- it is just a simple combination of three ingredients, two of which are well-known and widely used, namely digital chirp signals and discrete Gaussian filter functions, and the third being recent developments in Sparse Fast Fourier Transform algorithms.

---

Related events to note

date	event/title	location/speaker	info
Postponed	Applied Algebra Days 4 - Tensors	Several talks on tensors
1:30pm, 2nd Thursday of the month	Informal Seminar: Algebra in Statistics and Computation	Virtual
3:30pm	SIAM Student Chapter	Virtual
10am, 2nd Tuesday of the month	SIAM SAGA	Virtual: Recordings	Registration needed once.
10am, Most Tuesdays	Nonlinear algebra seminar online	Virtual: Recordings	Registration required once
Biweekly Mondays	Algebraic Statistics Online Seminar (ASOS)	Virtual: Recordings	Mailing list sign-up for Zoom-links
January 26th-29th, 2021	Sanya Workshop on Algebraic Geometry and Machine Learning	Virtual: Recordings
July 29-30, 2021	Real algebraic geometry and convex geometry Conference	TBD: TU Braunschweig, Germany or Online

---