# Random projection of Linear and Semidefinite problem with linear inequalities

arXiv: https://arxiv.org/abs/2007.00242 · HTML: https://mlsanity.com/paper/2007.00242/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jul 2020.

## Built on by (most cited first, 4 of 4)

- [Generalization Bound and Learning Methods for Data-Driven Projections in Linear Programming](https://mlsanity.com/paper/2309.00203/) (2023)
- [Provably data-driven projection method for quadratic programming](https://mlsanity.com/paper/2509.04524/) (2025)
- [Learning Decision-Sufficient Representations for Linear Optimization](https://mlsanity.com/paper/2603.18551/) (2026)
- [Data-driven Projection Generation for Efficiently Solving Heterogeneous Quadratic Programming Problems](https://mlsanity.com/paper/2510.26061/) (2025)

## Abstract (arXiv)

The Johnson-Lindenstrauss Lemma states that there exist linear maps that project a set of points of a vector space into a space of much lower dimension such that the Euclidean distance between these points is approximately preserved. This lemma has been previously used to prove that we can randomly aggregate, using a random matrix whose entries are drawn from a zero-mean sub-Gaussian distribution, the equality constraints of an Linear Program (LP) while preserving approximately the value of the problem. In this paper we extend these results to the inequality case by introducing a random matrix with non-negative entries that allows to randomly aggregate inequality constraints of an LP while preserving approximately the value of the problem. By duality, the approach we propose allows to reduce both the number of constraints and the dimension of the problem while obtaining some theoretical guarantees on the optimal value. We will also show an extension of our results to certain semidefinite programming instances.