I need to select $k$ elements from a pool containing a much larger number $N$ of elements. The selection must be done in a way that a function $h(\{z_{i_1},\ldots,z_{i_k}\})$ is maximized or approximately maximized. Evaluating all the possible subsets is infeasible due to combinatorial explosion.

What can be an efficient method to get such a subset? Do you have any pointers to literature?

Specifically: I need to select a subset of $(x,y)$ coordinates from a set that is at least 20 times larger. The subset I'm extracting should have a higher entropy in comparison to other possible selections.

There is a relationship between the samples in the function $h$. In other words, if $h$ returns a high value, if just one element in the subset is replaced, it is likely that the $h$ value won't change too much. How to exploit this property?

  • 1
    $\begingroup$ This is a convex regularization problem. The constraint $|z|_0 \leq k$ can be regularized by $|z|_1$ and good L1 norm solvers / regularizers exist. Then entropy is also concave so maximizing it is minimizing a convex function. $\endgroup$ Jul 22, 2015 at 9:34
  • 1
    $\begingroup$ I would recommend checking out the convex toolkit "cvx". It sounds like your problem could be solved using that software. $\endgroup$ Jul 22, 2015 at 9:36


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.