Radial Isotropic Position via an Implicit Newton's Method

Placing a dataset A = aii∈[n]⊂ ℝdin radial isotropic position, i.e., finding an invertible R ∈ ℝd×dsuch that the unit vectors ${\left\{ {\left( {{\text{R}}{{\text{a}}_i}} \right)\left\| {{\text{R}}{{\text{a}}_i}} \right\|_2^{ - 1}} \right\}_{i \in [n]}}$ are in isotropic position, is a powerful tool with applications in functional analysis, communication complexity, coding theory, and the design of learning algorithms. When the transformed dataset has a second moment matrix within a exp(±ϵ) factor of a multiple of Id, we call R an ϵ-approximate Forster transform.We give a faster algorithm for computing approximate Forster transforms, based on optimizing an objective defined by Barthe [1]. When the transform has a polynomially-bounded aspect ratio, our algorithm uses $O\left( {n{d^{\omega - 1}}{{\left( {\frac{n}{\varepsilon }} \right)}^{o(1)}}} \right)$ time to output an ϵ-approximate Forster transform with high probability, when one exists. This is almost the natural limit of this approach, as even evaluating Barthe’s objective takes O(ndω−1) time. Previously, the state-of-the-art runtime in this regime was based on cutting-plane methods, and scaled at least as ≈ n3+n2dω−1. We also provide explicit estimates on the aspect ratio in the smoothed analysis setting, and show that our algorithm similarly improves upon those in the literature.To obtain our results, we develop a subroutine of potential broader interest: a reduction from almost-linear time sparsification of graph Laplacians to the ability to support almost-linear time matrix-vector products. We combine this tool with new stability bounds on Barthe’s objective to implicitly implement a box-constrained Newton’s method [2], [3].