The ACO Seminar (2022–2023)

We will consider the problem of optimizing a quadratic function subject to quadratic constraints, in addition to a sparsity constraint that requires that solutions have only a few nonzero entries. Such problems include sparse versions of linear regression and principal components analysis. We'll see that the solutions to these problems are intimately related to the roots of certain polynomials that generalize the determinant, which arose from the study of hyperbolic polynomials. We'll also describe a fast algorithm for such problems, which performs well in practical situations. Connections to semidefinite programming and volume sampling will be mentioned.