Detailansicht
A global matrix factorization problem for interference alignment
Markus Levonyak
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Informatik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Masterstudium Scientific Computing
Betreuer*in
Wilfried Gansterer
DOI
10.25365/thesis.41380
URN
urn:nbn:at:at-ubw:1-24210.32186.739772-8
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Interferenzausrichtung auf dem K-Teilnehmer-Interferenzkanal ist ein Verfahren der Informationstheorie zur Vermeidung elektromagnetischer Interferenz in drahtlosen Netzwerken durch Anwendung von Präkodierungsmatrizen V_j auf Senderseite und Postkodierungsmatrizen U_k auf Empfängerseite, sodass für alle j ~= k: U*_k H_kj V_j = 0 für gegebene Kanalmatrizen H_kj. Ein Algorithmus von Gomadam u. a. löst das Interferenzausrichtungsproblem durch iterative Optimierung von V_j und U_k bei allen Sendern und Empfängern. Es wurde jedoch bisher nicht bewiesen, dass dieser iterative Algorithmus gegen ein globales Optimum konvergiert. Um eine direkte und optimale Lösung zu finden, reformulieren wir das Interferenzausrichtungsproblem als das äquivalente Problem, eine gegebene globale Kanalmatrix H so zu faktorisieren, dass H = U S V*, wobei U, S und V Matrizen mit bestimmten dünnbesetzten Strukturen sind. Als ersten Schritt in Richtung einer direkten Lösung dieses globalen Matrizenfaktorisierungsproblems konzentrieren wir uns darauf, S durch Anwendung von unitären Householder- und Givenstransformationen auf H zu konstruieren. Wir schlagen mehrere Varianten eines direkten Algorithmus vor, die S mit vollen, tridiagonalen und bidiagonalen Hauptdiagonalblöcken einer blockdiagonalen Untermatrix erzeugen. Die Algorithmenvariante, die bidiagonale Blöcke hervorbringt, akzeptiert alle Eingabeparameterwerte, die mit den Durchführbarkeitskriterien für Interferenzausrichtung aus der Literatur übereinstimmen. Unter Betrachtung der Hauptdiagonalelemente, die gleich null sein müssen, argumentieren wir, dass U und V keine Produkte von Householder- und Givensmatrizen sein können und es daher keine direkte Lösung des allgemeinen globalen Matrizenfaktorisierungsproblems ausschließlich basierend auf Householderspiegelungen und Givensdrehungen gibt. Auf Grundlage von numerischen Experimenten mit einer prototypischen Implementierung des iterativen Algorithmus erkennen wir, dass eine prototypische Implementierung unseres direkten Algorithmus beträchtlich weniger Operationen benötigt, wodurch die Bedeutung und das Potenzial einer direkten Lösung des Interferenzausrichtungsproblems ersichtlich ist.
Abstract
(Englisch)
Interference alignment on the K-user interference channel is a technique from information theory that aims to avoid electromagnetic interference in wireless networks by employing precoding matrices V_j at the transmitters and postcoding matrices U_k at the receivers such that for all j ~= k: U*_k H_kj V_j = 0 for given channel matrices H_kj. An algorithm by Gomadam et al. solves the interference alignment problem by iteratively optimizing V_j and U_k at all transmitters and receivers. However, it has not yet been proved that this iterative algorithm converges to a global optimum. For the purpose of finding a direct and optimal solution, we reformulate the interference alignment problem as the equivalent problem to factorize a given global channel matrix H such that H = U S V*, where U, S, and V are matrices of specific sparsity patterns. As a first step towards a direct solution to this global matrix factorization problem, we focus on constructing S by applying unitary Householder and Givens transformations to H. We propose several variants of a direct algorithm that create S with full, tridiagonal, and bidiagonal main diagonal blocks of a block-diagonal submatrix. The bidiagonal blocks algorithm variant accepts all input parameter values in conformance with the feasibility criteria for interference alignment from the literature. In consideration of the main diagonal elements that have to be equal to zero, we argue that U and V cannot be products of Householder and Givens matrices, and hence, there is no direct solution to the general global matrix factorization problem solely based on Householder reflections and Givens rotations. On the basis of numerical experiments with a prototype implementation of the iterative algorithm, we discover that a prototype implementation of our direct algorithm requires substantially less operations, which shows the relevance and potential of a direct solution to the interference alignment problem.
Schlagwörter
Schlagwörter
(Englisch)
interference alignment direct algorithm matrix factorization Householder reflection Givens rotation
Schlagwörter
(Deutsch)
Interferenzausrichtung direkter Algorithmus Matrizenfaktorisierung Householderspiegelung Givensdrehung
Autor*innen
Markus Levonyak
Haupttitel (Englisch)
A global matrix factorization problem for interference alignment
Paralleltitel (Deutsch)
Ein globales Matrizenfaktorisierungsproblem für Interferenzausrichtung
Publikationsjahr
2016
Umfangsangabe
xvi, 140 Seiten : Diagramme
Sprache
Englisch
Beurteiler*in
Wilfried Gansterer
AC Nummer
AC13086028
Utheses ID
36622
Studienkennzahl
UA | 066 | 940 | |