Solving LP using random projections

Leo Liberti; Pierre Louis Poirion; Vu Khac Ky

doi:10.1016/j.endm.2016.10.014

Solving LP using random projections

Leo Liberti
, Pierre Louis Poirion
, Vu Khac Ky

Research output: Contribution to journal › Article › peer-review

Abstract

A celebrated result of Johnson and Lindenstrauss asserts that, in high enough dimensional spaces, Euclidean distances defined by a finite set of points are approximately preserved when these points are projected to a certain lower dimensional space. We show that the distance from a point to a convex set is another approximate invariant, and leverage this result to approximately solve linear programs with a logarithmic number of rows.

Original language	English
Pages (from-to)	53-56
Number of pages	4
Journal	Electronic Notes in Discrete Mathematics
Volume	55
DOIs	https://doi.org/10.1016/j.endm.2016.10.014
Publication status	Published - 1 Nov 2016

Keywords

Johnson-Lindenstrauss lemma
random projection

Access to Document

10.1016/j.endm.2016.10.014

Cite this

@article{c78a06be2e8d4b6b9e717c70be2ea36c,

title = "Solving LP using random projections",

abstract = "A celebrated result of Johnson and Lindenstrauss asserts that, in high enough dimensional spaces, Euclidean distances defined by a finite set of points are approximately preserved when these points are projected to a certain lower dimensional space. We show that the distance from a point to a convex set is another approximate invariant, and leverage this result to approximately solve linear programs with a logarithmic number of rows.",

keywords = "Johnson-Lindenstrauss lemma, random projection",

author = "Leo Liberti and Poirion, \{Pierre Louis\} and Ky, \{Vu Khac\}",

note = "Publisher Copyright: {\textcopyright} 2016 Elsevier B.V.",

year = "2016",

month = nov,

day = "1",

doi = "10.1016/j.endm.2016.10.014",

language = "English",

volume = "55",

pages = "53--56",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

}

TY - JOUR

T1 - Solving LP using random projections

AU - Liberti, Leo

AU - Poirion, Pierre Louis

AU - Ky, Vu Khac

PY - 2016/11/1

Y1 - 2016/11/1

N2 - A celebrated result of Johnson and Lindenstrauss asserts that, in high enough dimensional spaces, Euclidean distances defined by a finite set of points are approximately preserved when these points are projected to a certain lower dimensional space. We show that the distance from a point to a convex set is another approximate invariant, and leverage this result to approximately solve linear programs with a logarithmic number of rows.

AB - A celebrated result of Johnson and Lindenstrauss asserts that, in high enough dimensional spaces, Euclidean distances defined by a finite set of points are approximately preserved when these points are projected to a certain lower dimensional space. We show that the distance from a point to a convex set is another approximate invariant, and leverage this result to approximately solve linear programs with a logarithmic number of rows.

KW - Johnson-Lindenstrauss lemma

KW - random projection

U2 - 10.1016/j.endm.2016.10.014

DO - 10.1016/j.endm.2016.10.014

M3 - Article

AN - SCOPUS:84995543451

SN - 1571-0653

VL - 55

SP - 53

EP - 56

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

ER -

Solving LP using random projections

Abstract

Keywords

Access to Document

Fingerprint

Cite this