The Rank-Collapse Principle for Quadratic Optimization

Abstract

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=B{B}^{\top }$ is positive semidefinite, the objective depends on $x$ only through the rank-space shadow $y=B^{\top }x$. Every optimal shadow $y^{\ast }$ 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.

26 pages, 7 figures. Ancillary reproducibility package included