GOAL Associate Team (2015-...)

Short Description

GOAL led by Bernd Sturmfels (UC Berkeley) and Jean-charles Faugere (POLSYS, Inria Paris) on

“Geometry and Optimization with ALgebraic method"

 The goal of this project is to develop algorithms and mathematical tools to solve geometric and optimization problems through algebraic techniques. As a long-term goal, the joint team plans to develop new software to solve these problems more efficiently. These objectives encompass the challenge of identifying instances of these problems that can be solved in polynomial time with respect to the number of solutions and modeling these problems with polynomial equations. .

List of participants (permanent members)

Objectives of the project

The goal is to develop algorithms and mathematical tools to solve geometric and optimization problems through algebraic techniques. As a long-term goal, we plan to develop new software to solve these problems more efficiently. These objectives encompass the challenge of identifying instances of these problems that can be solved in polynomial time with respect to the number of solutions and modeling these problems with polynomial equations.
Geometry of polynomial optimization. Most of the recent numerical techniques in this context (e.g. those based on semi-definite programming) consist of tracking a path, called the central curve, that is an algebraic curve. The modeling plays an important role since, most of the time, problems can be expressed in a primal or a dual form. Understanding the geometry and the algebraic degree of these curves can allow us to predict which model (primal or dual) should be used. We will also focus on important optimization problems that have an intrinsic geometric description [Baj88]; this is the case for example of the famous Fermat-Weber problem [WF29] that is described in the next section. For both problems numerical methods are available [HRVW96, KK62] but their bit complexity is unknown (the needed precision for the basic arithmetic operations). One can consider exact methods as an alternative. To solve these problems exactly, one can compute a set of univariate polynomials equations whose degree is the algebraic degree. The algebraic degree is usually very big, even for instances of small input size1. The algebraic degree is also useful to estimate the number of digits required to obtain reliable numerical routines. Our goal is to exploit the geometric structure of these problems, to improve numerical techniques, and to obtain dedicated algebraic algorithms for solving them.
Matrix factorizations. Matrix factorizations are a classical and important topic in applied mathematics. In the standard low-rank matrix factorization problem, the goal is to write a given matrix M as a product M = A  B where the intermediate dimension of A and B is as small as possible. In many situations, additional conditions on the factors are required. We will consider the non-negative factorization problem (see [CR93]) and the positive semi-definite factorization problem (see [FGP+14]). Describing the sets of matrices A and B that yield the best factorizations requires considering highly structured systems of polynomial equations and inequalities. In many cases these inequalities imply additional polynomial equations that are hard to discover. A well defined procedure for finding these equations (which is a modeling task) and analyzing the algebraic degree of the sets of equations would yield significant
improvements to the state-of-the-art

Scientific results (2015)

Mixture of Gaussians

The goal is to recover all the parameters of a n-dimensional Gaussian from the set of vectors of moments of order ≤ d. This problem can be reduced to solve a polynomial system of equations. From a geometrical point of view we study the moment variety whose points are the vectors of all moments up to some order of a family of probability distributions. Following up on Pearson’s classical work from 1894, we apply current tools from computational algebra to recover the parameters from the moments. Our moment varieties extend objects familiar to algebraic geometers. For instance, the secant varieties of Veronese varieties are the loci obtained by setting all covariance matrices to zero. We compute the ideals of the 5-dimensional moment varieties representing mixtures of two univariate Gaussians, and we offer a comparison to the maximum likelihood approach.

Moment Varieties of Gaussian Mixtures (arxiv) (C. Améndola, J-C. Faugère and B. Sturmfels), submitted to Journal of Algebraic Statistics.

Activities in 2016

Activities in 2015