Random Projections for Linear Programming

Ky Vu (), Pierre-Louis Poirion () and Leo Liberti ()
Additional contact information
Ky Vu: Institute of Theoretical Computer Science and Communications (ITCSC), Chinese University of Hong Kong, Hong Kong, China
Pierre-Louis Poirion: Huawei Research Center, Paris, France
Leo Liberti: National Center for Scientific Research (CNRS) LIX, Ecole Polytechnique, 91128 Palaiseau, France

Mathematics of Operations Research, 2018, vol. 43, issue 4, 1051-1071

Abstract: Random projections are random linear maps, sampled from appropriate distributions, which approximately 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 matrices with surprisingly few rows which 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 approximately solve linear programs. 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.

Keywords: Johnson-Lindenstrauss lemma; concentration of measure; dimension reduction (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1287/moor.2017.0894 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:43:y:2018:i:4:p:1051-1071

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().