期刊
MATHEMATICS OF OPERATIONS RESEARCH
卷 43, 期 4, 页码 1051-1071出版社
INFORMS
DOI: 10.1287/moor.2017.0894
关键词
Johnson-Lindenstrauss lemma; concentration of measure; dimension reduction
资金
- SO-grid project - ADEME
- EU [316647]
- ANR [ANR-10-BINF-0003]
- Microsoft Research PhD fellowship
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据