Random projections for linear programming
From MaRDI portal
Publication:5219688
Abstract: Random projections are random linear maps, sampled from appropriate distributions, that approx- imately preserve certain geometrical invariants so that the approximation improves as the dimension of the space grows. The well-known Johnson-Lindenstrauss lemma states that there are random ma- trices with surprisingly few rows that approximately preserve pairwise Euclidean distances among a set of points. This is commonly used to speed up algorithms based on Euclidean distances. We prove that these matrices also preserve other quantities, such as the distance to a cone. We exploit this result to devise a probabilistic algorithm to solve linear programs approximately. We show that this algorithm can approximately solve very large randomly generated LP instances. We also showcase its application to an error correction coding problem.
Recommendations
Cites work
- A sparse Johnson-Lindenstrauss transform
- An elementary proof of a theorem of Johnson and Lindenstrauss
- Computing in operations research using Julia
- Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
- Decoding by Linear Programming
- Extensions of Lipschitz mappings into a Hilbert space
- scientific article; zbMATH DE number 53984 (Why is no real title available?)
- Interior-point methods
- Julia: a fresh approach to numerical computing
- Nearest-neighbor-preserving embeddings
- On Constraint Sampling in the Linear Programming Approach to Approximate Dynamic Programming
- On the complexity of a pivot step of the revised simplex algorithm
- On variants of the Johnson–Lindenstrauss lemma
- Quantile regression for large-scale applications
- Quantile regression.
- Sparse Approximate Solutions to Linear Systems
- Sparser Johnson-Lindenstrauss transforms
- The Johnson-Lindenstrauss Transform: An Empirical Study
- The simplex method. A probabilistic analysis
- Understanding and using linear programming
Cited in
(24)- Random projections for the nonnegative least-squares problem
- Gaussian random projections for Euclidean membership problems
- Random projections for conic programs
- Side-constrained minimum sum-of-squares clustering: mathematical programming and random projections
- Distance geometry and data science
- Random projections for quadratic programs
- Normal projection: deterministic and probabilistic algorithms
- Random projections for quadratic programs over a Euclidean ball
- A note on linear function approximation using random projections
- Bound-constrained global optimization of functions with low effective dimensionality using multiple random embeddings
- Random projections of linear and semidefinite problems with linear inequalities
- Random linear programs with many variables and few constraints
- Linear programming — Randomization and abstract frameworks
- Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds
- Convexification with bounded gap for randomly projected quadratic optimization
- Solving LP using random projections
- scientific article; zbMATH DE number 6276198 (Why is no real title available?)
- Stable probability of reduced matrix obtained by Gaussian random projection
- Global optimization using random embeddings
- Simple and fast algorithm for binary integer and online linear programming
- Random Projection and Recovery for High Dimensional Optimization with Arbitrary Outliers
- Random projections for linear programming: an improved retrieval phase
- Random projections for semidefinite programming
- Sparse sub-Gaussian random projections for semidefinite programming relaxations
This page was built for publication: Random projections for linear programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5219688)
