Paperlane

no. 16 · Tuesday 17 November 2026

Ensemble Bounds for Pairwise Dissimilar Decomposition of Deterministic Datasets

Ghurumuruhan Ganesan

math.IT · via stat.ML

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
pdf ↗ page arXiv:2611.18625 ↗