
The matrix logarithm, when applied to Hermitian positive definite matrices,
is concave with respect to the positive semidefinite order. This operator
concavity property leads to numerous concavity and convexity results for other
matrix functions, many of which are of importance in quantum information
theory. In this paper we show how to approximate the matrix logarithm with
functions that preserve operator concavity and can be described using the
feasible regions of semidefinite optimization problems of fairly small size.
Such approximations allow us to use offtheshelf semidefinite optimization
solvers for convex optimization problems involving the matrix logarithm and
related functions, such as the quantum relative entropy. The basic ingredients
of our approach apply, beyond the matrix logarithm, to functions that are
operator concave and operator monotone. As such, we introduce strategies for
constructing semidefinite approximations that we expect will be useful, more
generally, for studying the approximation power of functions with small
semidefinite representations.

Many important problems are characterized by the eigenvalues of a large
matrix. For example, the difficulty of many optimization problems, such as
those arising from the fitting of large models in statistics and machine
learning, can be investigated via the spectrum of the Hessian of the empirical
loss function. Network data can be understood via the eigenstructure of a graph
Laplacian matrix using spectral graph theory. Quantum simulations and other
manybody problems are often characterized via the eigenvalues of the solution
space, as are various dynamic systems. However, naive eigenvalue estimation is
computationally expensive even when the matrix can be represented; in many of
these situations the matrix is so large as to only be available implicitly via
products with vectors. Even worse, one may only have noisy estimates of such
matrix vector products. In this work, we combine several different techniques
for randomized estimation and show that it is possible to construct unbiased
estimators to answer a broad class of questions about the spectra of such
implicit matrices, even in the presence of noise. We validate these methods on
largescale problems in which graph theory and random matrix theory provide
ground truth.

We consider a new and general online resource allocation problem, where the
goal is to maximize a function of a positive semidefinite (PSD) matrix with a
scalar budget constraint. The problem data arrives online, and the algorithm
needs to make an irrevocable decision at each step. Of particular interest are
classic experiment design problems in the online setting, with the algorithm
deciding whether to allocate budget to each experiment as new experiments
become available sequentially.
We analyze two greedy primaldual algorithms and provide bounds on their
competitive ratios. Our analysis relies on a smooth surrogate of the objective
function that needs to satisfy a new diminishing returns (PSDDR) property
(that its gradient is orderreversing with respect to the PSD cone). Using the
representation for monotone maps on the PSD cone given by L\"owner's theorem,
we obtain a convex parametrization of the family of functions satisfying
PSDDR. We then formulate a convex optimization problem to directly optimize
our competitive ratio bound over this set. This design problem can be solved
offline before the data start arriving. The online algorithm that uses the
designed smoothing is tailored to the given cost function, and enjoys a
competitive ratio at least as good as our optimized bound. We provide examples
of computing the smooth surrogate for Doptimal and Aoptimal experiment
design, and demonstrate the performance of the customdesigned algorithm.

If $X$ is an $n\times n$ symmetric matrix, then the directional derivative of
$X \mapsto \det(X)$ in the direction $I$ is the elementary symmetric polynomial
of degree $n1$ in the eigenvalues of $X$. This is a polynomial in the entries
of $X$ with the property that it is hyperbolic with respect to the direction
$I$. The corresponding hyperbolicity cone is a relaxation of the positive
semidefinite (PSD) cone known as the first derivative relaxation (or Renegar
derivative) of the PSD cone. A spectrahedal cone is a convex cone that has a
representation as the intersection of a subspace with the cone of PSD matrices
in some dimension. We show that the first derivative relaxation of the PSD cone
is a spectrahedral cone, and give an explicit spectrahedral description of size
$\binom{n+1}{2}1$. The construction provides a new explicit example of a
hyperbolicity cone that is also a spectrahedron. This is consistent with the
generalized Lax conjecture, which conjectures that every hyperbolicity cone is
a spectrahedron.

It is wellknown that any sum of squares (SOS) program can be cast as a
semidefinite program (SDP) of a particular structure and that therein lies the
computational bottleneck for SOS programs, as the SDPs generated by this
procedure are large and costly to solve when the polynomials involved in the
SOS programs have a large number of variables and degree. In this paper, we
review SOS optimization techniques and present two new methods for improving
their computational efficiency. The first method leverages the sparsity of the
underlying SDP to obtain computational speedups. Further improvements can be
obtained if the coefficients of the polynomials that describe the problem have
a particular sparsity pattern, called chordal sparsity. The second method
bypasses semidefinite programming altogether and relies instead on solving a
sequence of more tractable convex programs, namely linear and second order cone
programs. This opens up the question as to how well one can approximate the
cone of SOS polynomials by second order representable cones. In the last part
of the paper, we present some recent negative results related to this question.

We consider the problem of finding sum of squares (sos) expressions to
establish the nonnegativity of a symmetric polynomial over a discrete
hypercube whose coordinates are indexed by the $k$element subsets of $[n]$.
For simplicity, we focus on the case $k=2$, but our results extend naturally to
all values of $k \geq 2$. We develop a variant of the GatermannParrilo
symmetryreduction method tailored to our setting that allows for several
simplifications and a connection to flag algebras.
We show that every symmetric polynomial that has a sos expression of a fixed
degree also has a succinct sos expression whose size depends only on the degree
and not on the number of variables. Our method bypasses much of the technical
difficulties needed to apply the GatermannParrilo method, and offers
flexibility in obtaining succinct sos expressions that are combinatorially
meaningful. As a byproduct of our results, we arrive at a natural
representationtheoretic justification for the concept of flags as introduced
by Razborov in his flag algebra calculus. Furthermore, this connection exposes
a family of nonnegative polynomials that cannot be certified with any fixed
set of flags, answering a question of Razborov in the context of our finite
setting.

A famous result of Lieb establishes that the map $(A,B) \mapsto
\text{tr}\left[K^* A^{1t} K B^t\right]$ is jointly concave in the pair $(A,B)$
of positive definite matrices, where $K$ is a fixed matrix and $t \in [0,1]$.
In this paper we show that Lieb's function admits an explicit semidefinite
programming formulation for any rational $t \in [0,1]$. Our construction makes
use of a semidefinite formulation of weighted matrix geometric means. We
provide an implementation of our constructions in Matlab.

A central question in optimization is to maximize (or minimize) a linear
function over a given polytope P. To solve such a problem in practice one needs
a concise description of the polytope P. In this paper we are interested in
representations of P using the positive semidefinite cone: a positive
semidefinite lift (psd lift) of a polytope P is a representation of P as the
projection of an affine slice of the positive semidefinite cone
$\mathbf{S}^d_+$. Such a representation allows linear optimization problems
over P to be written as semidefinite programs of size d. Such representations
can be beneficial in practice when d is much smaller than the number of facets
of the polytope P. In this paper we are concerned with socalled equivariant
psd lifts (also known as symmetric psd lifts) which respect the symmetries of
the polytope P. We present a representationtheoretic framework to study
equivariant psd lifts of a certain class of symmetric polytopes known as
orbitopes. Our main result is a structure theorem where we show that any
equivariant psd lift of size d of an orbitope is of sumofsquares type where
the functions in the sumofsquares decomposition come from an invariant
subspace of dimension smaller than d^3. We use this framework to study two
wellknown families of polytopes, namely the parity polytope and the cut
polytope, and we prove exponential lower bounds for equivariant psd lifts of
these polytopes.

Let G be a finite abelian group. This paper is concerned with nonnegative
functions on G that are sparse with respect to the Fourier basis. We establish
combinatorial conditions on subsets S and T of Fourier basis elements under
which nonnegative functions with Fourier support S are sums of squares of
functions with Fourier support T. Our combinatorial condition involves
constructing a chordal cover of a graph related to G and S (the Cayley graph
Cay($\hat{G}$,S)) with maximal cliques related to T. Our result relies on two
main ingredients: the decomposition of sparse positive semidefinite matrices
with a chordal sparsity pattern, as well as a simple but key observation
exploiting the structure of the Fourier basis elements of G.
We apply our general result to two examples. First, in the case where $G =
\mathbb{Z}_2^n$, by constructing a particular chordal cover of the halfcube
graph, we prove that any nonnegative quadratic form in n binary variables is a
sum of squares of functions of degree at most $\lceil n/2 \rceil$, establishing
a conjecture of Laurent. Second, we consider nonnegative functions of degree d
on $\mathbb{Z}_N$ (when d divides N). By constructing a particular chordal
cover of the d'th power of the Ncycle, we prove that any such function is a
sum of squares of functions with at most $3d\log(N/d)$ nonzero Fourier
coefficients. Dually this shows that a certain cyclic polytope in
$\mathbb{R}^{2d}$ with N vertices can be expressed as a projection of a section
of the cone of psd matrices of size $3d\log(N/d)$. Putting $N=d^2$ gives a
family of polytopes $P_d \subset \mathbb{R}^{2d}$ with LP extension complexity
$\text{xc}_{LP}(P_d) = \Omega(d^2)$ and SDP extension complexity
$\text{xc}_{PSD}(P_d) = O(d\log(d))$. To the best of our knowledge, this is the
first explicit family of polytopes in increasing dimensions where
$\text{xc}_{PSD}(P_d) = o(\text{xc}_{LP}(P_d))$.

We consider the problem of jointly estimating the attitude and spinrate of a
spinning spacecraft. Psiaki (J. Astronautical Sci., 57(12):7392, 2009) has
formulated a family of optimization problems that generalize the classical
leastsquares attitude estimation problem, known as Wahba's problem, to the
case of a spinning spacecraft. If the rotation axis is fixed and known, but the
spinrate is unknown (such as for nutationdamped spinstabilized spacecraft)
we show that Psiaki's problem can be reformulated exactly as a type of
tractable convex optimization problem called a semidefinite optimization
problem. This reformulation allows us to globally solve the problem using
standard numerical routines for semidefinite optimization. It also provides a
natural semidefinite relaxationbased approach to more complicated variations
on the problem.

Given a polytope P in $\mathbb{R}^n$, we say that P has a positive
semidefinite lift (psd lift) of size d if one can express P as the linear
projection of an affine slice of the positive semidefinite cone
$\mathbf{S}^d_+$. If a polytope P has symmetry, we can consider equivariant psd
lifts, i.e. those psd lifts that respect the symmetry of P. One of the simplest
families of polytopes with interesting symmetries are regular polygons in the
plane, which have played an important role in the study of linear programming
lifts (or extended formulations). In this paper we study equivariant psd lifts
of regular polygons. We first show that the standard Lasserre/sumofsquares
hierarchy for the regular Ngon requires exactly ceil(N/4) iterations and thus
yields an equivariant psd lift of size linear in N. In contrast we show that
one can construct an equivariant psd lift of the regular 2^ngon of size 2n1,
which is exponentially smaller than the psd lift of the sumofsquares
hierarchy. Our construction relies on finding a sparse sumofsquares
certificate for the facetdefining inequalities of the regular 2^ngon, i.e.,
one that only uses a small (logarithmic) number of monomials. Since any
equivariant LP lift of the regular 2^ngon must have size 2^n, this gives the
first example of a polytope with an exponential gap between sizes of
equivariant LP lifts and equivariant psd lifts. Finally we prove that our
construction is essentially optimal by showing that any equivariant psd lift of
the regular Ngon must have size at least logarithmic in N.

We give explicit polynomialsized (in $n$ and $k$) semidefinite
representations of the hyperbolicity cones associated with the elementary
symmetric polynomials of degree $k$ in $n$ variables. These convex cones form a
family of nonpolyhedral outer approximations of the nonnegative orthant that
preserve lowdimensional faces while successively discarding highdimensional
faces. More generally we construct explicit semidefinite representations
(polynomialsized in $k,m$, and $n$) of the hyperbolicity cones associated with
$k$th directional derivatives of polynomials of the form $p(x) =
\det(\sum_{i=1}^{n}A_i x_i)$ where the $A_i$ are $m\times m$ symmetric
matrices. These convex cones form an analogous family of outer approximations
to any spectrahedral cone. Our representations allow us to use semidefinite
programming to solve the linear cone programs associated with these convex
cones as well as their (less well understood) dual cones.

We study the convex hull of $SO(n)$, thought of as the set of $n\times n$
orthogonal matrices with unit determinant, from the point of view of
semidefinite programming. We show that the convex hull of $SO(n)$ is doubly
spectrahedral, i.e. both it and its polar have a description as the
intersection of a cone of positive semidefinite matrices with an affine
subspace. Our spectrahedral representations are explicit, and are of minimum
size, in the sense that there are no smaller spectrahedral representations of
these convex bodies.

In this paper we establish links between, and new results for, three problems
that are not usually considered together. The first is a matrix decomposition
problem that arises in areas such as statistical modeling and signal
processing: given a matrix $X$ formed as the sum of an unknown diagonal matrix
and an unknown low rank positive semidefinite matrix, decompose $X$ into these
constituents. The second problem we consider is to determine the facial
structure of the set of correlation matrices, a convex set also known as the
elliptope. This convex body, and particularly its facial structure, plays a
role in applications from combinatorial optimization to mathematical finance.
The third problem is a basic geometric question: given points
$v_1,v_2,...,v_n\in \R^k$ (where $n > k$) determine whether there is a centered
ellipsoid passing \emph{exactly} through all of the points.
We show that in a precise sense these three problems are equivalent.
Furthermore we establish a simple sufficient condition on a subspace $U$ that
ensures any positive semidefinite matrix $L$ with column space $U$ can be
recovered from $D+L$ for any diagonal matrix $D$ using a convex
optimizationbased heuristic known as minimum trace factor analysis. This
result leads to a new understanding of the structure of rankdeficient
correlation matrices and a simple condition on a set of points that ensures
there is a centered ellipsoid passing through them.