Metraipolis › archive › dc_cd5f83da772b

Random projection with linear equalities and inequalities — arXiv:2610.09324

Source: arXiv (en)
Original: https://arxiv.org/abs/2610.09324
License (as archived): CC0-1.0
Archived: 2026-10-08T12:40:30.515Z
SHA-256 of the archived text: b70997d133bc69cb229e4de425f023b1de903a257f6657e902f9ed5596352994
Stable URL of this page: https://metraipolis.com/documento/dc_cd5f83da772b

How to cite

Random projection with linear equalities and inequalities — arXiv:2610.09324 — arXiv (en), https://arxiv.org/abs/2610.09324 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_cd5f83da772b (Metraipolis archive dc_cd5f83da772b, sha256 b70997d133bc69cb229e4de425f023b1de903a257f6657e902f9ed5596352994)

BibTeX

@misc{dccd5f83da772b,
  title = {Random projection with linear equalities and inequalities — arXiv:2610.09324},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.09324},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_cd5f83da772b; sha256 b70997d133bc69cb229e4de425f023b1de903a257f6657e902f9ed5596352994},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.09324. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.OC, nuovi lavori del giorno).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2610.09324 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T12:16:00.178Z dalla pagina https://arxiv.org/list/math.OC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).