English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The top-$k$-sum operator computes the sum of the largest $k$ components of agiven vector. The Euclidean projection onto the top-$k$-sum constraint servesas a crucial subroutine in iterative methods to solve composite superquantileoptimization problems. In this paper, we introduce a solver that implements twofinite-termination algorithms to compute this projection. Both algorithms havecomplexity $O(n)$ when applied to a sorted $n$-dimensional input vector, wherethe absorbed constant is independent of $k$. This stands in contrast to theexisting grid-search-inspired method that has $O(k(n-k))$ complexity. Theimprovement is significant when $k$ is linearly dependent on $n$, whichfrequently encountered in practical superquantile optimization applications. Ininstances where the input vector is unsorted, an additional cost is incurred to(partially) sort the vector. To reduce this cost, we further derive a rigorousprocedure that leverages approximate sorting to compute the projection, whichis particularly useful when solving a sequence of similar projection problems.Numerical results show that our methods solve problems of scale $n=10^7$ and$k=10^4$ within $0.05$ seconds, whereas the existing grid-search-based methodand the Gurobi QP solver can take minutes to hours.

On $O(n)$ Algorithms for Projection onto the Top-$k$-sum Constraint