We show how random projections can be used to solve large-scale dense linear programs approximately. This is a new application of techniques which are now fairly well known in probabilistic algorithms, but have never yet been systematically applied to the fundamental class of Linear Programming. We develop the necessary theoretical framework, and show that this idea works in practice by showcasing its effect on the quantile regression problem, where the state-of-the-art CPLEX solver fails on large or poorly scaled datasets.
Article
View Fast approximate solution of large dense linear programs