0
$\begingroup$

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?

$\endgroup$
2
  • 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$
    – mathreadler
    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$
    – mathreadler
    Jul 22, 2015 at 9:36

0

Reset to default

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.