Related papers: Sums of Separable and Quadratic Polynomials

Sums of Separable and Quadratic Polynomials

URL: http://arxiv.org/abs/2105.04766v1
Date: Tue, 11 May 2021 03:26:46 GMT
Title: Sums of Separable and Quadratic Polynomials
Authors: Amir Ali Ahmadi, Cemil Dibek, Georgina Hall
Abstract summary: We study separable plus quadratic (SPQ)s. We show that convex SPQ optimization problems can be solved by "small" semidefinite programs.
Score: 0.3222802562733786
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We study separable plus quadratic (SPQ) polynomials, i.e., polynomials that are the sum of univariate polynomials in different variables and a quadratic polynomial. Motivated by the fact that nonnegative separable and nonnegative quadratic polynomials are sums of squares, we study whether nonnegative SPQ polynomials are (i) the sum of a nonnegative separable and a nonnegative quadratic polynomial, and (ii) a sum of squares. We establish that the answer to question (i) is positive for univariate plus quadratic polynomials and for convex SPQ polynomials, but negative already for bivariate quartic SPQ polynomials. We use our decomposition result for convex SPQ polynomials to show that convex SPQ polynomial optimization problems can be solved by "small" semidefinite programs. For question (ii), we provide a complete characterization of the answer based on the degree and the number of variables of the SPQ polynomial. We also prove that testing nonnegativity of SPQ polynomials is NP-hard when the degree is at least four. We end by presenting applications of SPQ polynomials to upper bounding sparsity of solutions to linear programs, polynomial regression problems in statistics, and a generalization of Newton's method which incorporates separable higher-order derivative information.

Related papers

Efficient Solution of Point-Line Absolute Pose [52.775981113238046]
We revisit certain problems of pose estimation based on 3D--2D correspondences between features which may be points or lines. We show experimentally that the resulting solvers are numerically stable and fast.
arXiv Detail & Related papers (2024-04-25T12:09:16Z)
Sums of squares certificates for polynomial moment inequalities [1.6385815610837167]
This paper introduces and develops the framework of moment expressions, which are expressions in commuting variables and their formal mixed moments. As an application, two open nonlinear Bell inequalities from quantum physics are settled.
arXiv Detail & Related papers (2023-06-09T08:55:26Z)
Influences of Fourier Completely Bounded Polynomials and Classical Simulation of Quantum Algorithms [0.0]
We show that quantum query algorithms are characterized by a new class of Fourier completely boundeds. We conjecture that all suchs have an influential variable. Our proof is simpler, obtains better constants and does not use randomness.
arXiv Detail & Related papers (2023-04-13T17:58:36Z)
State polynomials: positivity, optimization and nonlinear Bell inequalities [3.9692590090301683]
This paper introduces states in noncommuting variables and formal states of their products. It shows that states, positive over all and matricial states, are sums of squares with denominators. It is also established that avinetengle Kritivsatz fails to hold in the state setting.
arXiv Detail & Related papers (2023-01-29T18:52:21Z)
A Direct Reduction from the Polynomial to the Adversary Method [92.54311953850168]
We give a simple and direct reduction from the method (in the form of a dual) to the adversary method. This shows that any lower bound in the form of a dual is an adversary lower bound of a specific form.
arXiv Detail & Related papers (2023-01-24T21:37:20Z)
An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree [79.43134049617873]
In this paper, we demonstrate an exponential separation between exact degree and approximate quantum query for a partial function. For an alphabet size, we have a constant versus separation complexity.
arXiv Detail & Related papers (2023-01-22T22:08:28Z)
Two-body Coulomb problem and $g^{(2)}$ algebra (once again about the Hydrogen atom) [77.34726150561087]
It is shown that if the symmetry of the three-dimensional system is $(r, rho, varphi)$, the variables $(r, rho, varphi)$ allow a separation of variable $varphi$ and eigenfunctions. Thoses occur in the study of the Zeeman effect on Hydrogen atom.
arXiv Detail & Related papers (2022-12-02T20:11:17Z)
Complexity aspects of local minima and related notions [3.42658286826597]
We consider the notions of (i) critical points, (ii) second-order points, (iii) local minima, and (iv) strict local minima for multivariates. We show that it is strongly NP-hard to decide if a cubic has a critical point. We briefly present a potential application of finding local minima cubics to the design of a third-order Newton method.
arXiv Detail & Related papers (2020-08-14T00:50:13Z)
SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
SURF is an algorithm for approximating distributions by piecewises. It outperforms state-of-the-art algorithms in experiments.
arXiv Detail & Related papers (2020-02-22T01:03:33Z)
A refinement of Reznick's Positivstellensatz with applications to quantum information theory [72.8349503901712]
In Hilbert's 17th problem Artin showed that any positive definite in several variables can be written as the quotient of two sums of squares. Reznick showed that the denominator in Artin's result can always be chosen as an $N$-th power of the squared norm of the variables.
arXiv Detail & Related papers (2019-09-04T11:46:26Z)
Discrete orthogonality relations for multi-indexed Laguerre and Jacobi polynomials [0.0]
We show that they also hold for multi-indexed Laguerre and Jacobis. We show that they also hold for Krein-Adlers based on the Hermite, Laguerre and Jacobis.
arXiv Detail & Related papers (2019-07-21T10:15:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.