Groupe d’études et de recherche en analyse des décisions

G-2015-54

A lower bound on the sum of the largest components of a nonnegative vector

We study the function returning the sum of the k components of largest magnitude of a vector. We show that if a nonnegative vector x is such that its Euclidean norm is greater than or equal to one, and if the integer k is an upper bound on the Manhattan norm of x, then there exists k components of x whose sum is greater than or equal to one.

, 7 pages