An official website of the United States government
The multilinear polytope of a hypergraph is the convex hull of a set of binary points satisfying a collection of multilinear equations. We introduce the running intersection inequalities, a new class of facet-defining inequalities for the multilinear polytope. Accordingly, we define a new polyhedral relaxation of the multilinear polytope, referred to as the running intersection relaxation, and identify conditions under which this relaxation is tight. Namely, we show that for kite-free beta-acyclic hypergraphs, a class that lies between gamma-acyclic and beta-acyclic hypergraphs, the running intersection relaxation coincides with the multilinear polytope and it admits a polynomial size extended formulation.
more »
« less
Multilinear Singular Integral Forms of Christ-Journé Type
We introduce a class of multilinear singular integral forms which generalize the Christ-Journ´e multilinear forms. The research is partially motivated by an approach to Bressan’s problem on incompressible mixing flows. A key aspect of the theory is that the class of operators is closed under adjoints (i.e. the class of multilinear forms is closed under permutations of the entries).
more »
« less
- Award ID(s):
- 1764265
- PAR ID:
- 10087161
- Date Published:
- Journal Name:
- Memoirs of the American Mathematical Society
- Volume:
- 257
- Issue:
- 1231
- ISSN:
- 1947-6221
- Page Range / eLocation ID:
- 1-146
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract We study several model-theoretic aspects of W $$^*$$ ∗ -probability spaces, that is, $$\sigma $$ σ -finite von Neumann algebras equipped with a faithful normal state. We first study the existentially closed W $$^*$$ ∗ -spaces and prove several structural results about such spaces, including that they are type III $$_1$$ 1 factors that tensorially absorb the Araki–Woods factor $$R_\infty $$ R ∞ . We also study the existentially closed objects in the restricted class of W $$^*$$ ∗ -probability spaces with Kirchberg’s QWEP property, proving that $$R_\infty $$ R ∞ itself is such an existentially closed space in this class. Our results about existentially closed probability spaces imply that the class of type III $$_1$$ 1 factors forms a $$\forall _2$$ ∀ 2 -axiomatizable class. We show that for $$\lambda \in (0,1)$$ λ ∈ ( 0 , 1 ) , the class of III $$_\lambda $$ λ factors is not $$\forall _2$$ ∀ 2 -axiomatizable but is $$\forall _3$$ ∀ 3 -axiomatizable; this latter result uses a version of Keisler’s Sandwich theorem adapted to continuous logic. Finally, we discuss some results around elementary equivalence of III $$_\lambda $$ λ factors. Using a result of Boutonnet, Chifan, and Ioana, we show that, for any $$\lambda \in (0,1)$$ λ ∈ ( 0 , 1 ) , there is a family of pairwise non-elementarily equivalent III $$_\lambda $$ λ factors of size continuum. While we cannot prove the same result for III $$_1$$ 1 factors, we show that there are at least three pairwise non-elementarily equivalent III $$_1$$ 1 factors by showing that the class of full factors is preserved under elementary equivalence.more » « less
-
We consider global optimization of nonconvex problems whose factorable reformulations contain a collection of multilinear equations. Important special cases include multilinear and polynomial optimization problems. The multilinear polytope is the convex hull of the set of binary points z satisfying the system of multilinear equations given above. Recently Del Pia and Khajavirad introduced running intersection inequalities, a family of facet-defining inequalities for the multilinear polytope. In this paper we address the separation problem for this class of inequalities. We first prove that separating flower inequalities, a subclass of running intersection inequalities, is NP-hard. Subsequently, for multilinear polytopes of fixed degree, we devise an efficient polynomial-time algorithm for separating running intersection inequalities and embed the proposed cutting-plane generation scheme at every node of the branch-and-reduce global solver BARON. To evaluate the effectiveness of the proposed method we consider two test sets: randomly generated multilinear and polynomial optimization problems of degree three and four, and computer vision instances from an image restoration problem Results show that running intersection cuts significantly improve the performance of BARON and lead to an average CPU time reduction of 50% for the random test set and of 63% for the image restoration test set.more » « less
-
Byrka, Jaroslaw; Meka, Raghu (Ed.)In this work, we prove new relations between the bias of multilinear forms, the correlation between multilinear forms and lower degree polynomials, and the rank of tensors over F₂. We show the following results for multilinear forms and tensors. Correlation bounds. We show that a random d-linear form has exponentially low correlation with low-degree polynomials. More precisely, for d = 2^{o(k)}, we show that a random d-linear form f(X₁,X₂, … , X_d) : (F₂^{k}) ^d → F₂ has correlation 2^{-k(1-o(1))} with any polynomial of degree at most d/2 with high probability. This result is proved by giving near-optimal bounds on the bias of a random d-linear form, which is in turn proved by giving near-optimal bounds on the probability that a sum of t random d-dimensional rank-1 tensors is identically zero. Tensor rank vs Bias. We show that if a 3-dimensional tensor has small rank then its bias, when viewed as a 3-linear form, is large. More precisely, given any 3-dimensional tensor T: [k]³ → F₂ of rank at most t, the bias of the 3-linear form f_T(X₁, X₂, X₃) : = ∑_{(i₁, i₂, i₃) ∈ [k]³} T(i₁, i₂, i₃)⋅ X_{1,i₁}⋅ X_{2,i₂}⋅ X_{3,i₃} is at least (3/4)^t. This bias vs tensor-rank connection suggests a natural approach to proving nontrivial tensor-rank lower bounds. In particular, we use this approach to give a new proof that the finite field multiplication tensor has tensor rank at least 3.52 k, which is the best known rank lower bound for any explicit tensor in three dimensions over F₂. Moreover, this relation between bias and tensor rank holds for d-dimensional tensors for any fixed d.more » « less
-
Multilinear discriminant analysis (MLDA), a novel approach based upon recent developments in tensor-tensor decomposition, has been proposed recently and showed better performance than traditional matrix linear discriminant analysis (LDA). The current paper presents a nonlinear generalization of MLDA (referred to as KMLDA) by extending the well known ``kernel trick" to multilinear data. The approach proceeds by defining a new dot product based on new tensor operators for third-order tensors. Experimental results on the ORL, extended Yale B, and COIL-100 data sets demonstrate that performing MLDA in feature space provides more class separability. It is also shown that the proposed KMLDA approach performs better than the Tucker-based discriminant analysis methods in terms of image classification.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- The DOI is not currently available.
