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

非负性和稀疏性是数据和信号分解算法中非常理想的性质。当所涉及的变量具有物理解释并确保以相加方式相互作用的属性的分离时，非负性尤其相关。非负性和稀疏性在主成分分析中有着广泛的应用，包括生物信息学、高光谱成像和计算机视觉。本研究涉及二次优化问题的稀疏性和非负性的研究。这个项目开发了一种新的算法来解决稀疏性和非负性约束下的这类问题，使用了一个低阶投影框架。这一框架允许开发非负稀疏主成分分析和矩阵因式分解的新算法。该研究项目依赖于信息论、组合学和线性代数工具的卓有成效的综合。所开发的算法在经验上都超过了以前的技术水平，并且具有可证明的近似保证。

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.