Sum of the largest components

The sum of the

k

largest components of

x \in R^{n}

is the support function of the capped simplex:

\sum_{i = 1}^{k} x_{[i]} = max {x^{T} v : 0 \leq v \leq 1, \sum_{i} v_{i} = k}

.

Table of contents
- Threshold formula for the sum of the largest components Sum of the largest components

Threshold formula for the sum of the largest components ( $f_{k} (x) = min_{t} {k t + \sum_{i} (x_{i} - t)_{+}}$ )

For

1 \leq k \leq n

, linear programming duality gives

f_{k} (x) = min_{t \in R, s \geq 0} {k t + \sum_{i} s_{i} : s_{i} + t \geq x_{i}} = min_{t \in R} {k t + \sum_{i} (x_{i} - t)_{+}},

where

(\cdot)_{+}

is the positive part of a real-valued function. To see equality directly, order the coordinates

x_{[1]} \geq \dots \geq x_{[n]}

and choose

x_{[k + 1]} \leq t \leq x_{[k]}

for

k < n

, or

t \leq x_{[n]}

for

k = n

. The threshold expression then equals the sum of the largest components. Introducing the variables

s_{i}

turns this convex piecewise-linear objective into a linear program.

 Ancestors (6)

 Incoming links (4)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version