TU Berlin

Fachgebiet Algorithmische AlgebraAlgebra Meets Numerics: Condition and Complexity

Inhalt des Dokuments

zur Navigation

Algebra meets Numerics: Condition and Complexity

Lupe

Summary

This workshop is funded within the project "Complexity and accuracy of numerical algorithms in algebra and geometry" by the Einstein Foundation (2017-2019).

Recently, it became apparent that for many computational problems, a synthesis of algebraic and numerical methods provides the most promising approach. Since one deals with approximate computations and errors, the concept of condition is central for designing and analyzing algorithms.

The goal of the workshop is to introduce the motivation, background, and to present some state-of-the-art results.

Venue

November 6

Lupe

Berlin-Brandenburg Academy of Sciences and Humanities (BBAW)
Jägerstrasse 22/23 (Right next to the Gendarmenmarkt)
Link to the BBAW

Nearby metro stations: U2 Hausvogteiplatz and U6 Französische Straße

Room: 01.03 Workshopraum 2 (1st floor)

November 7

Lupe

TU Berlin
Institut für Mathematik

Straße des 17. Juni 136
Link to the Institute of Mathematics of TU Berlin

Nearby Metro stations: U2 Ernst-Reuter-Platz and S3/S5/S7/S75 Tiergarten.

Room: MA 313/14 (3rd floor)

Schedule

A self-paid workshop dinner is planned for the evening of November 6.

November 6
Speaker
Title
Time
Gregorio Malajovich
On the Complexity of Sparse Polynomial Solving
900-950
Alperen Ergür
Probabilistic Condition Number Estimates for Real Polynomial Systems
950-1040
Break
Carlos Beltran
On the condition number of the polynomial eigenvalue problem
1110-1200
Lunch (and Coffee)
Paul Breiding
The condition number of the tensor rank decomposition problem
1400-1450
Nick Vannieuwenhoven
A Riemannian trust region method for the canonical tensor rank approximation problem
1450-1540
Break
Alex Townsend
Worst-case numerical instability of algebraic-geometric methods for solving multivariate polynomial systems
1610-1700
Antonio Lerario
Random rational ​maps​
1700-1750
November 7
Speaker
Title
Time
Martin Lotz
Condition number bounds in convex regularization
800-850
Vanni Noferini
The structured condition number of a differentiable map between matrix manifolds
850-940
Break
Nicolai Vorobjov
Upper bounds on homotopy and homology of definable sets
1020-1110
Felipe Cucker
Computing the homology of basic semialgebraic sets 
1110-1200
Lunch (and Coffee)
Josue
Tonelli-Cueto
Computing the homology of general semialgebraic sets
1400-1450
Jose Israel Rodriguez
Trace test
1450-1540
Further discussion

Abstracts

On the condition number of the polynomial eigenvalue problem

Speaker: Carlos Beltran

I will present a recent result with Diego Armentano where we compute the exact value of the expected squared condition number for the polynomial eigenvalue problem. 

In a few words, our result justifies the fact that one can usually solve these problems with seemingly accurate numerical methods.

The condition number of the tensor rank decomposition problem

Speaker: Paul Breiding

In this talk I want to discuss the condition number of the tensor rank decomposition problem (TRDP). I will explain why for many ranks the TRDP is not ill-posed (contrary to the matrix rank decomposition problem). Moreover,  I will show you the behavior of the condition number close to points where rank and border-rank differ. Finally, I will describe the condition number as the inverse distance to some ill-posed set in a product of Grassmannians and give some perspectives how one could get such a 'condition number theorem' also in the tensor space itself. (Joint work with Nick Vannieuwenhoven)

Computing the homology of basic semialgebraic sets

Speaker: Felipe Cucker

We describe a numerical algorithm computing the homology of a basic semialgebraic set from the coefficients of the defining polynomials in dense representation. The algorithm is numerically stable in the sense that the precision required to guarantee a correct output depends on the condition number of the data and it is polynomially small. Its running time also depends on this condition but it is bounded by a singly exponential bound on the size of the input out of a vanishingly small set of data. 

Probabilistic Condition Number Estimates for Real Polynomial Systems

Speaker: Alperen Ergür

We study the sensitivity of the real roots of real polynomial systems to the perturbations in the coefficients. In particular, -for the condition number introduced by Cucker, Krick, Malajovich, and Wschebor- we establish probabilistic estimates that allow a much broader family of measures than considered earlier.

Random rational ​maps​

Speaker: Antonio Lerario

In this talk I will ​introduce the notion of random rational maps and discuss some of their properties.

The number of the singularities of their images (e.g., the number of nodes in the case of plane rational curves) is related to the volume of secant varieties, which in turn gives the measure of the set of symmetric tensors with a given Waring rank. 

(This is based on joint work with S. Basu, E. Lundberg and C. Peterson.)

Condition number bounds in convex regularization

Speaker: Martin Lotz

A common approach to solving underdetermined or ill-posed least squares problems with structural constraints (such as sparsity or low rank) is to include a convex regularization term in the objective function. One parameter that controls the performance of such a convex regularization is the statistical dimension of the regularizer. Such a regularizer often has the form g(x) = f(Dx), where f is a convex function (often a norm) and D a linear map (for example, a finite difference map). Even if the statistical dimension of f is known, determining that of g can be a challenging problem. 

We show that the statistical dimension of g can be bounded in terms of that of f and Renegar's condition number of D with respect to the descent cone of f. 

Since the map D is often ill-conditioned, even in very natural settings such as total variation regularization, such a bound is, in general, not very effective. 

Using a suprising result from integral geometry, the TQC Lemma, we show that this bound can be improved dramatically by replacing Renegars condition number of D with its expectation under a random projection of D. We discuss some open problems related to the conditioning of random projections of given matrices.

Joint work with Dennis Amelunxen and Jake Walvin

On the Complexity of Sparse Polynomial Solving

Speaker: Gregorio Malajovich

We know at this time that it is possible to find one root of a random dense polynomial system in time polynomial in the number of coefficients. In this talk I shall address the problem of solving sparse polynomial systems indeed. In order to avoid ill-posedness, one needs to look for roots in a certain toric variety rather than in ordinary projective space. This motivates the introduction of a sparse condition number and of certain group actions related to the new setting.

The structured condition number of a differentiable map between matrix manifolds

Speaker: Vanni Noferini

We discuss the structured condition number of differentiable maps between differentiable matrix manifolds, thus developing a theoretical framework that extends previous results on vector subspaces. We develop algorithms to compute the structured condition number. Then, we derive a lower bound on the structured condition number which can be much cheaper to compute, and an algorithm for computing the bound. Finally, as an application, we provide numerical comparisons between the structured and unstructured condition numbers for matrices in automorphism groups and various maps: the matrix logarithm, the matrix square root, the polar decomposition, and the sign decomposition. We argue that the cheaply computable lower bound is often a good estimate of the structured condition number; moreover, we show experimentally that the structured and unstructured condition numbers can differ by several order of magnitude, thus motivating the future development of more structure-preserving algorithms.

This talk is based on joint work with Bahar Arslan (Technical University of Bursa) and Françoise Tisseur (University of Manchester).

Trace test

Speaker: Jose Israel Rodriguez 

Numerical algebraic geometry uses numerical algorithms to study algebraic varieties, which are sets defined by polynomial equations. It is becoming a core tool in applications of algebraic geometry outside of mathematics. Its fundamental concept is a witness set which gives a representation of a variety that may be manipulated on a computer. The trace test is used to verify that a witness set is complete and provide stopping criteria for algorithms. In this talk we discuss witness sets and how the trace test is used in applications. Moreover, we show how a dimension reduction leads to a new practical trace test for algebraic varieties in product spaces, which is the natural setting for solutions of parameterized polynomial systems. 

Joint work with Anton Leykin and Frank Sottile: arxiv.org/pdf/1608.00540.pdf

Computing the homology of general semialgebraic sets

Speaker: Josue Tonelli-Cueto

The methods and techniques of (Cucker, Krick & Shub, 2016) and (Bürgisser, Cucker & Lairez, 2017) allows us to compute the homology of basic semialgebraic sets in weak single exponential time. The main issue in order to generalise this ideas beyond the basic semialgebraic sets is that the reach of a general semialgebraic set is generally zero, which means that the main technique for computing homology in the basic case cannot be applied to general semialgebraic sets. However, using the tools of algebraic topology and some stronger results from semialgebraic geometry one can work around this difficulty and compute the homology of general semialgebraic sets numerically in weak single exponential time. This talk will give the main ideas of how this can be done. Work in progress.

Worst-case numerical instability of algebraic-geometric methods for solving multivariate polynomial systems

Speaker: Alex Townsend

Two popular numerical ways to globally solve multidimensional polynomial systems are hidden-variable resultant methods and Grobner bases. 

In two dimensions, when significant care is taken, hidden-variable resultant methods are competitive numerical rootfinders.  

However, in higher dimensions both resultants and Grobner bases are notoriously difficult to make numerically robust.  

We will show that the most popular variants of these two methods are inherently numerically unstable by a factor that grows exponentially with dimension in the worst case.

A Riemannian trust region method for the canonical tensor rank approximation problem

Speaker: Nick Vannieuwenhoven

In recent years, tensors have found application in a growing number of applications, and tensor decompositions are now increasingly employed for revealing practical multi-linear structures underlying multidimensional data. A signature application of the tensor CP decomposition (CPD) was devised by Appellof and Davidson (1981) who showed that fluorophores in a collection of diluted chemical mixtures can be identified naturally from this decomposition of the multidimensional data array that is sampled in fluorescence spectroscopy experiments. 

Unfortunately, in applications, we are not usually dealing with tensors that admit a mathematically exact CPD with few summands, because of the usual representation, roundoff, measurement, and model errors. Therefore, one is usually interested in finding a closest low-rank CPD near a given tensor. This tensor canonical rank approximation (TAP) problem is naturally formulated as a nonlinear least squares problem where the constraint set forms a non-smooth semi-algebraic set. 

In this talk, we consider a Riemannian Gauss-Newton (RGN) method with trust region for solving TAPs. First, we show how the constraint set can be parameterized as the Cartesian product of Segre manifolds, hereby formulating the TAP as a Riemannian optimization problem. It is argued theoretically from geometrical considerations why this parametrization is among the best possible. Second, it is shown that the radius and rate of local convergence of this RGN method are intimately related to the TAP's condition number. We also show that the local convergence of current state-of-the-art optimization methods for the TAP are governed by a different condition number. Our analysis shows specifically that problems with large differences in scaling of the terms in the CPD should best be treated with the proposed RGN method as it is insensitive to this. Third, an analysis shows that some types of ill-conditioned CPDs are particularly troublesome for any RGN process. We introduce a hot restart mechanism that efficiently detects when the optimization process is tending to an ill-conditioned CPD and which often yields a quick escape path from such spurious decompositions. Numerical experiments show improvements of up to two orders of magnitude in terms of the execution time over existing state-of-the-art methods.

This is joint work with Paul Breiding.

Upper bounds on homotopy and homology of definable sets

Speaker: Nicolai Vorobjov

I will describe a number of tools useful in proving upper bounds on homotopy and homology (in particular, Betti numbers) of sets definable in an o-minimal structure over the reals (e.g., semi-algebraic or real subanalytic sets).

Registration

For registration, write an e-mail to  with subject "Registration Condition and Complexity" and body of the e-mail as follows:

Name: This-is-my-name-surname
Affiliation: This-is-my-institution

Although registration is not compulsory, it's recommended.

Participants

  • Lamprini Ananiadi (Otto-von-Guericke-Universität Magdeburg)
  • Carlos Beltran (Universidad de Cantabria)
  • Paul Breiding (MPI Leipzig)
  • Peter Bürgisser (TU Berlin)
  • Felipe Cucker (CityU Hong Kong)
  • Alperen Ergür (TU Berlin)
  • Alexandru Iosif (Otto-von-Guericke-Universität Magdeburg)
  • Antonio Lerario (Scuola Internazionale Superiore di Studi Avanzati)
  • Martin Lotz (University of Manchester)
  • Gregorio Malajovich (Universidade Federal do Rio de Janeiro)
  • Matthias Miltenberger (Zuse Institute Berlin)
  • Vanni Noferini (University of Essex)
  • Jose Israel Rodriguez (University of Chicago)
  • Josue Tonelli-Cueto (TU Berlin)
  • Alex Townsend (Cornell University)
  • Nick Vannieuwenhoven (KU Leuven)
  • Nicolai Vorobjov (University of Bath)

 

 

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe