Random projection with linear equalities and inequalities
Abstract
Random projection is a preprocessing technique for optimization that reduces the number of linear equality constraints by replacing them with random linear combinations while approximately preserving the optimal value. In this paper, we emphasize the role of suprema of random processes, and in particular generic chaining, in explaining this phenomenon. By combining Lagrangian duality with generic chaining, we obtain shorter proofs and sharper guarantees that apply beyond the typical polyhedral settings based on the Johnson--Lindenstrauss lemma. More importantly, this perspective allows us to extend random projection to problems with linear inequality constraints. Although randomly projected inequality constraints generally define neither a relaxation nor a restriction of the original feasible region, we show that random projection can nevertheless approximately preserve the dual bound. The key is a new construction for randomly projecting dual certificates that preserves dual feasibility and differs from existing constructions motivated by the Johnson--Lindenstrauss lemma.
Related
- Inequalities and equalities of means in Constructive Mathematics
- A Projection Identity for Simplices Sharp Inequalities, Converse Results, and Affine Projections
- Radon Transforms of Projection Functions and Aleksandrov-Fenchel Inequalities
- A Projection Anderson Acceleration Algorithm for Non-quasi-monotone Variational Inequalities with Hölder Continuous Terms
- Sharp projection inequalities for antichains in cone orders
BibTeX
@misc{dey2026random,
title = {{Random projection with linear equalities and inequalities}},
author = {Santanu S. Dey and Jingye Xu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.09324},
eprint = {2610.09324},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.09324},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Random projection with linear equalities and inequalities
AU - Santanu S. Dey
AU - Jingye Xu
PY - 2026
DA - 2026/10/07
PB - arXiv
DO - 10.48550/arxiv.2610.09324
UR - https://arxiv.org/abs/2610.09324
AB - Random projection is a preprocessing technique for optimization that reduces the number of linear equality constraints by replacing them with random linear combinations while approximately preserving the optimal value. In this paper, we emphasize the role of suprema of random processes, and in particular generic chaining, in explaining this phenomenon. By combining Lagrangian duality with generic chaining, we obtain shorter proofs and sharper guarantees that apply beyond the typical polyhedral settings based on the Johnson--Lindenstrauss lemma. More importantly, this perspective allows us to extend random projection to problems with linear inequality constraints. Although randomly projected inequality constraints generally define neither a relaxation nor a restriction of the original feasible region, we show that random projection can nevertheless approximately preserve the dual bound. The key is a new construction for randomly projecting dual certificates that preserves dual feasibility and differs from existing constructions motivated by the Johnson--Lindenstrauss lemma.
ER -