  Linear programming (LP) is an extremely useful tool which 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 both feasible and
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
iterative solvers such as Conjugate Gradient or Chebyshev Iteration, provably
guarantees that 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.
