Quadratic maximization under combinatorial constraints and related applications

dc.contributor.advisorDimakis, Alexandros G.
dc.contributor.committeeMemberCaramanis, Constantine
dc.contributor.committeeMemberPrice, Eric
dc.contributor.committeeMemberShakkottai, Sanjay
dc.contributor.committeeMemberSanghavi, Sujay
dc.creatorAsteris, Megasthenis
dc.date.accessioned2017-04-14T14:57:49Z
dc.date.available2017-04-14T14:57:49Z
dc.date.issued2016-12
dc.date.submittedDecember 2016
dc.date.updated2017-04-14T14:57:49Z
dc.description.abstractMotivated primarily by restricted variants of Principal Component Analysis (PCA), we study quadratic maximization problems subject to sparsity, nonnegativity and other combinatorial constraints. Intuitively, a key technical challenge is determining the support of the optimal solution. We develop a method that can surprisingly solve the maximization exactly when the argument matrix of the quadratic objective is positive semidefinite and has constant rank. Our approach relies on a hyper-spherical transformation of the low-rank space and has complexity that scales exponentially in the rank of the input, but polynomially in the ambient dimension. Extending these observations, we describe a simpler {approximation} algorithm based on exploring the low-rank space with an [epsilon]-net, drastically improving the dependence on the ambient dimension, implying a Polynomial Time Approximation Scheme (PTAS) for inputs with rank scaling up to logarithmically in the dimension or sufficiently sharp spectral decay. We discuss extensions of our approach to jointly computing multiple principal components under combinatorial constraints, such as the problem of extracting multiple orthogonal nonnegative components, or sparse components with common or disjoint supports, and related approximate matrix factorization problems. We further extend our quadratic maximization framework to bilinear optimization problems and employ it in the context of specific applications, e.g., to develop a provable approximation algorithm for the NP-hard problem of Bipartite Correlation Clustering (BCC). Real datasets will typically produce covariance matrices that have full rank, rendering our algorithms not applicable. Our approach is to first obtain a low-rank approximation of the input data and subsequently solve the low-rank problem using our framework. Although this approach is not always suitable, from an optimization perspective it yields provable, data-dependent performance bounds that rely on the spectral decay of the input and the employed approximation technique. Interestingly, most real matrices can be well approximated by low-rank surrogates since the eigenvalues display a significant decay. Empirical evaluation shows that our algorithms have excellent performance and in many cases outperform the previous state of the art. Finally, utilizing our framework, we develop algorithms with interesting theoretical guarantees in the context of specific applications, such as approximate Orthogonal Nonnegative Matrix Factorization or Bipartite Correlation Clustering.
dc.description.departmentElectrical and Computer Engineering
dc.format.mimetypeapplication/pdf
dc.identifierdoi:10.15781/T2TT4FZ7M
dc.identifier.urihttp://hdl.handle.net/2152/46455
dc.language.isoen
dc.subjectQuadratic maximization
dc.subjectSparse nonnegative PCA
dc.titleQuadratic maximization under combinatorial constraints and related applications
dc.typeThesis
dc.type.materialtext
thesis.degree.departmentElectrical and Computer Engineering
thesis.degree.disciplineElectrical and Computer engineering
thesis.degree.grantorThe University of Texas at Austin
thesis.degree.levelDoctoral
thesis.degree.nameDoctor of Philosophy

Access full-text files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
ASTERIS-DISSERTATION-2016.pdf
Size:
4.13 MB
Format:
Adobe Portable Document Format

License bundle

Now showing 1 - 2 of 2
No Thumbnail Available
Name:
PROQUEST_LICENSE.txt
Size:
4.46 KB
Format:
Plain Text
Description:
No Thumbnail Available
Name:
LICENSE.txt
Size:
1.85 KB
Format:
Plain Text
Description: