MATRIX SKETCHING AND LINEAR PROGRAMMING

Abstract

Random projection has become a standard tool for dimensionality reduction, yet extensive research is still being conducted on its efficiency for large LPs. This thesis contains: (i) surveying matrix–sketching and decomposition techniques used in machine learning and optimisation, (ii) extending theoretical guarantees for projected linear programming problems, and (iii) validating those guarantees through extensive experiments. After reviewing subspace embeddings and the Johnson–Lindenstrauss theorem, we prove that if the original linear problem problem is unbounded, then the projected one is unbounded as well. A counterexample shows that the converse is not necessarily true. We conducted numerical experiments on synthetically generated feasible and infeasible instances to evaluate the efficiency of the random projection method. In general, our study clarifies when matrix sketching accelerates large-scale linear programming problems and when it induces hidden costs, providing practical guidelines for choosing an optimal dimension and sparsity for a random projector.