Improved linear embeddings via Lagrange duality

Show simple item record Sheth, Kshiteej Garg, Dinesh Dasgupta, Anirban 2019-03-27T06:42:09Z 2019-03-27T06:42:09Z 2019-03
dc.identifier.citation Sheth, Kshiteej; Garg, Dinesh and Dasgupta, Anirban,"Improved linear embeddings via Lagrange duality", Machine Learning, DOI: 10.1007/s10994-018-5729-x, vol. 108, no. 4, pp. 575-594, Mar. 2019. en_US
dc.identifier.issn 0885-6125
dc.identifier.issn 1573-0565
dc.description.abstract Near isometric orthogonal embeddings to lower dimensions are a fundamental tool in data science and machine learning. In this paper, we present the construction of such embeddings that minimizes the maximum distortion for a given set of points. We formulate the problem as a non convex constrained optimization problem. We first construct a primal relaxation and then use the theory of Lagrange duality to create a dual relaxation. We also suggest a polynomial time algorithm based on the theory of convex optimization to solve the dual relaxation provably. We provide a theoretical upper bound on the approximation guarantees for our algorithm, which depends only on the spectral properties of the dataset. We experimentally demonstrate the superiority of our algorithm compared to baselines in terms of the scalability and the ability to achieve lower distortion.
dc.description.statementofresponsibility by Kshiteej Sheth, Dinesh Garg and Anirban Dasgupta
dc.format.extent vol. 108, no. 4, pp. 575-594
dc.language.iso en en_US
dc.publisher Springer en_US
dc.subject Near isometric embeddings en_US
dc.subject Dimensionality reduction en_US
dc.subject Convex and non-convex optimization en_US
dc.subject Convex relaxation en_US
dc.title Improved linear embeddings via Lagrange duality en_US
dc.type Article en_US
dc.relation.journal Machine Learning

Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search Digital Repository


My Account