We provide a new hierarchy of semidefinite programming relaxations, called
NCTSSOS
, to solve large-scale sparse noncommutative polynomial optimization problems. This hierarchy features the ...exploitation of
term sparsity
hidden in the input data for eigenvalue and trace optimization problems. NCTSSOS complements the recent work that exploits
correlative sparsity
for noncommutative optimization problems by Klep et al. (MP, 2021), and is the noncommutative analogue of the TSSOS framework by Wang et al. (SIAMJO 31: 114–141, 2021, SIAMJO 31: 30–58, 2021). We also propose an extension exploiting simultaneously correlative and term sparsity, as done previously in the commutative case (Wang in CS-TSSOS: Correlative and term sparsity for large-scale polynomial optimization, 2020). Under certain conditions, we prove that the optima of the NCTSSOS hierarchy converge to the optimum of the corresponding dense semidefinite programming relaxation. We illustrate the efficiency and scalability of NCTSSOS by solving eigenvalue/trace optimization problems from the literature as well as randomly generated examples involving up to several thousand variables.
Construction of multivariate tight framelets is known to be a challenging problem because it is linked to the difficult problem on sum of squares of multivariate polynomials in real algebraic ...geometry. Multivariate dual framelets with vanishing moments generalize tight framelets and are not easy to be constructed either, since their construction is related to syzygy modules and factorization of multivariate polynomials. On the other hand, compactly supported multivariate framelets with directionality or high vanishing moments are of interest and importance in both theory and applications. In this paper we introduce the notion of a quasi-tight framelet, which is a dual framelet, but behaves almost like a tight framelet. Let ϕ∈L2(Rd) be an arbitrary compactly supported real-valued M-refinable function with a general dilation matrix M and ϕˆ(0)=1 such that its underlying real-valued low-pass filter satisfies the basic sum rule. We first constructively prove by a step-by-step algorithm that we can always easily derive from the arbitrary M-refinable function ϕ a directional compactly supported real-valued quasi-tight M-framelet in L2(Rd) associated with a directional quasi-tight M-framelet filter bank, each of whose high-pass filters has one vanishing moment and only two nonzero coefficients. If in addition all the coefficients of its low-pass filter are nonnegative, then such a quasi-tight M-framelet becomes a directional tight M-framelet in L2(Rd). Furthermore, we show by a constructive algorithm that we can always derive from the arbitrary M-refinable function ϕ a compactly supported quasi-tight M-framelet in L2(Rd) with the highest possible order of vanishing moments. We shall also present a result on quasi-tight framelets whose associated high-pass filters are purely differencing filters with the highest order of vanishing moments. Several examples will be provided to illustrate our main theoretical results and algorithms in this paper.
We introduce the prime coset sum method for constructing tight wavelet frames, which allows one to construct nonseparable multivariate tight wavelet frames with prime dilation, using a univariate ...lowpass mask with this same prime dilation as input. This method relies on the idea of finding a sum of hermitian squares representation for a nonnegative trigonometric polynomial related to the sub-QMF condition for the lowpass mask. We prove the existence of these representations under some conditions on the input lowpass mask, utilizing the special structure of the recently introduced prime coset sum method, which is used to generate the lowpass masks in our construction. We also prove guarantees on the vanishing moments of the wavelets arising from this method, some of which hold more generally.
Continuing our recent work in 5 we study polynomial masks of multivariate tight wavelet frames from two additional and complementary points of view: convexity and system theory. We consider such ...polynomial masks that are derived by means of the unitary extension principle from a single polynomial. We show that the set of such polynomials is convex and reveal its extremal points as polynomials that satisfy the quadrature mirror filter condition. Multiplicative structure of this polynomial set allows us to improve the known upper bounds on the number of frame generators derived from box splines. Moreover, in the univariate and bivariate settings, the polynomial masks of a tight wavelet frame can be interpreted as the transfer function of a conservative multivariate linear system. Recent advances in system theory enable us to develop a more effective method for tight frame constructions. Employing an example by S.W. Drury, we show that for dimension greater than 2 such transfer function representations of the corresponding polynomial masks do not always exist. However, for all wavelet masks derived from multivariate polynomials with non-negative coefficients, we determine explicit transfer function representations. We illustrate our results with several examples.
•Convexity and characterization of extremal points of sets of polynomials in UEP.•Connection between UEP and multivariate linear system theory.•Algebraic methods for UEP frames from polynomials with non-negative coefficients.
Recent advances in real algebraic geometry and in the theory of polynomial optimization are applied to answer some open questions in the theory of multivariate tight wavelet frames whose generators ...have at least one vanishing moment. Namely, several equivalent formulations of the so-called Unitary Extension Principle (UEP) are given in terms of Hermitian sums of squares of certain nonnegative Laurent polynomials and in terms of semidefinite programming. These formulations merge recent advances in real algebraic geometry and wavelet frame theory and lead to an affirmative answer to the long-standing open question of the existence of tight wavelet frames in dimension
d
=2. They also provide, for every
d
, efficient numerical methods for checking the existence of tight wavelet frames and for their construction. A class of counterexamples in dimension
d
=3 show that, in general, the so-called sub-QMF condition is not sufficient for the existence of tight wavelet frames. Stronger sufficient conditions for determining the existence of tight wavelet frames in dimension
d
≥3 are derived. The results are illustrated on several examples.
Numerous applied problems contain matrices as variables, and the formulas therefore involve polynomials in matrices. To handle such polynomials it is necessary study non-commutative polynomials. In ...this paper we will present an algorithm and its implementation in the free Matlab package NCSOStools using semidefinite programming to check whether a given non-commutative polynomial in non-symmetric variables can be written as a sum of Hermitian squares.
NCSOStools
is a Matlab toolbox for
*
symbolic computation with polynomials in noncommuting (NC) variables;
*
constructing and solving sum of Hermitian squares (with commutators) programs for ...polynomials in NC variables.
It can be used in combination with semidefinite programming software, such as SeDuMi, SDPA or SDPT3, to solve these constructed programs. This paper provides an overview of the theoretical underpinning of the sum of Hermitian squares (with commutators) programs and provides a gentle introduction to the primary features of
NCSOStools
.
We show that all the coefficients of the polynomial
are nonnegative whenever
m
≤13 is a nonnegative integer and
A
and
B
are positive semidefinite matrices of the same size. This has previously been ...known only for
m
≤7. The validity of the statement for arbitrary
m
has recently been shown to be equivalent to the Bessis-Moussa-Villani conjecture from theoretical physics. In our proof, we establish a connection to sums of hermitian squares of polynomials in noncommuting variables and to semidefinite programming. As a by-product we obtain an example of a real polynomial in two noncommuting variables having nonnegative trace on all symmetric matrices of the same size, yet not being a sum of hermitian squares and commutators.
We present tracial analogs of the classical results of Curto and Fialkow on moment matrices. A sequence of real numbers indexed by words in noncommuting variables with values invariant under cyclic ...permutations of the indexes, is called a tracial sequence. We prove that such a sequence can be represented with tracial moments of matrices if its corresponding moment matrix is positive semidefinite and of finite rank. A truncated tracial sequence allows for such a representation if and only if one of its extensions admits a flat extension. Finally, we apply this theory via duality to investigate trace-positive polynomials in noncommuting variables.
PDF
