2021/08/02 by Yong Sheng Soh, Soh, Yong Sheng, Antonios Varvitsiotis +1
Mathematics · #Advanced Optimization Algorithms Research #FOS: Computer and information sciences #FOS: Electrical engineering #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Mathematical Inequalities and Applications #Optimization and Control (math.OC) #Signal Processing (eess.SP) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.2108.00740
openalex publication_date 2021/08/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a matrix X∈ ℝm× n+ with non-negative entries, the cone factorization problem over a cone K⊆ ℝk concerns computing \ a1,…, am \ ⊆ K and \ b1,…, bn \ ⊆~K^* belonging to its dual so that Xij = ⟨ ai, bj ⟩ for all i∈ [m], j∈ [n]. Cone factorizations are fundamental to mathematical optimization as they allow us to express convex bodies as feasible regions of linear conic programs. In this paper, we introduce and analyze the symmetric-cone multiplicative update (SCMU) algorithm for computing cone factorizations when K is symmetric; i.e., it is self-dual and homogeneous. Symmetric cones are of central interest in mathematical optimization as they provide a common language for studying linear optimization over the nonnegative orthant (linear programs), over the second-order cone (second order cone programs), and over the cone of positive semidefinite matrices (semidefinite programs). The SCMU algorithm is multiplicative in the sense that the iterates are updated by applying a meticulously chosen automorphism of the cone computed using a generalization of the geometric mean to symmetric cones. Using an extension of Lieb's concavity theorem and von Neumann's trace inequality to symmetric cones, we show that the squared loss objective is non-decreasing along the trajectories of the SCMU algorithm. Specialized to the nonnegative orthant, the SCMU algorithm corresponds to the seminal algorithm by Lee and Seung for computing Nonnegative Matrix Factorizations.