Name
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. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.endm.2016.10.014 | Electronic Notes in Discrete Mathematics |
Keywords | Field | DocType |
Johnson-Lindenstrauss lemma,random projection | Random projection,Row,Discrete mathematics,Combinatorics,Finite set,Convex set,Invariant (mathematics),Euclidean geometry,Logarithm,Mathematics,Johnson–Lindenstrauss lemma | Journal |
Volume | ISSN | Citations |
55 | 1571-0653 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Leo Liberti | 1 | 1280 | 105.20 |
| Pierre-Louis Poirion | 2 | 24 | 7.43 |
| Ky Khac Vu | 3 | 8 | 2.20 |