Computer Science

I plan to survey some parts of Strassen's seminal body of work on the theory of asymptotic spectra, in which optimization and symmetry play crucial roles. In particular, I will motivate and explain the notion of asymptotic spectra, Strassen's duality theorem (far reaching generalization of linear programming duality, with connections to Positivstellensatz), and Strassen's connectivity theorem of the spectra of matrix multiplication.

The Kronecker coefficients of the symmetric group are the multiplicities of irreducible representations in the decomposition of the tensor product of two other irreducible representations. Ever since their definition by Murnaghan more than 80 years ago they've presented a major mystery and open problem in Algebraic Combinatorics. Recently they have come to play a crucial role in Geometric Complexity Theory in the quest for separation of VP and VNP. In this talk I'll give a broad overview of this topic with respect to combinatorics, asymptotics and computational complexity.

The state of a system of several quantum particles is an element in the tensor product of Hilbert spaces. In certain situations, the inner product requirement can be relaxed. Quantum states then turn into tensors, and tools and intuition from quantum information, algebraic geometry and algebraic complexity can connect. I will explain the two main traits of application, each leading to an optimization problem. The first is to quantum entanglement - the strong correlations among quantum particles - leading to an optimization over moment polytopes. The second is to many-body physics, where tensor networks are used as an ansatz class to describe the intricate correlations in quantum materials.

We study the average complexity of solving structured polynomial systems that are characterised by a low evaluation cost, as opposed to the dense random model previously used. Firstly, we design a continuation algorithm that computes, with high probability, an approximate zero of a polynomial system given only as black-box evaluation program. Secondly, we introduce a universal model of random polynomial systems with prescribed evaluation complexity L. Combining both, we show that we can compute an approximate zero of a random structured polynomial system with n equations of degree at most d in n variables with only poly(n,d) L operations with high probability. This exceeds the expectations implicit in Smale's 17th problem. This is joint work with Felipe Cucker and Pierre Lairez, see arXiv:2010.10997.

Groups and symmetries are at the heart of many problems in statistics and data analysis. I will focus on parameter estimation in statistical models via maximum likelihood estimation. We will see connections between maximum likelihood estimation, linear algebra, and invariant theory. The group or symmetric structure of a statistical model can be used to capture the existence and uniqueness of a maximum likelihood estimate, as well as to suggest suitable algorithms to find it. This talk is based on joint work with Carlos Améndola, Kathlén Kohn, Visu Makam, and Philipp Reichenbach.

The simplest homogeneous polynomials with nonnegative coefficients are products of linear forms Prod_{A}(X) associated with nonnegative matrices A. We prove that for any H-Stable(homogeneous and stable) polynomial p with P(E) = 1, where E is the vector of all ones, it's value p(X) = Prod_{A(X)}(X), where A(X) is nonnegative matrix with unit row sums and the vector of column sums equal to the gradient of p at E. I will first explain some intuition, and history, behind the result; sketch the proof and present a few applications and generalizations of this "productization" property. (Joint work with Jonathan Leake).

Exponential densities on unitary conjugation orbits of Hermitian matrices, known as Harish-Chandra-Itzykson-Zuber (HCIZ) densities, are important in various settings in physics and random matrix theory. However, the basic question of efficient sampling from these densities has remained open. We present two efficient algorithms to sample matrices from distributions that are close to the HCIZ distribution. Both algorithms exploit a natural self-reducible structure that arises from continuous symmetries of the underlying unitary orbit. We will also discuss applications to quantum inference and differentially private rank-k approximation.

Maximum entropy distributions on discrete domains have been studied in a number of contexts over the past few decades. In particular, they have been used in deterministic algorithms for the approximation of the permanent, scaling problems for torus actions, applications of spanning tree sampling problems, and beyond. These applications are intimately linked to distributions on some finite support set, with a given expectation, and which maximize entropy. In this talk, we will discuss the generalization of maximum entropy distributions from finite discrete support sets to continuous manifolds. Such distributions arise in connection to a number of topics; for example, quantum entropy, interior point methods, matrix distributions studied in statistics, the isotropic constant, and low-rank matrix approximation. We will discuss a few of these applications, along with some of the computability issues which arise when moving from discrete support to continuous. We will also briefly discuss the connection between this generalization and the norm minimization techniques used for general scaling problems. This is joint work with Nisheeth Vishnoi.

Many applications involve non-Euclidean data, where exploiting Riemannian geometry can deliver algorithms that are computationally superior to standard nonlinear programming approaches. This observation has resulted in an increasing interest in Riemannian methods in the optimization and machine learning community. In this talk, we consider the problem of optimizing a function on a Riemannian manifold subject to convex constraints. We introduce Riemannian Frank-Wolfe (RFW) methods, a class of projection-free algorithms for constrained geodesically convex optimization. To understand the algorithm’s efficiency, we discuss (1) its iteration complexity, (2) the complexity of computing the Riemannian gradient, and (3) the complexity of the Riemannian “linear” oracle (RLO), a crucial subroutine at the heart of the algorithm. We complement our theoretical results with an empirical comparison of RFW against state-of-the-art Riemannian optimization methods. Joint work with Suvrit Sra (MIT).

The matrix normal model, the family of Gaussian matrix-variate distributions whose covariance matrix is the Kronecker product of two lower dimensional factors, is frequently used to model matrix-variate data. The tensor normal model generalizes this family to Kronecker products of three or more factors. We study the estimation of the Kronecker factors of the covariance matrix in the matrix and tensor models. We show nonasymptotic bounds for the error achieved by the maximum likelihood estimator (MLE) in several natural metrics. In contrast to existing bounds, our results do not rely on the factors being well-conditioned or sparse. For the matrix normal model, all our bounds are minimax optimal up to logarithmic factors, and for the tensor normal model our bound for the largest factor and overall covariance matrix are minimax optimal up to constant factors provided there are enough samples for any estimator to obtain constant Frobenius error. In the same regimes as our sample complexity bounds, we show that an iterative procedure to compute the MLE known as the flip-flop algorithm converges linearly with high probability. Our main tool is geodesic strong convexity in the geometry on positive-definite matrices induced by the Fisher information metric. This strong convexity is determined by the expansion of certain random quantum channels. We also provide numerical evidence that combining the flip-flop algorithm with a simple shrinkage estimator can improve performance in the undersampled regime.

In this paper, we address the noncommutative rank (nc-rank) computation of a linear symbolic matrix A=A1 x1+A2 x2 +⋯+ Am xm, where each Ai is an n x n matrix over a field K, and xi (i=1,2,…,m) are noncommutative variables. For this problem, polynomial time algorithms were given by Garg, Gurvits, Oliveira, and Wigderson for K=Q, and by Ivanyos, Qiao, and Subrahmanyam for an arbitrary field K. We present a significantly different polynomial time algorithm that works on an arbitrary field K. Our algorithm is based on a combination of submodular optimization on modular lattices and convex optimization on CAT(0) spaces.

Given many identical copies of a quantum particle, what's the chance measuring their overall angular momentum yields zero? We show how to frame this problem as an optimization problem over a matrix group. We'll then discuss the relationship between this optimization problem and invariant theory, quantum tomography, and the Jacobian conjecture. This talk is based on the joint work https://arxiv.org/abs/2004.14872 with Michael Walter.