  Convex regression is the problem of fitting a convex function to a data set
consisting of input-output pairs. We present a new approach to this problem
called spectrahedral regression, in which we fit a spectrahedral function to
the data, i.e. a function that is the maximum eigenvalue of an affine matrix
expression of the input. This method represents a significant generalization of
polyhedral (also called max-affine) regression, in which a polyhedral function
(a maximum of a fixed number of affine functions) is fit to the data. We prove
bounds on how well spectrahedral functions can approximate arbitrary convex
functions via statistical risk analysis. We also analyze an alternating
minimization algorithm for the non-convex optimization problem of fitting the
best spectrahedral function to a given data set. We show that this algorithm
converges geometrically with high probability to a small ball around the
optimal parameter given a good initialization. Finally, we demonstrate the
utility of our approach with experiments on synthetic data sets as well as real
data arising in applications such as economics and engineering design.
