Reproduce “Horospherically convex optimization for fractional subspace packing and its applications” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Hiroshi Hirai
A horospherically convex optimization framework turns fractional subspace packing, a semi-infinite linear program over all subspaces, into Busemann-function minimization on a Euclidean building. The resulting subgradient method gives an additive FPTAS for arbitrary subspaces, fixed-dimension exact algorithms, an alternative solver for fractional linear matroid parity, and approximate and exact procedures for Brascamp–Lieb polytope problems.
Key insights
- The apparently semi-infinite LP has a useful geometric compression: optimal dual solutions live on flags, and flags are naturally organized by the CAT(0) geometry of a Euclidean building.
- Busemann functions serve as the analogue of affine functions on this non-Euclidean domain, enabling first-order optimization despite the absence of ordinary vector-space structure.
- For two-dimensional subspaces, the general geometric method can be combined with half-integrality to recover optimal 2-covers and fractional linear matroid parity solutions.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.