The Paulsen Problem, Continuous Operator Scaling, and Smoothed Analysis

The Paulsen problem is a basic open problem in operator theory: Given vectors $u_1,\dots ,u_n\in {\mathbb{R}}^d$ that are $ϵ$-nearly satisfying the Parseval’s condition and the equal norm condition, is it close to a set of vectors $v_1,\dots ,v_n\in {\mathbb{R}}^d$ that exactly satisfy the Parseval’s condition and the equal norm condition? Given $u_1,\dots ,u_n$, the squared distance (to the set of exact solutions) is defined as $\inf_{v} \sum_{i=1}^n | u_i - v_i |_2^2$ where the infimum is over the set of exact solutions. Previous results show that the squared distance of any $ϵ$-nearly solution is at most $O(\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}(d,n,ϵ))$ and there are $ϵ$-nearly solutions with squared distance at least $\mathrm{\Omega }(dϵ)$. The fundamental open question is whether the squared distance can be independent of the number of vectors $n$. We answer this question affirmatively by proving that the squared distance of any $ϵ$-nearly solution is $O(d^{13\mathrm{/}2}ϵ)$. Our approach is based on a continuous version of the operator scaling algorithm and consists of two parts. First, we define a dynamical system based on operator scaling and use it to prove that the squared distance of any $ϵ$-nearly solution is $O(d^2 n \epsilon)$. Then, we show that by randomly perturbing the input vectors, the dynamical system will converge faster and the squared distance of an $ϵ$-nearly solution is $O(d^{5\mathrm{/}2}ϵ)$ when $n$ is large enough and $ϵ$ is small enough. To analyze the convergence of the dynamical system, we develop some new techniques in lower bounding the operator capacity, a concept introduced by Gurvits to analyze the operator scaling algorithm.