A Convex Optimization Approach to the Paulsen Problem

Abstract

A frame $\{v_1, \dots, v_n\} \subseteq \R^d$, $n \geq d$, is a spanning set of vectors. Like a basis, it allows every vector in the space to be reconstructed from its inner products with frame vectors. A frame is Parseval if this reconstruction works without any rescaling, similar to computing the coefficients for an orthonormal basis. A frame is equal-norm if every vector in the collection has the same length. An equal-norm Parseval frame combines both properties.

The Paulsen Problem is a problem in frame theory that asked, given an $\epsilon$-almost equal-norm Parseval frame, can one find an equal-norm Parseval frame such that the distance between the frames is bounded above by a polynomial in $d$ and $\epsilon$? This was answered affirmatively using two different algorithmic techniques: one using operator scaling, and another that uses convex optimization to find a linear transformation that will place the frame vectors in radial isotropic position (a geometric condition that causes this transformed frame to be an equal-norm Parseval frame). We investigate the latter and its relationships to convex analysis in various ways. We come to understand more clearly the structure of the basis polytope and problems related to it, how the functional analysis underpinning radial isotropic position may be understood with the lens of convex analysis, and analytic information regarding the Paulsen Problem and the radial isotropic position problem. We implement the algorithm as well, and using this analytic information, run experiments to attempt to observe an upper bounding polynomial in $d$ and $\epsilon$.