Answers are grounded in this paper and cite their sources.
Demonstrates improved projection efficiency for matrix optimization, suggesting enhanced scalability in high dimensions.
This paper develops an efficient algorithm for computing the Euclidean projection onto the top-k-sum constraint, a key operation in financial risk management and matrix optimization problems. Existing projection methods rely on sorting and therefore incur an initial O(nlogn) complexity, which limits their scalability in high-dimensional settings. To address this difficulty, we revisit the Karush-Kuhn-Tucker (KKT) conditions of the projection problem and introduce relaxed conditions that remain sufficient for characterizing the solution. These conditions lead to a simple geometric interpretation: finding the solutions is equivalent to locating the intersection of two monotone piecewise linear functions. Building on this insight, we propose an iterative and highly efficient algorithm that searches directly for the intersection point and completely avoids all sorting procedures. We prove that the algorithm converges globally and reaches the exact solution in a finite number of iterations. Extensive numerical experiments further demonstrate that the proposed algorithm substantially outperforms existing algorithms and exhibits empirical O(n) complexity across a broad range of problem instances. A Julia implementation of the algorithm is available in our public GitHub repository (https://github.com/PanT12/top-k-sum).
No takes yet. Share an insight, caveat, or question.
Pan et al. (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: