Metraipolis › archive › dc_3300a8d0a6ef

The Rank-Collapse Principle for Quadratic Optimization — arXiv:2608.07828

Source: arXiv (en)
Original: https://arxiv.org/abs/2608.07828
License (as archived): CC0-1.0
Archived: 2026-10-19T09:05:21.422Z
SHA-256 of the archived text: bf39077f61c31757fafa5d11e02c9e2411b9182fce6fd6e3424d537ccf101b0c
Stable URL of this page: https://metraipolis.com/documento/dc_3300a8d0a6ef

How to cite

The Rank-Collapse Principle for Quadratic Optimization — arXiv:2608.07828 — arXiv (en), https://arxiv.org/abs/2608.07828 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_3300a8d0a6ef (Metraipolis archive dc_3300a8d0a6ef, sha256 bf39077f61c31757fafa5d11e02c9e2411b9182fce6fd6e3424d537ccf101b0c)

BibTeX

@misc{dc3300a8d0a6ef,
  title = {The Rank-Collapse Principle for Quadratic Optimization — arXiv:2608.07828},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.07828},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_3300a8d0a6ef; sha256 bf39077f61c31757fafa5d11e02c9e2411b9182fce6fd6e3424d537ccf101b0c},
  year = {2026}
}

Archived text

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

Quadratic optimization becomes hard as soon as either the matrix in the quadratic form has an unfavorable curvature or the feasible set is discrete, combinatorial, or otherwise nonconvex. A complementary phenomenon is also well known in the signal-processing and optimization communities: when the matrix in the quadratic form has small rank, some hard-looking quadratic programs admit exact polynomial-time algorithms for fixed rank. We study the common positive-semidefinite geometry behind this phenomenon. If $Q=BB^\top$ is positive semidefinite, the objective depends on $x$ only through the rank-space shadow $y=B^\top x$. Every optimal shadow $y^*$ uniquely maximizes the linear functional defined by its own direction and satisfies a quantitative quadratic margin. Thus nonlinear optimality collapses to a low-dimensional, self-generated linear exposure direction. We call this the rank-collapse principle. The principle alone does not imply a finite candidate set: efficient exact optimization additionally depends on the projected or active geometry of the feasible family. We organize this distinction through projected-shadow scattering and active-structure collapse, relate it explicitly to established zonotope, convex-combinatorial, edge-skeleton, projected-normal-fan, and fixed-rank sparse-PCA methods, and derive tie-safe consequences for binary and finite-phase vectors, cardinality constraints, matroid bases, and sparse PCA. We also give directional-stability and approximately low-rank certificates, together with reproducible experiments. The paper's contribution is a unified, careful framework and a set of quantitative consequences, rather than a claim to originate the known fixed-rank tractability results that motivate it.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-11 in math.OC).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2608.07828 — 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-19T09:03:32.041Z dalla pagina https://arxiv.org/catchup/math.OC/2026-08-11?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).