Random Projections for Linear Programming
Random Projections for Linear Programming
复制标题
线性规划的随机投影
DOI：
--
复制
发表时间：
2017
影响因子：
1.7
通讯作者：
Leo Liberti
中科院分区：
文献类型：
--
作者：
K. Vu;Pierre;Leo Liberti
随机投影是随机线性图，从适当的分布中取样，该分布将近似保留某些几何不变，因此随着空间尺寸的增长，近似值会改善。众所周知的约翰逊 - 林斯特劳斯引理说，有很多行的随机矩阵几乎可以在一组点之间保留成对的欧几里得距离。这通常用于基于欧几里得距离加快算法。我们证明这些矩阵还保留了其他数量，例如与锥体的距离。我们利用此结果将概率算法设计为求解线性程序。我们表明，该算法可以大致求解非常大的随机生成的LP实例。我们还展示了其应用于错误校正编码问题。
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.