The Paulsen problem for nearly equal norm Parseval frames

Let $V=(v_1,\dots,v_n)$ be an $\epsilon$ -nearly equal norm Parseval frame in $\mathbb R^d$ , meaning

(1-\epsilon)I\preceq\sum_{i=1}^n v_i v_i^T\preceq(1+\epsilon)I

and

(1-\epsilon)\frac dn\leq\|v_i\|_2^2\leq(1+\epsilon)\frac dn

for every $i$ . Let $\mathcal F$ be the set of equal norm Parseval frames, and for two sequences $V=(v_1,\dots,v_n)$ and $W=(w_1,\dots,w_n)$ define

\operatorname{dist}^2(V,W)=\sum_{i=1}^n\|v_i-w_i\|^2.

Paulsen problem. For every $\epsilon$ -nearly equal norm Parseval frame $V$ , is

\inf_{W\in\mathcal F}\operatorname{dist}^2(V,W)

bounded by a fixed polynomial in $\epsilon$ and $d$ ?

The problem was a major open question in frame theory, but the supplied context states that Kwok, Lau, Lee and Ramachandran had already proved a polynomial bound, and that the paper gives the improved bound $O(\epsilon d^2)$ . Thus the conjecture is resolved.

The Paulsen problem asks whether approximate Parseval frames can be changed into exactly equal-norm Parseval frames at polynomial squared distance. Kwok, Lau, Lee, and Ramachandran announced an affirmative solution in 2017; Hamilton and Moitra later gave a simpler proof and improved the estimate.

Known results

Hadwin: compactness proves existence of a Paulsen function.
Casazza: the bound is independent of $n$ , with lower bound $f(\varepsilon,n,d)\geq\varepsilon^2d$ .
Kwok, Lau, Lee, and Ramachandran, 2017: $\operatorname{dist}^2\leq O(\varepsilon d^{13/2})$ .
Hamilton and Moitra, 2018: $\operatorname{dist}^2\leq20\varepsilon d^2$ ; the known lower bound is $\Omega(\varepsilon d)$ .

May 2026 probabilistic improvement

A 2026 preprint proves a high-probability bound of order $O(\varepsilon^2d)$ for uniformly random nearly equal-norm frames. This improves the typical-case estimate, not the best general deterministic bound, which remains $20\varepsilon d^2$ ; narrowing the deterministic gap to the $\Omega(\varepsilon d)$ lower bound remains open.

Current status (as of September 2026): The existence question is settled by claimed published proofs, with deterministic bound $O(\varepsilon d^2)$ and a stronger random-case estimate, while the optimal deterministic dependence between $\Omega(\varepsilon d)$ and $O(\varepsilon d^2)$ remains open.

The Paulsen problem for nearly equal norm Parseval frames

Primary source

Progress summary

Solutions 0