biclustering; network information theory; distributed source coding; CEO problem; log loss distortion; information bottleneck; Boolean functions
en
Abstract:
Diese Arbeit befasst sich mit Problemen der verteilten Quellenkodierung, welche sich von Biclustering Methoden ableiten. Wir definieren dieses Shannon-theoretische verteilte Quellenkodierungsproblem, bei dem die Transinformation zwischen Codewörtern maximiert werden soll. Die mathematischen Eigenschaften der Transinformation machen dieses Problem für Techniken zugänglich, die auf allgemeine Rate-Distortion Probleme nicht anwendbar wären. Wir untersuchen die erreichbare Region und zeigen dabei Zusammenhänge mit etlichen anderen Kodierungsproblemen in der Literatur auf. Zunächst beschränken wir uns auf zwei Quellen und finden Schranken für die erreichbare Region. Dabei stellen wir Zusammenhänge mit Problemen des Hypothesentestens und der Mustererkennung her. Wir ergänzen diese Resultate durch Abschätzungen für die Kardinalität der Hilfsvariablen, wobei wir die üblichen Abschätzungen verbessern, die durch Anwenden der Methode konvexer Überdeckungen erreicht werden. Die verbesserten Abschätzungen wenden im Fall einer doppelt symmetrischen binären Quelle an und stellen fest, dass die inneren und äußeren Schranken nicht übereinstimmen, was eine Vermutung von Westover und O'Sullivan (2008) widerlegt. Wir verallgemeinern das Problem für eine beliebige Zahl an Quellen und zeigen, dass ein CEO-Problem mit logarithmischem Verlust als Verzerrung einen Spezialfall darstellt, welcher zuvor von Courtade und Weissman (2014) untersucht wurde. Dieses CEO-Problem kann erweitert werden, indem man mehrfache Beschreibungen berücksichtigt. Wir verwenden die Theorie submodularer Funktionen und finden eine single-letter Charakterisierung der erreichbaren Region für dieses CEO-Problem mit mehrfachen Beschreibungen unter geeigneten Annahmen bedingter Unabhängigkeit. Die resultierende Region hat einige interessante technische Eigenschaften. Insbesondere ist die benötigte Rate im Allgemeinen niedriger als für eine erfolgreiche typische Dekodierung notwendig. Weiters präsentieren wir den Beweis einer Vermutung von Kumar und Courtade (2013) über die maximale Transinformation von zwei Boolschen Funktionen, die besagt, dass I(f(Xⁿ); g(Yⁿ)) ≤ I(X;Y) für zwei beliebige Boolsche Funktionen gilt, wobei (X,Y) eine doppelt symmetrische binäre Quelle ist. Wir zeigen, dass, abgesehen von Spezialfällen, die Diktator"=Funktionen die einzigen Boolschen Funktionen sind, die Gleichheit erreichen. Der Schlüsselschritt des Beweises ist eine detailierte Analyse des Fourier-Spektrums der Boolschen Funktionen, die es erlaubt, die Vermutung auf eine elementare Ungleichung zurückzuführen.
de
This thesis is concerned with multi-terminal source coding problems motivated by biclustering applications. We introduce the Shannon theoretic multi-clustering problem and investigate its properties, uncovering connections with many other coding problems in the literature. The figure of merit for this information-theoretic problem is mutual information, the mathematical properties of which make the multi-clustering problem amenable to techniques that could not be used in a general rate-distortion setting. We first consider the case of two sources, where we derive single-letter bounds for the achievable region by connecting our setting to hypothesis testing and pattern recognition problems in the information theory literature. We complement these bounds with cardinality bounds for the auxiliary random variables, improving upon the results typically obtained by using the convex cover method. Applying these improved cardinality bounds to the case of a doubly symmetric binary source, we find a gap between the outer and inner bound, disproving a conjecture by Westover and O'Sullivan (2008). We generalize the problem setup to an arbitrary number of sources and show that a CEO problem with logarithmic loss distortion, which was previously investigated by Courtade and Weissman (2014), constitutes a special case of this multi-clustering problem. This CEO problem can be extended by requiring multiple description coding. Drawing from the theory of submodular functions, we prove a tight inner and outer bound for the resulting achievable region under a suitable conditional independence assumption. The single-letter characterization of the achievable region we obtain has some interesting technical properties. In particular, the rate requirement is in general insufficient to ensure successful typicality decoding of the corresponding description. Furthermore, we present a proof of the two-function case of a conjecture by Kumar and Courtade (2013), showing that the inequality I(f(Xⁿ); g(Yⁿ)) ≤ I(X;Y) holds for any two Boolean functions f and g, where (X,Y) is a doubly symmetric binary source. We also show that the dictator functions are essentially the only functions achieving equality. The key step in the proof is a careful analysis of the Fourier spectrum of the two Boolean functions. This allows us to reduce the statement to an elementary inequality which we subsequently prove.
en
Additional information:
Abweichender Titel nach Übersetzung der Verfasserin/des Verfassers