seminar
09/08/2021 07/06/2022

# Numerical Algebra and Optimization Seminar

### Previous Events

 07.06.2022 Vyacheslav Kungurtsev (Czech Technical University Prague) Simultaneous Online Model Identification and Production Optimization Using Modifier Adaptation and Reinforcement Learning A key problem for many industrial processes is to limit exposure to system malfunction. However, it is often the case that control cost minimization is prioritized over model identification. Indeed, model identification is typically not considered in production optimization, which can lead to delayed awareness and alerting of malfunction. In this talk, I will discuss strategies to address the problem of simultaneous production optimization and system identification. In particular, presenting new algorithms based on modifier adaptation and reinforcement learning, which efficiently manage the tradeoff between cost minimization and identification. For two case studies based on a chemical reactor and subsea oil and gas exploration, we show that our algorithms yield control costs comparable to existing methods while yielding rapid identification of system degradation.
 06.12.2021 Henrik Eisenmann (MPI MiS, Leipzig) Maximum distance of a symmetric rank-two tensor to rank-one tensors We investigate the maximum distance of a symmetric rank-two tensor to rank-one tensors. An equivalent problem is given by the minimal ratio of spectral and Frobenius norm of a tensor. For matrices the distance of a rank k matrix to a rank r matrices is given by the singular value decomposition, but since there is a lack of a fitting analog of the singular value decomposition for tensors, this question is more difficult in the regime of tensors. 06.12.2021 Nick Dewaele (KU Leuven) Computing the condition number of tensor decompositions through Tucker compression Several computational problems in data science and signal processing can be understood as finding a decomposition of a tensor. In contrast to matrices, tensor decompositions are often unique with minimal constraints. This property makes it possible to have a unique interpretation of the decomposition of the tensor. This is the case for decompositions like the (symmetric) tensor rank and block term decomposition. One caveat, however, is that the decomposition may be highly sensitive with respect to the tensor. This sensitivity is measured by the condition number, which determines up to what precision the decomposition can be known. We will discuss an algorithm to compute the condition number of several of tensor decompositions. In practical computations, one often represents a tensor in a minimal subspace prior to computing its decomposition. This dimensionality reduction technique, known as Tucker compression, can dramatically speed up the computation of the decomposition. Thus, it is natural to ask whether this technique changes to condition number. In recent work, we showed that the answer is negative. We illustrate how this result can be used to speed up the computation of the condition number by several orders of magnitude. 25.10.2021 Sylvain Spitz (TU Berlin) Generalized Permutahedra and Optimal Auctions We study a family of convex polytopes, called SIM-bodies, which were introduced by Giannakopoulos and Koutsoupias (2018) to analyze so-called Straight-Jacket Auctions. First, we show that the SIM-bodies belong to the class of generalized permutahedra. Second, we prove an optimality result for the Straight-Jacket Auctions among certain deterministic auctions. Third, we employ computer algebra methods and mathematical software to explicitly determine optimal prices and revenues. 18.10.2021 Rainer Sinn (Universität Leipzig) Chirality in Computer Vision A fundamental question in computer vision is whether a set of point pairs is the image of a scene that lies \textbf{in front} of cameras. Such a scene and the cameras together are known as a chiral reconstruction of the point pairs. We discuss how this constraint “to be in front of" can be expressed in terms of polynomial inequalities in real projective space. In particular, we focus on the case of two cameras which has connections to classical (real) geometry of cubic hypersurfaces. 11.10.2021 Melina Freitag (Universität Potsdam) Optimisation and numerical linear algebra in data assimilation Data assimilation is a method that combines observations (e.g. real world data) of a state of a system with model output for that system in order to improve the estimate of the state of the system and thereby the model output. The model is usually represented by a discretised partial differential equation. The data assimilation problem can be formulated as a large scale Bayesian inverse problem. Based on this interpretation we derive the most important variational and sequential data assimilation approaches, in particular three-dimensional and four-dimensional variational data assimilation (3D-Var and 4D-Var), and the Kalman filter. We will then consider more advanced methods which are extensions of the Kalman filter and variational data assimilation. The data assimilation problem usually results in very large optimisation problems and/or very large linear systems to solve. Hence, the final part of this talk aims to review advances and challenges, in particular from the point of view of numerical linear algebra, within the various data assimilation approaches. 04.10.2021 Myfanwy Evans (Universität Potsdam) Packings, frameworks and tensegrity structures In this talk, I will present a variety of interesting geometric objects that can be studied to gain a deeper understanding of biological and chemical structures. The movements of these structures in space can be considered from the perspective of algebraic geometry, and the question becomes: can we find the parallels between real material behaviour and algebraic properties? 27.09.2021 Johannes Maly (Katholische Universität Eichstätt-Ingolstadt) Robust Sensing of Low-Rank Matrices with Non-Orthogonal Sparse Decomposition We consider the problem of recovering an unknown low-rank matrix X with (possibly) non-orthogonal, effectively sparse rank-1 decomposition from incomplete and inaccurate measurements y gathered in a linear measurement process A. We propose a variational formulation that lends itself to alternating minimization and whose global minimizers provably approximate X from y up to noise level. Working with a variant of robust injectivity, we derive reconstruction guarantees for various choices of A including sub-gaussian, Gaussian rank-1, and heavy-tailed measurements. Numerical experiments support the validity of our theoretical considerations. 13.09.2021 Russell Luke (Georg-August-Universität Göttingen) Structured (In)Feasibility: Nonmonotone Operator Splitting in Nonlinear Spaces The success of operator splitting techniques for convex optimization has led to an explosion of methods for solving large-scale and nonconvex optimization problems via convex relaxation. This success is at the cost of overlooking direct approaches to operator splitting that embrace some of the more inconvenient aspects of many model problems, namely nonconvexity, nonsmoothness and infeasibility. I will introduce some of the tools we have developed for handling these issues, and present sketches of the basic results we can obtain. The formalism is in general metric spaces, but most applications have their basis in Euclidean spaces. Along the way I will try to point out connections to other areas of intense interest, such as optimal mass transport. 06.09.2021 Sebastian Neumayer (TU Berlin) Invertible Neural Networks for Inverse Problems In this talk, I will discuss invertible neural networks, which can be used for modelling inverse problems. If properly trained, such networks provide a way for efficiently sampling from the posterior. Starting from the theoretical analysis of the related optimization problem, we will discuss some practical implications of the established results based on numerical examples. At the end, I will outline some open issues. 30.08.2021 Dogyoon Song (Massachusetts Institute of Technology) On Approximating Positive Semidefinite Cone Using Small-sized PSD Constraints We study the problem of approximating the cone of positive semidefinite (PSD) matrices with a convex cone that can be described by smaller-sized PSD constraints. Specifically, we ask the question: "how closely can we approximate the set of unit-trace $n \times n$ positive semidefinite (PSD) matrices, denoted by $D$, using at most $N$ number of $k \times k$ PSD constraints?" We show that any set that approximates $D$ within a constant approximation ratio must have superpolynomially large $k$-semidefinite extension complexity when $k = o(n / \log n)$. 25.08.2021 Max Pfeffer (TU Chemnitz) Constrained Matrix and Tensor Factorizations The aim of this talk is to give an overview over our research on constrained matrix and tensor factorizations. We give an introduction into these factorizations and into possible constraints. Furthermore, we discuss joint factorizations in data fusion. Several methods for their computation are considered, which are fitted to the respective constraints. Finally, some applications in various states of completion are presented. 16.08.2021 Guido Montufar (MPI MiS, Leipzig + University of California, LA) Geometry of Linear Convolutional Networks We study the family of functions that are represented by a linear convolutional neural network (LCN). These functions form a semi-algebraic subset of the set of linear maps from input space to output space. In contrast, the families of functions represented by fully-connected linear networks form algebraic sets. We observe that the functions represented by LCNs can be identified with polynomials that admit certain factorizations, and we use this perspective to describe the impact of the network’s architecture on the geometry of the resulting function space. We further study the optimization of an objective function over an LCN, analyzing critical points in function space and in parameter space, and describing dynamical invariants for gradient descent. Overall, our theory predicts that the optimized parameters of an LCN will often correspond to repeated filters across layers, or filters that can be decomposed as repeated filters. We also conduct numerical and symbolic experiments that illustrate our results and present an in-depth analysis of the landscape for small architectures. This is joint work with Kathlen Kohn, Thomas Merkh, and Matthew Trager. 09.08.2021 Venkat Chandrasekaran (California Institute of Technology, Pasadena) Fitting Convex Sets to Data A number of problems in signal processing may be viewed conceptually as fitting a convex set to data. In vision and learning, the task of identifying a collection of features or atoms that provide a concise description of a dataset has been widely studied under the title of dictionary learning or sparse coding. In convex-geometric terms, this problem entails learning a polytope with a desired facial structure from data. In computed tomography, reconstructing a shape from support measurements arises commonly in MRI, robotics, and target reconstruction from radar data. This problem is usually reformulated as one of estimating a polytope from a collection of noisy halfspaces. In this talk we describe new approaches to these problems that leverage contemporary ideas from the optimization literature on lift-and-project descriptions of convex sets. This perspective leads to natural semidefinite programming generalizations of previous techniques for fitting polyhedral convex sets to data. We provide several stylized illustrations in which these generalizations provide improved reconstructions. On the algorithmic front our methods rely prominently on operator scaling, while on the statistical side our analysis builds on links between learning theory and semialgebraic geometry.