Search

This paper studies an optimization problem on the sum of traces of matrix quadratic forms in m semiorthogonal matrices, which can be considered as a generalization of the synchronization of rotations. While the problem is nonconvex, this paper shows that its semidefinite pro-gramming relaxation solves the original nonconvex problems exactly with high probability under an additive noise model with small noise in the order of O(m1/4). In addition, it shows that, with high probability, the sufficient condition for global optimality considered in Won, Zhou, and Lange [SIAM J. Matrix Anal. Appl., 2 (2021), pp. 859-882] is also necessary under a similar small noise condition. These results can be considered as a generalization of existing results on phase synchronization. [ABSTRACT FROM AUTHOR]

For two graphs $F$ and $H$, the relative Turán number ${ex}(H,F)$ is the maximum number of edges in an $F$-free subgraph of $H$. Foucaud, Krivelevich, and Perarnau [SIAM J. Discrete Math., 29 (2015), pp. 65--78] and Perarnau and Reed [Combin. Probab. Comput., 26 (2017), pp. 448--467] studied these quantities as a function of the maximum degree of $H$. In this paper, we study a generalization for uniform hypergraphs. If $F$ is a complete $r$-partite $r$-uniform hypergraph with parts of sizes $s_1,s_2,\dots,s_r$ with each $s_{i + 1}$ sufficiently large relative to $s_i$, then with $1/\beta = \sum_{i = 2}^r \prod_{j = 1}^{i - 1} s_j$ we prove that for any $r$-uniform hypergraph $H$ with maximum degree $\Delta$, ${ex}(H,F)\ge \Delta^{-\beta - o(1)} \cdot e(H).$ This is tight as $\Delta \rightarrow \infty$ up to the $o(1)$ term in the exponent, since we show there exists a $\Delta$-regular $r$-graph $H$ such that ${ex}(H,F)=O(\Delta^{-\beta}) \cdot e(H)$. Similar tight results are obtained when $H$ is the random $n$-vertex $r$-graph $H_{n,p}^r$ with edge-probability $p$, extending results of Balogh and Samotij [J. Lond. Math. Soc., 83 (2011), pp. 1091--1094] and Morris and Saxton [Adv. Math., 298 (2016), pp. 534--580]. General lower bounds for a wider class of $F$ are also obtained. [ABSTRACT FROM AUTHOR]

A convex optimization problem in conic form involves minimizing a linear functional over the intersection of a convex cone and an affine subspace. In some cases, it is possible to replace a conic formulation using a certain cone, with a “lifted” conic formulation using another cone that is higher-dimensional, but simpler, in some sense. One situation in which this can be computationally advantageous is when the higher-dimensional cone is a Cartesian product of many “low-complexity” cones, such as second-order cones, or small positive semidefinite cones. This paper studies obstructions to a convex cone having a lifted representation with such a product structure. The main result says that whenever a convex cone has a certain neighborliness property, then it does not have a lifted representation using a finite product of cones, each of which has only short chains of faces. This is a generalization of recent work of Averkov [SIAM J. Appl. Alg. Geom., 3 (2019), pp. 128–151], which considers only lifted representations using products of positive semidefinite cones of bounded size. Among the consequences of the main result is that various cones related to nonnegative polynomials do not have lifted representations using products of “low-complexity” cones, such as smooth cones, the exponential cone, and cones defined by hyperbolic polynomials of low degree. [ABSTRACT FROM AUTHOR]

A method to compute guaranteed lower bounds to the eigenvalues of the Maxwell system in two or three space dimensions is proposed as a generalization of the method of Liu and Oishi [SIAM J. Numer. Anal., 51 (2013), pp. 1634-1654] for the Laplace operator. The main tool is the computation of an explicit upper bound to the error of the Galerkin projection. The error is split into two parts. One part is controlled by a hypercircle principle and an auxiliary eigenvalue problem. The second part requires a perturbation argument for the right-hand side replaced by a suitable piecewise polynomial. The latter error is controlled through the use of the commuting quasi-interpolation by Falk and Winther and computational bounds on its stability constant. This situation is different from the Laplace operator where such a perturbation is easily controlled through local Poincaré inequalities. The practical viability of the approach is demonstrated in test cases for two and three space dimensions. [ABSTRACT FROM AUTHOR]

We develop a formal construction of a pointwise divergence-free basis in the nonconforming virtual element method of arbitrary order for the Stokes problem introduced in Zhao et al. (SIAM J. Numer. Anal. 57(6):2730–2759, 2019). The proposed construction can be seen as a generalization of the divergence-free basis in Crouzeix-Raviart finite element space (Brenner, Math. Comp. 55(192):411–437, 1990; Thomasset, 1981) to the virtual element space. Using the divergence-free basis obtained from our construction, we can eliminate the pressure variable from the mixed system and obtain a symmetric positive definite system. Several numerical tests are presented to confirm the efficiency and the accuracy of our construction. [ABSTRACT FROM AUTHOR]

This study computes the gradient of a function of numerical solutions of ordinary differential equations (ODEs) with respect to the initial condition. The adjoint method computes the gradient approximately by solving the corresponding adjoint system numerically. In this context, Sanz-Serna [SIAM Rev., 58 (2016), pp. 3–33] showed that when the initial value problem is solved by a Runge–Kutta (RK) method, the gradient can be exactly computed by applying an appropriate RK method to the adjoint system. Focusing on the case where the initial value problem is solved by a partitioned RK (PRK) method, this paper presents a numerical method, which can be seen as a generalization of PRK methods, for the adjoint system that gives the exact gradient. [ABSTRACT FROM AUTHOR]

We generalize the concept of adaptive sampling rules to the sketch-and-project method for solving linear systems. Analyzing adaptive sampling rules in the sketch-and-project setting yields convergence results that apply to all special cases at once, including the Kaczmarz and coordinate descent. This eliminates the need to separately analyze analogous adaptive sampling rules in each special case. To deduce new sampling rules, we show how the progress of one step of the sketch-and-project method depends directly on a sketched residual. Based on this insight, we derive a (1) max-distance sampling rule, by sampling the sketch with the largest sketched residual,(2) a proportional sampling rule, by sampling proportional to the sketched residual, and finally (3)a capped sampling rule. The capped sampling rule is a generalization of the recently introduced adaptive sampling rules for the Kaczmarz method [Z.-Z. Bai and W.-T. Wu,SIAM J. Sci. Comput.,40 (2018), pp. A592--A606]. We provide a global exponential convergence theorem for each sampling rule and show that the max-distance sampling rule enjoys the fastest convergence. This finding is alsoverified in extensive numerical experiments that lead us to conclude that the max-distance sampling rule is superior both experimentally and theoretically to the capped sampling rule. We also provide numerical insights into implementing the adaptive strategies so that the per iteration cost is of the same order as using a fixed sampling strategy when the product of the number of sketches with the sketch size is not significantly larger than the number of columns [ABSTRACT FROM AUTHOR]