CIF: Small: Sparsity in Quadratic Optimization through Low-Rank Approximations

University Of Texas At Austin, Austin TX

Investigators

Abstract

Nonnegativity and sparsity are highly desirable properties in data and signal decomposition algorithms. Nonnegativity is particularly relevant when the involved variables have a physical interpretation and ensures a separation of properties that interact in an additive manner. Nonnegativity and sparsity have been used in principal component analysis for numerous applications including bioinformatics, hyperspectral imaging and computer vision. This research involves the study of sparsity and nonnegativity in quadratic optimization problems. This project develops novel algorithms for solving such problems under sparsity and nonnegativity constraints using a low-rank projection framework. This framework allows the development of novel algorithms for nonnegative sparse principal component analysis and matrix factorization. The research program relies on a fruitful synthesis of tools from information theory, combinatorics and linear algebra. The developed algorithms are both empirically outperforming the previous state of the art and have provable approximation guarantees.