Solving row-sparse principal component analysis via convex integer programs
For general computational-intensive mixed-integer non-linear optimization problems, a major challenge is to verify/guarantee the quality of any feasible solution within tractable time/computational limits. A natural idea to tackle this challenge is constructing tight relaxations and designing approximation algorithms for relaxed problems. In this talk, we focus on the (row) sparse principal component analysis (rsPCA) problem, i.e., the problem of finding the top-r leading principal components of a covariance matrix such that all these principal components are linear combinations of a subset of k variables. We propose: (a) a convex integer programming relaxation of rsPCA that gives upper (dual) bounds for rsPCA, and; (b) a new local search algorithm for finding primal feasible solutions for rsPCA. We also show that, in the worst-case, the dual bounds provided by the convex IP are within an affine function of the globally optimal value. We demonstrate our techniques applied to large-scale covariance matrices. This is a joint work with Santanu S. Dey, Rahul Mazumder, Macro Molinaro.
When: 24th of November 2021 - 11am (EST)
More: Guanyi's Website