With the goal of obtaining strong relaxations for binary polynomial optimization problems, we introduce the pseudo-Boolean polytope defined as the convex hull of the set of binary points satisfying a collection of equations containing pseudo-Boolean functions. By representing the pseudo-Boolean polytope via a signed hypergraph, we obtain sufficient conditions under which this polytope has a polynomial-size extended formulation. Our new framework unifies and extends all prior results on the existence of polynomial-size extended formulations for the convex hull of the feasible region of binary polynomial optimization problems of degree at least three.
Multivariate imputation by chained equations (MICE) is one of the most popular approaches to address missing values in a data set. This approach requires specifying a univariate imputation model for every variable under imputation. The specification of which predictors should be included in these univariate imputation models can be a daunting task. Principal component analysis (PCA) can simplify this process by replacing all of the potential imputation model predictors with a few components summarizing their variance. In this article, we extend the use of PCA with MICE to include a supervised aspect whereby information from the variables under imputation is incorporated into the principal component estimation. We conducted an extensive simulation study to assess the statistical properties of MICE with different versions of supervised dimensionality reduction and we compared them with the use of classical unsupervised PCA as a simpler dimensionality reduction technique.
A new numerical domain decomposition method is proposed for solving elliptic equations on compact Riemannian manifolds. The advantage of this method is to avoid global triangulations or grids on manifolds. Our method is numerically tested on some $4$-dimensional manifolds such as the unit sphere $S^{4}$, the complex projective space $\mathbb{CP}^{2}$ and the product manifold $S^{2} \times S^{2}$.
Finding functions, particularly permutations, with good differential properties has received a lot of attention due to their possible applications. For instance, in combinatorial design theory, a correspondence of perfect $c$-nonlinear functions and difference sets in some quasigroups was recently shown [1]. Additionally, in a recent manuscript by Pal and Stanica [20], a very interesting connection between the $c$-differential uniformity and boomerang uniformity when $c=-1$ was pointed out, showing that that they are the same for an odd APN permutations. This makes the construction of functions with low $c$-differential uniformity an intriguing problem. We investigate the $c$-differential uniformity of some classes of permutation polynomials. As a result, we add four more classes of permutation polynomials to the family of functions that only contains a few (non-trivial) perfect $c$-nonlinear functions over finite fields of even characteristic. Moreover, we include a class of permutation polynomials with low $c$-differential uniformity over the field of characteristic~$3$. As a byproduct, our proofs shows the permutation property of these classes. To solve the involved equations over finite fields, we use various techniques, in particular, we find explicitly many Walsh transform coefficients and Weil sums that may be of an independent interest.
We propose and analyze a novel symmetric exponential wave integrator (sEWI) for the nonlinear Schr\"odinger equation (NLSE) with low regularity potential and typical power-type nonlinearity of the form $ f(\rho) = \rho^\sigma $, where $ \rho:=|\psi|^2 $ is the density with $ \psi $ the wave function and $ \sigma > 0 $ is the exponent of the nonlinearity. The sEWI is explicit and stable under a time step size restriction independent of the mesh size. We rigorously establish error estimates of the sEWI under various regularity assumptions on potential and nonlinearity. For "good" potential and nonlinearity ($H^2$-potential and $\sigma \geq 1$), we establish an optimal second-order error bound in $L^2$-norm. For low regularity potential and nonlinearity ($L^\infty$-potential and $\sigma > 0$), we obtain a first-order $L^2$-norm error bound accompanied with a uniform $H^2$-norm bound of the numerical solution. Moreover, adopting a new technique of \textit{regularity compensation oscillation} (RCO) to analyze error cancellation, for some non-resonant time steps, the optimal second-order $L^2$-norm error bound is proved under a weaker assumption on the nonlinearity: $\sigma \geq 1/2$. For all the cases, we also present corresponding fractional order error bounds in $H^1$-norm, which is the natural norm in terms of energy. Extensive numerical results are reported to confirm our error estimates and to demonstrate the superiority of the sEWI, including much weaker regularity requirements on potential and nonlinearity, and excellent long-time behavior with near-conservation of mass and energy.
We propose and analyze an extended Fourier pseudospectral (eFP) method for the spatial discretization of the Gross-Pitaevskii equation (GPE) with low regularity potential by treating the potential in an extended window for its discrete Fourier transform. The proposed eFP method maintains optimal convergence rates with respect to the regularity of the exact solution even if the potential is of low regularity and enjoys similar computational cost as the standard Fourier pseudospectral method, and thus it is both efficient and accurate. Furthermore, similar to the Fourier spectral/pseudospectral methods, the eFP method can be easily coupled with different popular temporal integrators including finite difference methods, time-splitting methods and exponential-type integrators. Numerical results are presented to validate our optimal error estimates and to demonstrate that they are sharp as well as to show its efficiency in practical computations.
A convincing feature of least-squares finite element methods is the built-in a posteriori error estimator for any conforming discretization. In order to generalize this property to discontinuous finite element ansatz functions, this paper introduces a least-squares principle on piecewise Sobolev functions for the solution of the Poisson model problem in 2D with mixed boundary conditions. It allows for fairly general discretizations including standard piecewise polynomial ansatz spaces on triangular and polygonal meshes. The presented scheme enforces the interelement continuity of the piecewise polynomials by additional least-squares residuals. A side condition on the normal jumps of the flux variable requires a vanishing integral mean and enables a natural weighting of the jump in the least-squares functional in terms of the mesh size. This avoids over-penalization with additional regularity assumptions on the exact solution as usually present in the literature on discontinuous LSFEM. The proof of the built-in a posteriori error estimation for the over-penalized scheme is presented as well. All results in this paper are robust with respect to the size of the domain guaranteed by a suitable weighting of the residuals in the least-squares functional. Numerical experiments exhibit optimal convergence rates of the adaptive mesh-refining algorithm for various polynomial degrees.
We study least-squares trace regression when the parameter is the sum of a $r$-low-rank and a $s$-sparse matrices and a fraction $\epsilon$ of the labels is corrupted. For subgaussian distributions, we highlight three design properties. The first, termed $\PP$, handles additive decomposition and follows from a product process inequality. The second, termed $\IP$, handles both label contamination and additive decomposition. It follows from Chevet's inequality. The third, termed $\MP$, handles the interaction between the design and featured-dependent noise. It follows from a multiplier process inequality. Jointly, these properties entail the near-optimality of a tractable estimator with respect to the effective dimensions $d_{\eff,r}$ and $d_{\eff,s}$ for the low-rank and sparse components, $\epsilon$ and the failure probability $\delta$. This rate has the form $$ \mathsf{r}(n,d_{\eff,r}) + \mathsf{r}(n,d_{\eff,s}) + \sqrt{(1+\log(1/\delta))/n} + \epsilon\log(1/\epsilon). $$ Here, $\mathsf{r}(n,d_{\eff,r})+\mathsf{r}(n,d_{\eff,s})$ is the optimal uncontaminated rate, independent of $\delta$. Our estimator is adaptive to $(s,r,\epsilon,\delta)$ and, for fixed absolute constant $c>0$, it attains the mentioned rate with probability $1-\delta$ uniformly over all $\delta\ge\exp(-cn)$. Disconsidering matrix decomposition, our analysis also entails optimal bounds for a robust estimator adapted to the noise variance. Finally, we consider robust matrix completion. We highlight a new property for this problem: one can robustly and optimally estimate the incomplete matrix regardless of the \emph{magnitude of the corruption}. Our estimators are based on ``sorted'' versions of Huber's loss. We present simulations matching the theory. In particular, it reveals the superiority of ``sorted'' Huber loss over the classical Huber's loss.
This work presents a comparative study to numerically compute impulse approximate controls for parabolic equations with various boundary conditions. Theoretical controllability results have been recently investigated using a logarithmic convexity estimate at a single time based on a Carleman commutator approach. We propose a numerical algorithm for computing the impulse controls with minimal $L^2$-norms by adapting a penalized Hilbert Uniqueness Method (HUM) combined with a Conjugate Gradient (CG) method. We consider static boundary conditions (Dirichlet and Neumann) and dynamic boundary conditions. Some numerical experiments based on our developed algorithm are given to validate and compare the theoretical impulse controllability results.
We introduce a convergent hierarchy of lower bounds on the minimum value of a real homogeneous polynomial over the sphere. The main practical advantage of our hierarchy over the sum-of-squares (SOS) hierarchy is that the lower bound at each level of our hierarchy is obtained by a minimum eigenvalue computation, as opposed to the full semidefinite program (SDP) required at each level of SOS. In practice, this allows us to go to much higher levels than are computationally feasible for the SOS hierarchy. For both hierarchies, the underlying space at the $k$-th level is the set of homogeneous polynomials of degree $2k$. We prove that our hierarchy converges as $O(1/k)$ in the level $k$, matching the best-known convergence of the SOS hierarchy when the number of variables $n$ is less than the half-degree $d$ (the best-known convergence of SOS when $n \geq d$ is $O(1/k^2)$). More generally, we introduce a convergent hierarchy of minimum eigenvalue computations for minimizing the inner product between a real tensor and an element of the spherical Segre-Veronese variety, with similar convergence guarantees. As examples, we obtain hierarchies for computing the (real) tensor spectral norm, and for minimizing biquadratic forms over the sphere. Hierarchies of eigencomputations for more general constrained polynomial optimization problems are discussed.
This work studies time-dependent electromagnetic scattering from obstacles whose interaction with the wave is fully determined by a nonlinear boundary condition. In particular, the boundary condition studied in this work enforces a power law type relation between the electric and magnetic field along the boundary. Based on time-dependent jump conditions of classical boundary operators, we derive a nonlinear system of time-dependent boundary integral equations that determines the tangential traces of the scattered electric and magnetic fields. These fields can subsequently be computed at arbitrary points in the exterior domain by evaluating a time-dependent representation formula. Fully discrete schemes are obtained by discretising the nonlinear system of boundary integral equations with Runge--Kutta based convolution quadrature in time and Raviart--Thomas boundary elements in space. Error bounds with explicitly stated convergence rates are proven, under the assumption of sufficient regularity of the exact solution. The error analysis is conducted through novel techniques based on time-discrete transmission problems and the use of a new discrete partial integration inequality. Numerical experiments illustrate the use of the proposed method and provide empirical convergence rates.