We provide effective methods to construct and manipulate trilinear birational maps $\phi:(\mathbb{P}^1)^3\dashrightarrow \mathbb{P}^3$ by establishing a novel connection between birationality and tensor rank. These yield four families of nonlinear birational transformations between 3D spaces that can be operated with enough flexibility for applications in computer-aided geometric design. More precisely, we describe the geometric constraints on the defining control points of the map that are necessary for birationality, and present constructions for such configurations. For adequately constrained control points, we prove that birationality is achieved if and only if a certain $2\times 2\times 2$ tensor has rank one. As a corollary, we prove that the locus of weights that ensure birationality is $\mathbb{P}^1\times\mathbb{P}^1\times\mathbb{P}^1$. Additionally, we provide formulas for the inverse $\phi^{-1}$ as well as the explicit defining equations of the irreducible components of the base loci. Finally, we introduce a notion of "distance to birationality" for trilinear rational maps, and explain how to continuously deform birational maps.
相關內容
In this work, we explore the dynamical sampling problem on $\ell^2(\mathbb{Z})$ driven by a convolution operator defined by a convolution kernel. This problem is inspired by the need to recover a bandlimited heat diffusion field from space-time samples and its discrete analogue. In this book chapter, we review recent results in the finite-dimensional case and extend these findings to the infinite-dimensional case, focusing on the study of the density of space-time sampling sets.
We study convergence rates of the Trotter-Kato splitting $e^{A+L} = \lim_{n \to \infty} (e^{L/n} e^{A/n})^n$ in the strong operator topology. In the first part, we use complex interpolation theory to treat generators $L$ and $A$ of contraction semigroups on Banach spaces, with $L$ relatively $A$-bounded. In the second part, we study unitary dynamics on Hilbert spaces and develop a new technique based on the concept of energy constraints. Our results provide a complete picture of the convergence rates for the Trotter splitting for all common types of Schr\"odinger and Dirac operators, including singular, confining and magnetic vector potentials, as well as molecular many-body Hamiltonians in dimension $d=3$. Using the Brezis-Mironescu inequality, we derive convergence rates for the Schr\"odinger operator with $V(x)=\pm |x|^{-a}$ potential. In each case, our conditions are fully explicit.
A $(1 \pm \epsilon)$-sparsifier of a hypergraph $G(V,E)$ is a (weighted) subgraph that preserves the value of every cut to within a $(1 \pm \epsilon)$-factor. It is known that every hypergraph with $n$ vertices admits a $(1 \pm \epsilon)$-sparsifier with $\tilde{O}(n/\epsilon^2)$ hyperedges. In this work, we explore the task of building such a sparsifier by using only linear measurements (a \emph{linear sketch}) over the hyperedges of $G$, and provide nearly-matching upper and lower bounds for this task. Specifically, we show that there is a randomized linear sketch of size $\widetilde{O}(n r \log(m) / \epsilon^2)$ bits which with high probability contains sufficient information to recover a $(1 \pm \epsilon)$ cut-sparsifier with $\tilde{O}(n/\epsilon^2)$ hyperedges for any hypergraph with at most $m$ edges each of which has arity bounded by $r$. This immediately gives a dynamic streaming algorithm for hypergraph cut sparsification with an identical space complexity, improving on the previous best known bound of $\widetilde{O}(n r^2 \log^4(m) / \epsilon^2)$ bits of space (Guha, McGregor, and Tench, PODS 2015). We complement our algorithmic result above with a nearly-matching lower bound. We show that for every $\epsilon \in (0,1)$, one needs $\Omega(nr \log(m/n) / \log(n))$ bits to construct a $(1 \pm \epsilon)$-sparsifier via linear sketching, thus showing that our linear sketch achieves an optimal dependence on both $r$ and $\log(m)$.
Wide stable neural networks: Sample regularity, functional convergence and Bayesian inverse problems
We study the large-width asymptotics of random fully connected neural networks with weights drawn from $\alpha$-stable distributions, a family of heavy-tailed distributions arising as the limiting distributions in the Gnedenko-Kolmogorov heavy-tailed central limit theorem. We show that in an arbitrary bounded Euclidean domain $\mathcal{U}$ with smooth boundary, the random field at the infinite-width limit, characterized in previous literature in terms of finite-dimensional distributions, has sample functions in the fractional Sobolev-Slobodeckij-type quasi-Banach function space $W^{s,p}(\mathcal{U})$ for integrability indices $p < \alpha$ and suitable smoothness indices $s$ depending on the activation function of the neural network, and establish the functional convergence of the processes in $\mathcal{P}(W^{s,p}(\mathcal{U}))$. This convergence result is leveraged in the study of functional posteriors for edge-preserving Bayesian inverse problems with stable neural network priors.
Anderson acceleration (AA) is widely used for accelerating the convergence of an underlying fixed-point iteration $\bm{x}_{k+1} = \bm{q}( \bm{x}_{k} )$, $k = 0, 1, \ldots$, with $\bm{x}_k \in \mathbb{R}^n$, $\bm{q} \colon \mathbb{R}^n \to \mathbb{R}^n$. Despite AA's widespread use, relatively little is understood theoretically about the extent to which it may accelerate the underlying fixed-point iteration. To this end, we analyze a restarted variant of AA with a restart size of one, a method closely related to GMRES(1). We consider the case of $\bm{q}( \bm{x} ) = M \bm{x} + \bm{b}$ with matrix $M \in \mathbb{R}^{n \times n}$ either symmetric or skew-symmetric. For both classes of $M$ we compute the worst-case root-average asymptotic convergence factor of the AA method, partially relying on conjecture in the symmetric setting, proving that it is strictly smaller than that of the underlying fixed-point iteration. For symmetric $M$, we show that the AA residual iteration corresponds to a fixed-point iteration for solving an eigenvector-dependent nonlinear eigenvalue problem (NEPv), and we show how this can result in the convergence factor strongly depending on the initial iterate, which we quantify exactly in certain special cases. Conversely, for skew-symmetric $M$ we show that the AA residual iteration is closely related to a power iteration for $M$, and how this results in the convergence factor being independent of the initial iterate. Supporting numerical results are given, which also indicate the theory is applicable to the more general setting of nonlinear $\bm{q}$ with Jacobian at the fixed point that is symmetric or skew symmetric.
We present an $\ell^2_2+\ell_1$-regularized discrete least squares approximation over general regions under assumptions of hyperinterpolation, named hybrid hyperinterpolation. Hybrid hyperinterpolation, using a soft thresholding operator and a filter function to shrink the Fourier coefficients approximated by a high-order quadrature rule of a given continuous function with respect to some orthonormal basis, is a combination of Lasso and filtered hyperinterpolations. Hybrid hyperinterpolation inherits features of them to deal with noisy data once the regularization parameter and the filter function are chosen well. We derive $L_2$ errors in theoretical analysis for hybrid hyperinterpolation to approximate continuous functions with noise data on sampling points. Numerical examples illustrate the theoretical results and show that well chosen regularization parameters can enhance the approximation quality over the unit-sphere and the union of disks.
The {\em discrepancy} of a matrix $M \in \mathbb{R}^{d \times n}$ is given by $\mathrm{DISC}(M) := \min_{\boldsymbol{x} \in \{-1,1\}^n} \|M\boldsymbol{x}\|_\infty$. An outstanding conjecture, attributed to Koml\'os, stipulates that $\mathrm{DISC}(M) = O(1)$, whenever $M$ is a Koml\'os matrix, that is, whenever every column of $M$ lies within the unit sphere. Our main result asserts that $\mathrm{DISC}(M + R/\sqrt{d}) = O(d^{-1/2})$ holds asymptotically almost surely, whenever $M \in \mathbb{R}^{d \times n}$ is Koml\'os, $R \in \mathbb{R}^{d \times n}$ is a Rademacher random matrix, $d = \omega(1)$, and $n = \omega(d \log d)$. The factor $d^{-1/2}$ normalising $R$ is essentially best possible and the dependency between $n$ and $d$ is asymptotically best possible. Our main source of inspiration is a result by Bansal, Jiang, Meka, Singla, and Sinha (ICALP 2022). They obtained an assertion similar to the one above in the case that the smoothing matrix is Gaussian. They asked whether their result can be attained with the optimal dependency $n = \omega(d \log d)$ in the case of Bernoulli random noise or any other types of discretely distributed noise; the latter types being more conducive for Smoothed Analysis in other discrepancy settings such as the Beck-Fiala problem. For Bernoulli noise, their method works if $n = \omega(d^2)$. In the case of Rademacher noise, we answer the question posed by Bansal, Jiang, Meka, Singla, and Sinha. Our proof builds upon their approach in a strong way and provides a discrete version of the latter. Breaking the $n = \omega(d^2)$ barrier and reaching the optimal dependency $n = \omega(d \log d)$ for Rademacher noise requires additional ideas expressed through a rather meticulous counting argument, incurred by the need to maintain a high level of precision all throughout the discretisation process.
Brown and Walker (1997) showed that GMRES determines a least squares solution of $ A x = b $ where $ A \in {\bf R}^{n \times n} $ without breakdown for arbitrary $ b, x_0 \in {\bf R}^n $ if and only if $A$ is range-symmetric, i.e. $ {\cal R} (A^{\rm T}) = {\cal R} (A) $, where $ A $ may be singular and $ b $ may not be in the range space ${\cal R} A)$ of $A$. In this paper, we propose applying GMRES to $ A C A^{\rm T} z = b $, where $ C \in {\bf R}^{n \times n} $ is symmetric positive definite. This determines a least squares solution $ x = CA^{\rm T} z $ of $ A x = b $ without breakdown for arbitrary (singular) matrix $A \in {\bf R}^{n \times n}$ and $ b \in {\bf R}^n $. To make the method numerically stable, we propose using the pseudoinverse with an appropriate threshold parameter to suppress the influence of tiny singular values when solving the severely ill-conditioned Hessenberg systems which arise in the Arnoldi process of GMRES when solving inconsistent range-symmetric systems. Numerical experiments show that the method taking $C$ to be the identity matrix and the inverse matrix of the diagonal matrix whose diagonal elements are the diagonal of $A A^{\rm T}$ gives a least squares solution even when $A$ is not range-symmetric, including the case when $ {\rm index}(A) >1$.
Determining the complexity of computing Gr\"{o}bner bases is an important problem both in theory and in practice, and for that the solving degree plays a key role. In this paper, we study the solving degrees of affine semi-regular sequences and their homogenized sequences. Some of our results are considered to give mathematically rigorous proofs of the correctness of methods for computing Gr\"{o}bner bases of the ideal generated by an affine semi-regular sequence. This paper is a sequel of the authors' previous work and gives additional results on the solving degrees and important behaviors of Gr\"obner basis computation. We also define the generalized degree of regularity for a sequence of homogeneous polynomials. For the homogenization of an affine semi-regular sequence, we relate its generalized degree of regularity with its maximal Gr\"{o}bner basis degree (i.e., the solving degree of the homogenized sequence). The definition of a generalized (cryptographic) semi-regular sequence is also given, and it derives a new cryptographic assumption to estimate the security of cryptosystems and signature schemes. From our experimental observation, we raise a conjecture and some questions related to this generalized semi-regularity. These new definitions and our results provide a theoretical formulation of (somehow heuristic) discussions done so far in the cryptographic community.
We consider the problem of enumerating all minimal transversals (also called minimal hitting sets) of a hypergraph $\mathcal{H}$. An equivalent formulation of this problem known as the \emph{transversal hypergraph} problem (or \emph{hypergraph dualization} problem) is to decide, given two hypergraphs, whether one corresponds to the set of minimal transversals of the other. The existence of a polynomial time algorithm to solve this problem is a long standing open question. In \cite{fredman_complexity_1996}, the authors present the first sub-exponential algorithm to solve the transversal hypergraph problem which runs in quasi-polynomial time, making it unlikely that the problem is (co)NP-complete. In this paper, we show that when one of the two hypergraphs is of bounded VC-dimension, the transversal hypergraph problem can be solved in polynomial time, or equivalently that if $\mathcal{H}$ is a hypergraph of bounded VC-dimension, then there exists an incremental polynomial time algorithm to enumerate its minimal transversals. This result generalizes most of the previously known polynomial cases in the literature since they almost all consider classes of hypergraphs of bounded VC-dimension. As a consequence, the hypergraph transversal problem is solvable in polynomial time for any class of hypergraphs closed under partial subhypergraphs. We also show that the proposed algorithm runs in quasi-polynomial time in general hypergraphs and runs in polynomial time if the conformality of the hypergraph is bounded, which is one of the few known polynomial cases where the VC-dimension is unbounded.
小貼士
登錄享
相關主題
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191