Structured numerical problems in contemporary applications

dc.contributor.advisorDhillon, Inderjit S.
dc.creatorSustik, Mátyás Attilaen
dc.date.accessioned2013-10-31T15:49:13Zen
dc.date.issued2013-05en
dc.date.submittedMay 2013en
dc.date.updated2013-10-31T15:49:13Zen
dc.descriptiontexten
dc.description.abstractThe presence of structure in a computational problem can often be exploited and can lead to a more efficient numerical algorithm. In this dissertation, we look at structured numerical problems that arise from applications in wireless communications and machine learning that also impact other areas of scientific computing. In wireless communication system designs, certain structured matrices (frames) need to be generated. The design of such matrices is equivalent to a symmetric inverse eigenvalue problem where the values of the diagonal elements are prescribed. We present algorithms that are capable of generating a larger set of these constructions than previous algorithms. We also discuss the existence of equiangular tight frames---frames that satisfy additional structural properties. Kernel learning is an important class of problems in machine learning. It often relies on efficient numerical algorithms that solve underlying convex optimization problems. In our work, the objective functions to be minimized are the von Neumann and the LogDet Bregman matrix divergences. The algorithm that solves this optimization problem performs matrix updates based on repeated eigendecompositions of diagonal plus rank-one matrices in the case of von Neumann matrix divergence, and Cholesky updates in case of the LogDet Bregman matrix divergence. Our contribution exploits the low-rank representations and the structure of the constraint matrices, resulting in more efficient algorithms than previously known. We also present two specialized zero-finding algorithms where we exploit the structure through the shape and exact formulation of the objective function. The first zero-finding task arises during the matrix update step which is part of the above-mentioned kernel learning application. The second zero-finding problem is for the secular equation; it is equivalent to the computation of the eigenvalues of a diagonal plus rank-one matrix. The secular equation arises in various applications, the most well-known is the divide-and-conquer eigensolver. In our solutions, we build upon a somewhat forgotten zero-finding method by P. Jarratt, first described in 1966. The method employs first derivatives only and needs the same amount of evaluations as Newton's method, but converges faster. Our contributions are the more efficient specialized zero-finding algorithms.en
dc.description.departmentComputer Sciencesen
dc.format.mimetypeapplication/pdfen
dc.identifier.urihttp://hdl.handle.net/2152/21855en
dc.language.isoen_USen
dc.subjectMatrix computationen
dc.subjectInverse eigenvalue problemen
dc.subjectEquiangular frameen
dc.subjectBregman divergenceen
dc.subjectZero-findingen
dc.subjectDivide-and-conquer eigensolveren
dc.titleStructured numerical problems in contemporary applicationsen
thesis.degree.departmentComputer Sciencesen
thesis.degree.disciplineComputer Scienceen
thesis.degree.grantorThe University of Texas at Austinen
thesis.degree.levelDoctoralen
thesis.degree.nameDoctor of Philosophyen

Access full-text files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
SUSTIK-DISSERTATION-2013.pdf
Size:
573.82 KB
Format:
Adobe Portable Document Format

License bundle

Now showing 1 - 3 of 3
No Thumbnail Available
Name:
LICENSE_2.txt
Size:
1.84 KB
Format:
Plain Text
Description:
No Thumbnail Available
Name:
LICENSE_1.txt
Size:
1.84 KB
Format:
Plain Text
Description:
No Thumbnail Available
Name:
LICENSE.txt
Size:
1.84 KB
Format:
Plain Text
Description: