2022/02/17 by Victor Magron, Magron, Victor, Ngoc Hoang Anh +5
Mathematics · #Advanced Topology and Set Theory #FOS: Mathematics #Mathematical Dynamics and Fractals #Mathematical and Theoretical Analysis #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.2202.08731
openalex publication_date 2022/02/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We focus on computing certified upper bounds for the positive maximal singular value (PMSV) of a given matrix. The PMSV problem boils down to maximizing a quadratic polynomial on the intersection of the unit sphere and the nonnegative orthant. We provide a hierarchy of tractable semidefinite relaxations to approximate the value of the latter polynomial optimization problem as closely as desired. This hierarchy is based on an extension of Pólya's representation theorem. Doing so, positive polynomials can be decomposed as weighted sums of squares of s-nomials, where s can be a priori fixed (s=1 corresponds to monomials, s=2 corresponds to binomials, etc.). This in turn allows us to control the size of the resulting semidefinite relaxations.