no. 16 · Tuesday 17 November 2026
Ensemble Bounds for Pairwise Dissimilar Decomposition of Deterministic Datasets
Abstract
In this paper, we study reduced similarity decompositions of \emph{deterministic} datasets using redundancy graphs and obtain \emph{ensemble} bounds for the minimum size of such constrained decomposition. We consider batch decompositions that reduce similarity \emph{across} batches and use the Lovász local lemma to obtain bounds for the minimum size of a decomposition with a given pairwise dissimilarity. We then consider unique batch decomposition with a given relaxation parameter and obtain upper and lower ensemble bounds for the minimum size. Throughout, we use Binomial random graphs to obtain the desired ensemble bounds, by conditioning on the number of similar \emph{pairs} of data points.
- comments
- Accepted for publication in Springer Proceedings in Mathematics and Statistics, QEDS conference, Ranchi, India
- fields
- Information Theory