Personal tools
You are here: Home CG seminar 2019 On Radial Isotropic Position: Theory, Algorithms, and Applications
« September 2020 »
Log in

Forgot your password?

On Radial Isotropic Position: Theory, Algorithms, and Applications

Wednesday, January 9th, 2019, 16:10

Schreiber 309


On Radial Isotropic Position: Theory, Algorithms, and Applications

Shiri Artstein-Avidan  and Haim Kaplan, TAU


We review the theory of, and develop algorithms for transforming a finite point set in $\R^d$ into a set in \emph{radial isotropic position} by a nonsingular linear transformation followed by rescaling each image point to the unit sphere. This problem arises in several applications, such as obtaining a linear lower bound on the unbounded error probabilistic communication complexity, robust subspace recovery in the presence of outliers in machine learning, and a recent application of Kane et al. to point location in arrangements of hyperplanes in high dimensions. We study the algorithmic issues in finding the transformation that puts a dataset in radial isotropic position, and design efficient algorithms that are based on gradient descent, applied to a particular convex function whose minimum defines the transformation (which, when it exists, is unique up to rotation). We show that computing the gradient amounts to computing the Singular Value Decomposition (SVD) of a certain matrix associated with the input set, so this technique is simple to implement. Our main contribution is an analysis of the convergence rates of several variants of the gradient descent technique, when applied to our function. Interestingly, the SVD also plays a crucial role in the analysis.


Joint work with Micha Sharir

Document Actions