On random embeddings and their application to optimisation

2022/06/07 by Zhen Shao, Shao, Zhen · 3 citations
Computer Science · #Advanced Multi-Objective Optimization Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Metaheuristic Optimization Algorithms Research #Numerical Analysis (math.NA) #Optimization and Control (math.OC)

paper · pdf · doi:10.48550/arxiv.2206.03371

openalex publication_date 2022/06/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Random embeddings project high-dimensional spaces to low-dimensional ones; they are careful constructions which allow the approximate preservation of key properties, such as the pair-wise distances between points. Often in the field of optimisation, one needs to explore high-dimensional spaces representing the problem data or its parameters and thus the computational cost of solving an optimisation problem is connected to the size of the data/variables. This thesis studies the theoretical properties of norm-preserving random embeddings, and their application to several classes of optimisation problems.

Cited by

• A Noise-Aware Scalable Subspace Classical Optimizer for the Quantum Approximate Optimization Algorithm
• CLARSTA: A random subspace trust-region algorithm for convex-constrained derivative-free optimization
• A variable dimension sketching strategy for nonlinear least-squares

Related

• On the choice of the low-dimensional domain for global optimization via random embeddings
• Random Embeddings with Optimal Accuracy
• On Probabilistic Embeddings in Optimal Dimension Reduction
• A dimensionality reduction technique for unconstrained global\n optimization of functions with low effective dimensionality
• Bayesian Optimization in a Billion Dimensions via Random Embeddings