Matrix factorization via polynomial optimization
In light of recent data science trends, new interest has fallen in alternative matrix factorizations. By this, we mean various ways of factorizing particular data matrices so that the factors have special properties and reveal insights into the original data. We are interested in the specialized ranks associated with these factorizations, but they are usually difficult to compute. In particular, we consider the nonnegative-, completely positive-, and separable ranks. We focus on a general tool for approximating factorization ranks, the moment hierarchy, a classical technique from polynomial optimization, further augmented by exploiting ideal-sparsity. Contrary to other examples of sparsity, the resulting sparse hierarchy yields equally strong, if not superior, bounds while potentially delivering a speed-up in computation.
|Springer Optimization and Its Applications
|Polynomial Optimization, Efficiency through Moments and Algebra
|Networks and Optimization
Steenkamp, A. (2023). Matrix factorization via polynomial optimization. In Polynomial Optimization, Moments, and Applications (pp. 153–180). doi:10.1007/978-3-031-38659-6_5