PhD Seminar • Algorithms and Complexity — The Paulsen Problem and Spectral Analysis of Scaling Problems

Friday, September 25, 2020 10:00 am - 10:00 am EDT (GMT -04:00)

Please note: This PhD seminar will be given online.

Akshay Ramachandran, PhD candidate
David R. Cheriton School of Computer Science

Supervisor: Professor Lap Chi Lau

The Paulsen problem is a basic problem in operator theory: given $n$ vectors $u_{1}, …, u_{n} \in \R^{d}$ that $\epsilon$-nearly satisfy two balanced marginal conditions, what are the nearest set of vectors $v_{1}, …, v_{n}$ that exactly satisfy those two balance conditions. The main conjecture was whether the Euclidean distance between $(U,V)$ can be made independent on $n$, i.e. only a function of $d$ and $\epsilon$. 

The solution to this conjecture came via the type of problems considered in this reading group. The gradient flow of a natural error measure applied to $U$ ends up at the solution of a related scaling problem on $U$. By this and a few other magical properties of the gradient flow (cf Kempf-Ness function), we are able to give a bound of $nd \epsilon$. The final step uses smoothed-analysis to first add some noise and then give a better convergence analysis. 

The analysis of gradient flow naturally falls into our setting of geodesic convex optimization, and we hope to motivate the relation between Paulsen type problems and scaling problems.


To join this PhD seminar on Zoom, please go to https://uva-live.zoom.us/j/890243122.