Low-rank approximation of kernels is a fundamental mathematical problem with widespread algorithmic applications. Often the kernel is restricted to an algebraic variety, e.g., in problems involving sparse or low-rank data. We show that significantly
better approximations are obtainable in this setting: the rank required to achieve a given error depends on the varietys dimension rather than the ambient dimension, which is typically much larger. This is true in both high-precision and high-dimensional regimes. Our results are presented for smooth isotropic kernels, the predominant class of kernels used in applications. Our main technical insight is to approximate smooth kernels by polynomial kernels, and leverage two key properties of polynomial kernels that hold when they are restricted to a variety. First, their ranks decrease exponentially in the varietys co-dimension. Second, their maximum values are governed by their values over a small set of points. Together, our results provide a general approach for exploiting (approximate) algebraic structure in datasets in order to efficiently solve large-scale data science problems.
We study the problem of approximating the cone of positive semidefinite (PSD) matrices with a 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 time
s n$ PSD matrices, denoted by $D$, using at most $N$ number of $k times k$ PSD constraints? In this paper, we prove lower bounds on $N$ to achieve a good approximation of $D$ by considering two constructions of an approximating set. First, we consider the unit-trace $n times n$ symmetric matrices that are PSD when restricted to a fixed set of $k$-dimensional subspaces in $mathbb{RR}^n$. We prove that if this set is a good approximation of $D$, then the number of subspaces must be at least exponentially large in $n$ for any $k = o(n)$. % Second, we show that any set $S$ that approximates $D$ within a constant approximation ratio must have superpolynomial $mathbf{S}_+^k$-extension complexity. To be more precise, if $S$ is a constant factor approximation of $D$, then $S$ must have $mathbf{S}_+^k$-extension complexity at least $exp( C cdot min { sqrt{n}, n/k })$ where $C$ is some absolute constant. In addition, we show that any set $S$ such that $D subseteq S$ and the Gaussian width of $D$ is at most a constant times larger than the Gaussian width of $D$ must have $mathbf{S}_+^k$-extension complexity at least $exp( C cdot min { n^{1/3}, sqrt{n/k} })$. These results imply that the cone of $n times n$ PSD matrices cannot be approximated by a polynomial number of $k times k$ PSD constraints for any $k = o(n / log^2 n)$. These results generalize the recent work of Fawzi on the hardness of polyhedral approximations of $mathbf{S}_+^n$, which corresponds to the special case with $k=1$.
We study the problem of maximizing the geometric mean of $d$ low-degree non-negative forms on the real or complex sphere in $n$ variables. We show that this highly non-convex problem is NP-hard even when the forms are quadratic and is equivalent to o
ptimizing a homogeneous polynomial of degree $O(d)$ on the sphere. The standard Sum-of-Squares based convex relaxation for this polynomial optimization problem requires solving a semidefinite program (SDP) of size $n^{O(d)}$, with multiplicative approximation guarantees of $Omega(frac{1}{n})$. We exploit the compact representation of this polynomial to introduce a SDP relaxation of size polynomial in $n$ and $d$, and prove that it achieves a constant factor multiplicative approximation when maximizing the geometric mean of non-negative quadratic forms. We also show that this analysis is asymptotically tight, with a sequence of instances where the gap between the relaxation and true optimum approaches this constant factor as $d rightarrow infty$. Next we propose a series of intermediate relaxations of increasing complexity that interpolate to the full Sum-of-Squares relaxation, as well as a rounding algorithm that finds an approximate solution from the solution of any intermediate relaxation. Finally we show that this approach can be generalized for relaxations of products of non-negative forms of any degree.
Given a graph, the shortest-path problem requires finding a sequence of edges with minimum cumulative length that connects a source vertex to a target vertex. We consider a generalization of this classical problem in which the position of each vertex
in the graph is a continuous decision variable, constrained to lie in a corresponding convex set. The length of an edge is then defined as a convex function of the positions of the vertices it connects. Problems of this form arise naturally in motion planning of autonomous vehicles, robot navigation, and even optimal control of hybrid dynamical systems. The price for such a wide applicability is the complexity of this problem, which is easily seen to be NP-hard. Our main contribution is a strong mixed-integer convex formulation based on perspective functions. This formulation has a very tight convex relaxation and makes it possible to efficiently find globally-optimal paths in large graphs and in high-dimensional spaces.
We revisit Min-Mean-Cycle, the classical problem of finding a cycle in a weighted directed graph with minimum mean weight. Despite an extensive algorithmic literature, previous work falls short of a near-linear runtime in the number of edges $m$--in
fact, there is a natural barrier which precludes such a runtime for solving Min-Mean-Cycle exactly. Here, we give a much faster approximation algorithm that, for graphs with polylogarithmic diameter, has near-linear runtime. In particular, this is the first algorithm whose runtime for the complete graph scales in the number of vertices $n$ as $tilde{O}(n^2)$. Moreover--unconditionally on the diameter--the algorithm uses only $O(n)$ memory beyond reading the input, making it memory-optimal. The algorithm is also simple to implement and has remarkable practical performance. Our approach is based on solving a linear programming (LP) relaxation using entropic regularization, which effectively reduces the LP to a Matrix Balancing problem--a la the popular reduction of Optimal Transport to Matrix Scaling. We then round the fractional LP solution using a variant of the classical Cycle-Cancelling algorithm that is sped up to near-linear runtime at the expense of being approximate, and implemented in a memory-optimal manner. We also provide an alternative algorithm with slightly faster theoretical runtime, albeit worse memory usage and practicality. This algorithm uses the same rounding procedure, but solves the LP relaxation by leveraging recent developments in area-convexity regularization. Its runtime scales inversely in the approximation accuracy, which we show is optimal--barring a major breakthrough in algorithmic graph theory, namely faster Shortest Paths algorithms.
We revisit Matrix Balancing, a pre-conditioning task used ubiquitously for computing eigenvalues and matrix exponentials. Since 1960, Osbornes algorithm has been the practitioners algorithm of choice and is now implemented in most numerical software
packages. However, its theoretical properties are not well understood. Here, we show that a simple random variant of Osbornes algorithm converges in near-linear time in the input sparsity. Specifically, it balances $Kinmathbb{R}_{geq 0}^{ntimes n}$ after $O(mepsilon^{-2}logkappa)$ arithmetic operations, where $m$ is the number of nonzeros in $K$, $epsilon$ is the $ell_1$ accuracy, and $kappa=sum_{ij}K_{ij}/(min_{ij:K_{ij} eq 0}K_{ij})$ measures the conditioning of $K$. Previous work had established near-linear runtimes either only for $ell_2$ accuracy (a weaker criterion which is less relevant for applications), or through an entirely different algorithm based on (currently) impractical Laplacian solvers. We further show that if the graph with adjacency matrix $K$ is moderately connected--e.g., if $K$ has at least one positive row/column pair--then Osbornes algorithm initially converges exponentially fast, yielding an improved runtime $O(mepsilon^{-1}logkappa)$. We also address numerical precision by showing that these runtime bounds still hold when using $O(log(nkappa/epsilon))$-bit numbers. Our results are established through an intuitive potential argument that leverages a convex optimization perspective of Osbornes algorithm, and relates the per-iteration progress to the current imbalance as measured in Hellinger distance. Unlike previous analyses, we critically exploit log-convexity of the potential. Our analysis extends to other variants of Osbornes algorithm: along the way, we establish significantly improved runtime bounds for cyclic, greedy, and parallelized variants.
This paper presents a selected tour through 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 convex sets have lifts that are dramatically simpler
to describe than the original set. Finding such simple lifts has significant algorithmic implications, particularly for optimization problems. We consider both the classical case of polyhedral lifts, described by linear inequalities, as well as spectrahedral lifts, defined by linear matrix inequalities, with a focus on recent developments related to spectrahedral lifts. Given a convex set, ideally we would either like to find a (low-complexity) polyhedral or spectrahedral lift, or find an obstruction proving that no such lift is possible. To this end, we explain the connection between the existence of lifts of a convex set and certain structured factorizations of its associated slack operator. Based on this characterization, we describe a uniform approach, via sums of squares, to the construction of spectrahedral lifts of convex sets and illustrate the method on several families of examples. Finally, we discuss two flavors of obstruction to the existence of lifts: one related to facial structure, and the other related to algebraic properties of the set in question. Rather than being exhaustive, our aim is to illustrate the richness of the area. We touch on a range of different topics related to the existence of lifts, and present many examples of lifts from different areas of mathematics and its applications.
We study the convex relaxation of a polynomial optimization problem, maximizing a product of linear forms over the complex sphere. We show that this convex program is also a relaxation of the permanent of Hermitian positive semidefinite (HPSD) matric
es. By analyzing a constructive randomized rounding algorithm, we obtain an improved multiplicative approximation factor to the permanent of HPSD matrices, as well as computationally efficient certificates for this approximation. We also propose an analog of van der Waerdens conjecture for HPSD matrices, where the polynomial optimization problem is interpreted as a relaxation of the permanent.
Bravais lattices are the most fundamental building blocks of crystallography. They are classified into groups according to their translational, rotational, and inversion symmetries. In computational analysis of Bravais lattices, fulfilment of symmetr
y conditions is usually determined by analysis of the metric tensor, using either a numerical tolerance to produce a binary (i.e. yes or no) classification, or a distance function which quantifies the deviation from an ideal lattice type. The metric tensor, though, is not scale-invariant, which complicates the choice of threshold and the interpretation of the distance function. Here, we quantify the distance of a lattice from a target Bravais class using strain. For an arbitrary lattice, we find the minimum-strain transformation needed to fulfil the symmetry conditions of a desired Bravais lattice type; the norm of the strain tensor is used to quantify the degree of symmetry breaking. The resulting distance is invariant to scale and rotation, and is a physically intuitive quantity. By symmetrizing to all Bravais classes, each lattice can be placed in a 14 dimensional space, which we use to create a map of the space of Bravais lattices and the transformation paths between them. A software implementation is available online under a permissive license.
The joint spectral radius (JSR) of a set of matrices characterizes the maximal asymptotic growth rate of an infinite product of matrices of the set. This quantity appears in a number of applications including the stability of switched and hybrid syst
ems. A popular method used for the stability analysis of these systems searches for a Lyapunov function with convex optimization tools. We analyse the accuracy of this method for constrained switched systems, a class of systems that has attracted increasing attention recently. We provide a new guarantee for the upper bound provided by the sum of squares implementation of the method. This guarantee relies on the p-radius of the system and the entropy of the language of allowed switching sequences. We end this paper with a method to reduce the computation of the JSR of low rank matrices to the computation of the constrained JSR of matrices of small dimension.
