Title: The Paulsen Problem, Continuous Operator Scaling, and Smoothed Analysis,
Abstract: The Paulsen problem is a basic open problem in operator theory: Given vectors
$u_1, \ldots, u_n \in \mathbb R^d$ that are $\epsilon$-nearly satisfying the
Parseval's condition and the equal norm condition, is it close to a set of
vectors $v_1, \ldots, v_n \in \mathbb R^d$ that exactly satisfy the Parseval's
condition and the equal norm condition? Given $u_1, \ldots, 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 $\epsilon$-nearly
solution is at most $O({\rm{poly}}(d,n,\epsilon))$ and there are
$\epsilon$-nearly solutions with squared distance at least $\Omega(d\epsilon)$.
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 $\epsilon$-nearly solution is $O(d^{13/2} \epsilon)$. 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 $\epsilon$-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
$\epsilon$-nearly solution is $O(d^{5/2} \epsilon)$ when $n$ is large enough
and $\epsilon$ 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.