Show simple item record

dc.contributor.advisorVishwanath, Sriramen
dc.contributor.advisorVikalo, Harisen
dc.creatorLee, Sang Hyun, 1977-en
dc.date.accessioned2011-06-01T17:07:04Zen
dc.date.accessioned2011-06-01T17:07:12Zen
dc.date.available2011-06-01T17:07:04Zen
dc.date.available2011-06-01T17:07:12Zen
dc.date.issued2011-05en
dc.date.submittedMay 2011en
dc.identifier.urihttp://hdl.handle.net/2152/ETD-UT-2011-05-3093en
dc.descriptiontexten
dc.description.abstractDistributed iterative algorithms are of great importance, as they are known to provide low-complexity and approximate solutions to what are otherwise high-dimensional intractable optimization problems. The theory of message-passing based algorithms is fairly well developed in the coding, machine learning and statistical physics literatures. Even though several applications of message-passing algorithms have already been identified, this work aims at establishing that a plethora of other applications exist where it can be of great importance. In particular, the goal of this work is to develop and demonstrate applications of this class of algorithms in network communications and computational biology. In the domain of communications, message-passing based algorithms provide distributed ways of inferring the optimal solution without the aid of a central agent for various optimization problems that happen in the resource allocation of communication networks. Our main framework is Affinity Propagation (AP), originally developed for clustering problems. We reinterpret this framework to unify the development of distributed algorithms for discrete resource allocation problems. Also, we consider a network-coded communication network, where continuous rate allocation is studied. We formulate an optimization problem with a linear cost function, and then utilize a Belief Propagation (BP) approach to determine a decentralized rate allocation strategy. Next, we move to the domain of computational biology, where graphical representations and computational biology play a major role. First, we consider the motif finding problem with several DNA sequences. In effect, this is a sequence matching problem, which can be modeled using various graphical representations and also solved using low-complexity algorithms based on message-passing techniques. In addition, we address the application of message-passing algorithms for a DNA sequencing problem where the one dimensional structure of a single DNA sequence is identified. We reinterpret the problem as being equivalent to the decoding of a nonlinear code. Based on the iterative decoding framework, we develop an appropriate graphical model which enables us to derive a message-passing algorithm to improve the performance of the DNA sequencing problem. Although this work consists of disparate application domains of communications, networks and computational biology, graphical models and distributed message-passing algorithms form a common underlying theme.en
dc.format.mimetypeapplication/pdfen
dc.language.isoengen
dc.subjectDistributed algorithmsen
dc.subjectGraphical modelsen
dc.subjectBelief propagationen
dc.subjectAffinity propagationen
dc.subjectResource allocationen
dc.subjectGenomic sequence analysisen
dc.subjectDistributed iterative algorithmsen
dc.subjectMessage-passing algorithmsen
dc.titleOn a class of distributed algorithms over networks and graphsen
dc.date.updated2011-06-01T17:07:12Zen
dc.contributor.committeeMemberPowers, Edward J.en
dc.contributor.committeeMemberGhosh, Joydeepen
dc.contributor.committeeMemberSanghavi, Sujayen
dc.contributor.committeeMemberQiu, Lilien
dc.description.departmentElectrical and Computer Engineeringen
dc.type.genrethesisen
thesis.degree.departmentElectrical and Computer Engineeringen
thesis.degree.disciplineElectrical and Computer Engineeringen
thesis.degree.grantorUniversity of Texas at Austinen
thesis.degree.levelDoctoralen
thesis.degree.nameDoctor of Philosophyen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record