Let $V$ be a set of vectors over $\mathbb{R}^l$, $l\ge 1$, $\pi_i(V)$ be the permutation of vectors in $V$ such that they are ordered by their $i$th component (descending) in order for $\pi_i(V)(\mathbf{v})$ to be the rank of $\textbf{v}$ by component $I$: then define $$ \operatorname{top}(V, k) := \sum_{i=0}^l \sum_{\substack{\mathbf{v} \\ \pi_i(V)(\textbf{v}) < k}} \mathbf{v}_i $$ What we desire is an algorithm (ideally involving polynomial time/space complexity in $|V|$) such that for a given $n$, $k \ll |V|$, we can find the subset of vectors $V^* \subset V, |V^*| = n$ that maximizes $\operatorname{top}(V^*, k)$.
Intuitively we can think of our set as a matrix (though it's column order invariant), and we can think of the $\operatorname{top}$ function as "sparsifying" any sub-matrix, by setting all but the top $k$ values in each row of that sub-matrix to 0. Then our goal is to select the $n$ columns that maximize the sum total of values in the sparsified sub-matrix.
I've played around a little bit with reductions to NP-Hard problems, but don't see anything obvious. You can easily compute the effect of "swapping" one vector for another in our selected subset, but it's not obvious to me that the greedy algorithm this implies would produce an optimal solution. Any help is appreciated.
