Improved linear embeddings via Lagrange duality

DOI10.1007/S10994-018-5729-XMaRDI QIDQ669310zbMATH OpenOpenAlexFDO

Authors Juan-Miguel Gracia

Publication date 15 March 2019

Published in Machine Learning (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.11527

zbMATH Keywords

dimensionality reductionconvex relaxationconvex and non-convex optimizationnear isometric embeddings

Mathematics Subject Classification ID

Factor analysis and principal components; correspondence analysis (62H25) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Optimality conditions and duality in mathematical programming (90C46) Nonconvex programming, global optimization (90C26)

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 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.

Recommendations

• A nonlinear approach to dimension reduction
• Finding graph embeddings by incremental low-rank semidefinite programming
• The Johnson-Lindenstrauss Transform: An Empirical Study
• The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction
• Distance preserving embeddings for general \(n\)-dimensional manifolds

Cites work

• scientific article; zbMATH DE number 1775450 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• Approximate clustering via core-sets
• Convex optimization: algorithms and complexity
• Extensions of Lipschitz mappings into a Hilbert space
• NuMax: A Convex Approach for Learning Near-Isometric Linear Embeddings
• Optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with subconstant error
• Problems and results in extremal combinatorics. I.

Describes a project that uses

Uses Software

• MNIST

This page was built for publication: Improved linear embeddings via Lagrange duality

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q669310)