  Set partitioning is a key component of many algorithms in machine learning,
signal processing, and communications. In general, the problem of finding a
partition that minimizes a given impurity (loss function) is NP-hard. As such,
there exists a wealth of literature on approximate algorithms and theoretical
analyses of the partitioning problem under different settings. In this paper,
we formulate and solve a variant of the partition problem called the minimum
impurity partition under constraint (MIPUC). MIPUC finds an optimal partition
that minimizes a given loss function under a given concave constraint. MIPUC
generalizes the recently proposed deterministic information bottleneck problem
which finds an optimal partition that maximizes the mutual information between
the input and partition output while minimizing the partition output entropy.
Our proposed algorithm is developed based on a novel optimality condition,
which allows us to find a locally optimal solution efficiently. Moreover, we
show that the optimal partition produces a hard partition that is equivalent to
the cuts by hyperplanes in the probability space of the posterior probability
that finally yields a polynomial time complexity algorithm to find the globally
optimal partition. Both theoretical and numerical results are provided to
validate the proposed algorithm.
