  Linear programming (LP) is an extremely useful tool and has been successfully
applied to solve various problems in a wide range of areas, including
operations research, engineering, economics, or even more abstract mathematical
areas such as combinatorics. It is also used in many machine learning
applications, such as $\ell_1$-regularized SVMs, basis pursuit, nonnegative
matrix factorization, etc. Interior Point Methods (IPMs) are one of the most
popular methods to solve LPs both in theory and in practice. Their underlying
complexity is dominated by the cost of solving a system of linear equations at
each iteration. In this paper, we consider \emph{infeasible} IPMs for the
special case where the number of variables is much larger than the number of
constraints. Using tools from Randomized Linear Algebra, we present a
preconditioning technique that, when combined with the Conjugate Gradient
iterative solver, provably guarantees that infeasible IPM algorithms (suitably
modified to account for the error incurred by the approximate solver), converge
to a feasible, approximately optimal solution, without increasing their
iteration complexity. Our empirical evaluations verify our theoretical results
on both real-world and synthetic data.

Data Structures and Algorithms;Optimization and Control