Abstract
Near isometric orthogonal embeddings to lower dimensions are a fundamentaltool in data science and machine learning. In this paper, we present theconstruction of such embeddings that minimizes the maximum distortion for agiven set of points. We formulate the problem as a non convex constrainedoptimization problem. We first construct a primal relaxation and then use thetheory of Lagrange duality to create dual relaxation. We also suggest apolynomial time algorithm based on the theory of convex optimization to solvethe dual relaxation provably. We provide a theoretical upper bound on theapproximation guarantees for our algorithm, which depends only on the spectralproperties of the dataset. We experimentally demonstrate the superiority of ouralgorithm compared to baselines in terms of the scalability and the ability toachieve lower distortion.