Convex Optimization & Parsimony of L_p-balls Representation
Presenter
January 28, 2016
Keywords:
- convex optimization; parsimony-inducing norms; computational geometry
MSC:
- 47N10
Abstract
We consider the family of nonnegative homogeneous polynomials of even degree p whose sublevel set G = {x : g(x) ≤ 1} (a unit ball) has same fixed volume and want to find in this family the one that minimizes either the parsimony-inducing ell_1-norm or the ell_2-norm of its vector of coefficients. We first show that in both cases this is a convex optimization problem with a unique optimal solution. In the former case, the unique solution is the polynomial associated with the L_p-ball, thus recovering a parsimony property of its representation via ell_1-minimization. We also show that the solution of the ell_2-norm problem is an appropriate power of the polynomial associated with the Euclidean ball. We also characterize the unique optimal solution of the same problem where one searches for an SOS homogeneous polynomial that minimizes the (parsimony-inducing) nuclear norm of its associated (psd) Gram matrix. Again the Euclidean ball shows up.