##### Personal tools
You are here: Home 2019 On Radial Isotropic Position: Theory, Algorithms, and Applications
« September 2020 »
September
SuMoTuWeThFrSa
12345
6789101112
13141516171819
20212223242526
27282930

# On Radial Isotropic Position: Theory, Algorithms, and Applications

### Abstract:

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