Search

Graph matching aims at finding the vertex correspondence between two unlabeled graphs that maximizes the total edge weight correlation. This amounts to solving a computationally intractable quadratic assignment problem. In this paper, we propose a new spectral method, graph matching by pairwise eigen-alignments (GRAMPA). Departing from prior spectral approaches that only compare top eigenvectors, or eigenvectors of the same order, GRAMPA first constructs a similarity matrix as a weighted sum of outer products between all pairs of eigenvectors of the two graphs, with weights given by a Cauchy kernel applied to the separation of the corresponding eigenvalues, then outputs a matching by a simple rounding procedure. The similarity matrix can also be interpreted as the solution to a regularized quadratic programming relaxation of the quadratic assignment problem. For the Gaussian Wigner model in which two complete graphs on n vertices have Gaussian edge weights with correlation coefficient [Formula omitted], we show that GRAMPA exactly recovers the correct vertex correspondence with high probability when [Formula omitted]. This matches the state of the art of polynomial-time algorithms and significantly improves over existing spectral methods which require [Formula omitted] to be polynomially small in n. The superiority of GRAMPA is also demonstrated on a variety of synthetic and real datasets, in terms of both statistical accuracy and computational efficiency. Universality results, including similar guarantees for dense and sparse Erdos-Rényi graphs, are deferred to a companion paper., Author(s): Zhou Fan [sup.1], Cheng Mao [sup.2], Yihong Wu [sup.1], Jiaming Xu [sup.3] Author Affiliations: (1) https://ror.org/03v76x132, grid.47100.32, 0000 0004 1936 8710, Department of Statistics and Data Science, Yale University, [...]

Recently, there has been a great interest in analysing dynamical flows, where the stationary limit is the minimiser of a convex energy. Particular flows of great interest have been continuous limits of Nesterov's algorithm and the fast iterative shrinkage-thresholding algorithm, respectively. In this paper, we approach the solutions of linear ill-posed problems by dynamical flows. Because the squared norm of the residual of a linear operator equation is a convex functional, the theoretical results from convex analysis for energy minimising flows are applicable. However, in the restricted situation of this paper they can often be significantly improved. Moreover, since we show that the proposed flows for minimising the norm of the residual of a linear operator equation are optimal regularisation methods and that they provide optimal convergence rates for the regularised solutions, the given rates can be considered the benchmarks for further studies in convex analysis., Author(s): Radu Bot [sup.1], Guozhi Dong [sup.2] [sup.3], Peter Elbau [sup.1], Otmar Scherzer [sup.1] [sup.4] Author Affiliations: (1) grid.10420.37, 0000 0001 2286 1424, Faculty of Mathematics, University of Vienna, , [...]

This paper presents a methodology to study non-twist invariant circles and their bifurcations for area preserving maps, which is supported on the theoretical framework developed in Gonzalez-Enriquez et al. (Mem. Amer. Math. Soc. 227:vi+115, 2014). We recall that non-twist invariant circles are characterized not only by being invariant, but also by having some specified normal behavior. The normal behavior may endow them with extra stability properties (e.g., against external noise), and hence, they appear as design goals in some applications, e.g., in plasma physics, astrodynamics and oceanography. The methodology leads to efficient algorithms to compute and continue, with respect to parameters, non-twist invariant circles. The algorithms are quadratically convergent and, when implemented using FFT, have low storage requirement and low operations count per step. Furthermore, the algorithms are backed up by rigorous a posteriori theorems, proved and discussed in detail in Gonzalez-Enriquez et al. (Mem. Amer. Math. Soc. 227:vi+115, 2014), which give sufficient conditions guaranteeing the existence of a true non-twist invariant circle, provided an approximate invariant circle is known. Hence, one can compute confidently even very close to breakdown. With some extra effort, the calculations could be turned into computer-assisted proofs, see Figueras et al. (Found. Comput. Math. 17:1123-1193, 2017) for examples of the latter. The algorithms are also guaranteed to converge up to the breakdown of the invariant circles, and then, they are suitable to compute regions of parameters where the non-twist invariant circles exist. The calculations involved in the computation of the boundary of these regions are very robust, and they do not require symmetries and can run without continuous manual adjustments, largely improving methods based on the computation of very long period periodic orbits to approximate invariant circles. This paper contains a detailed description of our algorithms, the corresponding implementation and some numerical results, obtained by running the computer programs. In particular, we include calculations for two-dimensional parameter regions where non-twist invariant circles (with a prescribed frequency) exist. Indeed, we present systematic results in systems that do not contain symmetry lines, which seem to be unaccessible for previous methods. These numerical explorations lead to some open questions, also included here., Author(s): Alejandra González [sup.1], Àlex Haro [sup.2], Rafael de la Llave [sup.3] Author Affiliations: (1) Foundations of Learning, Zurich, , Schwäntenmos 4, 8126, Zumikon, Switzerland (2) grid.5841.8, 0000 0004 1937 [...]

This paper is concerned with the theory and applications of varifolds to the representation, approximation and diffeomorphic registration of shapes. One of its purpose is to synthesize and extend several prior works which, so far, have made use of this framework mainly in the context of submanifold comparison and matching. In this work, we instead consider deformation models acting on general varifold spaces, which allow to formulate and tackle diffeomorphic registration problems for a much wider class of geometric objects and lead to a more versatile algorithmic pipeline. We study in detail the construction of kernel metrics on varifold spaces and the resulting topological properties of those metrics and then propose a mathematical model for diffeomorphic registration of varifolds under a specific group action which we formulate in the framework of optimal control theory. A second important part of the paper focuses on the discrete aspects. Specifically, we address the problem of optimal finite approximations (quantization) for those metrics and show a [Formula omitted]-convergence property for the corresponding registration functionals. Finally, we develop numerical pipelines for quantization and registration before showing a few preliminary results for one- and two-dimensional varifolds., Author(s): Hsi-Wei Hsieh [sup.1] , Nicolas Charon [sup.1] Author Affiliations: (1) grid.21107.35, 0000 0001 2171 9311, Department of Applied Mathematics and Statistics, Johns Hopkins University, , Clark Hall, Rm 320A, [...]

This paper studies the problem of deterministic rank-one matrix completion. It is known that the simplest semidefinite programming relaxation, involving minimization of the nuclear norm, does not in general return the solution for this problem. In this paper, we show that in every instance where the problem has a unique solution, one can provably recover the original matrix through the level 2 Lasserre relaxation with minimization of the trace norm. We further show that the solution of the proposed semidefinite program is Lipschitz stable with respect to perturbations of the observed entries, unlike more basic algorithms such as nonlinear propagation or ridge regression. Our proof is based on recursively building a certificate of optimality corresponding to a dual sum-of-squares (SoS) polynomial. This SoS polynomial is built from the polynomial ideal generated by the completion constraints and the monomials provided by the minimization of the trace. The proposed relaxation fits in the framework of the Lasserre hierarchy, albeit with the key addition of the trace objective function. Finally, we show how to represent and manipulate the moment tensor in favorable complexity by means of a hierarchical low-rank factorization., Author(s): Augustin Cosse [sup.1] [sup.2] , Laurent Demanet [sup.3] Author Affiliations: (1) grid.5607.4, 0000000121105547, Département de Mathématiques et Applications, Ecole Normale Supérieure, , Ulm, Paris, France (2) grid.440907.e, 0000 0004 [...]

Motivated by cutting-edge applications like cryo-electron microscopy (cryo-EM), the Multi-Reference Alignment (MRA) model entails the learning of an unknown signal from repeated measurements of its images under the latent action of a group of isometries and additive noise of magnitude [Formula omitted]. Despite significant interest, a clear picture for understanding rates of estimation in this model has emerged only recently, particularly in the high-noise regime [Formula omitted] that is highly relevant in applications. Recent investigations have revealed a remarkable asymptotic sample complexity of order [Formula omitted] for certain signals whose Fourier transforms have full support, in stark contrast to the traditional [Formula omitted] that arise in regular models. Often prohibitively large in practice, these results have prompted the investigation of variations around the MRA model where better sample complexity may be achieved. In this paper, we show that sparse signals exhibit an intermediate [Formula omitted] sample complexity even in the classical MRA model. Further, we characterize the dependence of the estimation rate on the support size s as [Formula omitted] and [Formula omitted] in the dilute and moderate regimes of sparsity respectively. Our techniques have implications for the problem of crystallographic phase retrieval, indicating a certain local uniqueness for the recovery of sparse signals from their power spectrum. Our results explore and exploit connections of the MRA estimation problem with two classical topics in applied mathematics: the beltway problem from combinatorial optimization, and uniform uncertainty principles from harmonic analysis. Our techniques include a certain enhanced form of the probabilistic method, which might be of general interest in its own right., Author(s): Subhroshekhar Ghosh [sup.1] , Philippe Rigollet [sup.2] Author Affiliations: (1) https://ror.org/01tgyzw49, grid.4280.e, 0000 0001 2180 6431, Department of Mathematics, National University of Singapore, , 10 Lower Kent Ridge Road, [...]

We study the matrix completion problem: an underlying [Formula omitted] matrix P is low rank, with incoherent singular vectors, and a random [Formula omitted] matrix A is equal to P on a (uniformly) random subset of entries of size dn. All other entries of A are equal to zero. The goal is to retrieve information on P from the observation of A. Let [Formula omitted] be the random matrix where each entry of A is multiplied by an independent [Formula omitted]-Bernoulli random variable with parameter 1/2. This paper is about when, how and why the non-Hermitian eigen-spectra of the matrices [Formula omitted] and [Formula omitted] captures more of the relevant information about the principal component structure of A than the eigen-spectra of [Formula omitted] and [Formula omitted]. We show that the eigenvalues of the asymmetric matrices [Formula omitted] and [Formula omitted] with modulus greater than a detection threshold are asymptotically equal to the eigenvalues of [Formula omitted] and [Formula omitted] and that the associated eigenvectors are aligned as well. The central surprise is that by intentionally inducing asymmetry and additional randomness via the [Formula omitted] matrix, we can extract more information than if we had worked with the singular value decomposition (SVD) of A. The associated detection threshold is asymptotically exact and is non-universal since it explicitly depends on the element-wise distribution of the underlying matrix P. We show that reliable, statistically optimal but not perfect matrix recovery, via a universal data-driven algorithm, is possible above this detection threshold using the information extracted from the asymmetric eigen-decompositions. Averaging the left and right eigenvectors provably improves estimation accuracy but not the detection threshold. Our results encompass the very sparse regime where d is of order 1 where matrix completion via the SVD of A fails or produces unreliable recovery. We define another variant of this asymmetric principal component analysis procedure that bypasses the randomization step and has a detection threshold that is smaller by a constant factor but with a computational cost that is larger by a polynomial factor of the number of observed entries. Both detection thresholds allow to go beyond the barrier due to the well-known information theoretical limit [Formula omitted] for exact matrix completion found in the literature., Author(s): Charles Bordenave [sup.1] , Simon Coste [sup.2] , Raj Rao Nadakuditi [sup.3] Author Affiliations: (1) grid.5399.6, 0000 0001 2176 4817, Institut de mathématiques de Marseille, Aix-Marseille Université, , 39 [...]

We analyze a new spectral graph matching algorithm, GRAph Matching by Pairwise eigen-Alignments (GRAMPA), for recovering the latent vertex correspondence between two unlabeled, edge-correlated weighted graphs. Extending the exact recovery guarantees established in a companion paper for Gaussian weights, in this work, we prove the universality of these guarantees for a general correlated Wigner model. In particular, for two Erdos-Rényi graphs with edge correlation coefficient [Formula omitted] and average degree at least [Formula omitted], we show that GRAMPA exactly recovers the latent vertex correspondence with high probability when [Formula omitted]. Moreover, we establish a similar guarantee for a variant of GRAMPA, corresponding to a tighter quadratic programming relaxation of the quadratic assignment problem. Our analysis exploits a resolvent representation of the GRAMPA similarity matrix and local laws for the resolvents of sparse Wigner matrices., Author(s): Zhou Fan [sup.1], Cheng Mao [sup.2], Yihong Wu [sup.1], Jiaming Xu [sup.3] Author Affiliations: (1) https://ror.org/03v76x132, grid.47100.32, 0000 0004 1936 8710, Department of Statistics and Data Science, Yale University, [...]

In this paper, we present a deterministic polynomial time algorithm for testing whether a symbolic matrix in non-commuting variables over [Formula omitted] is invertible or not. The analogous question for commuting variables is the celebrated polynomial identity testing (PIT) for symbolic determinants. In contrast to the commutative case, which has an efficient probabilistic algorithm, the best previous algorithm for the non-commutative setting required exponential time (Ivanyos et al. in Comput Complex 26(3):717-763, 2017 (See CR51)) (whether or not randomization is allowed). The algorithm efficiently solves the 'word problem' for the free skew field, and the identity testing problem for arithmetic formulae with division over non-commuting variables, two problems which had only exponential time algorithms prior to this work. The main contribution of this paper is a complexity analysis of an existing algorithm due to Gurvits (J Comput Syst Sci 69(3):448-484, 2004 (See CR37)), who proved it was polynomial time for certain classes of inputs. We prove it always runs in polynomial time. The main component of our analysis is a simple (given the necessary known tools) lower bound on central notion of capacity of operators (introduced by Gurvits 2004 (See CR37)). We extend the algorithm to actually approximate capacity to any accuracy in polynomial time, and use this analysis to give quantitative bounds on the continuity of capacity (the latter is used in a subsequent paper on Brascamp-Lieb inequalities). We also extend the algorithm to compute not only singularity, but actually the (non-commutative) rank of a symbolic matrix, yielding a factor 2 approximation of the commutative rank. This naturally raises a relaxation of the commutative PIT problem to achieving better deterministic approximation of the commutative rank. Symbolic matrices in non-commuting variables, and the related structural and algorithmic questions, have a remarkable number of diverse origins and motivations. They arise independently in (commutative) invariant theory and representation theory, linear algebra, optimization, linear system theory, quantum information theory, approximation of the permanent and naturally in non-commutative algebra. We provide a detailed account of some of these sources and their interconnections. In particular, we explain how some of these sources played an important role in the development of Gurvits' algorithm and in our analysis of it here., Author(s): Ankit Garg [sup.1] , Leonid Gurvits [sup.2] , Rafael Oliveira [sup.3] , Avi Wigderson [sup.4] Author Affiliations: (1) grid.466948.1, Microsoft Research India, , Bengaluru, India (2) grid.254250.4, 0000 0001 [...]

The persistence diagram is an increasingly useful tool from Topological Data Analysis, but its use alongside typical machine learning techniques requires mathematical finesse. The most success to date has come from methods that map persistence diagrams into vector spaces, in a way which maximizes the structure preserved. This process is commonly referred to as featurization. In this paper, we describe a mathematical framework for featurization called template functions, and we show that it addresses the problem of approximating continuous functions on compact subsets of the space of persistence diagrams. Specifically, we begin by characterizing relative compactness with respect to the bottleneck distance, and then provide explicit theoretical methods for constructing compact-open dense subsets of continuous functions on persistence diagrams. These dense subsets-obtained via template functions-are leveraged for supervised learning tasks with persistence diagrams. Specifically, we test the method for classification and regression algorithms on several examples including shape data and dynamical systems., Author(s): Jose A. Perea [sup.1], Elizabeth Munch [sup.2], Firas A. Khasawneh [sup.3] Author Affiliations: (1) grid.261112.7, 0000 0001 2173 3359, Department of Mathematics and Khoury College of Computer Sciences, Northeastern [...]

Recent advances in quantized compressed sensing and high-dimensional estimation have shown that signal recovery is even feasible under strong nonlinear distortions in the observation process. An important characteristic of associated guarantees is uniformity, i.e., recovery succeeds for an entire class of structured signals with a fixed measurement ensemble. However, despite significant results in various special cases, a general understanding of uniform recovery from nonlinear observations is still missing. This paper develops a unified approach to this problem under the assumption of i.i.d. sub-Gaussian measurement vectors. Our main result shows that a simple least-squares estimator with any convex constraint can serve as a universal recovery strategy, which is outlier robust and does not require explicit knowledge of the underlying nonlinearity. Based on empirical process theory, a key technical novelty is an approximative increment condition that can be implemented for all common types of nonlinear models. This flexibility allows us to apply our approach to a variety of problems in nonlinear compressed sensing and high-dimensional statistics, leading to several new and improved guarantees. Each of these applications is accompanied by a conceptually simple and systematic proof, which does not rely on any deeper properties of the observation model. On the other hand, known local stability properties can be incorporated into our framework in a plug-and-play manner, thereby implying near-optimal error bounds., Author(s): Martin Genzel [sup.1] , Alexander Stollenwerk [sup.2] Author Affiliations: (1) grid.5477.1, 0000000120346234, Utrecht University, Mathematical Institute, , Budapestlaan 6, 3584, Utrecht, CD, Netherlands (2) grid.7942.8, 0000 0001 2294 713X, [...]

In this paper, we explore orthogonal systems in [Formula omitted] which give rise to a real skew-symmetric, tridiagonal, irreducible differentiation matrix. Such systems are important since they are stable by design and, if necessary, preserve Euclidean energy for a variety of time-dependent partial differential equations. We prove that there is a one-to-one correspondence between such an orthonormal system [Formula omitted] and a sequence of polynomials [Formula omitted] orthonormal with respect to a symmetric probability measure [Formula omitted]. If [Formula omitted] is supported by the real line, this system is dense in [Formula omitted]; otherwise, it is dense in a Paley-Wiener space of band-limited functions. The path leading from [Formula omitted] to [Formula omitted] is constructive, and we provide detailed algorithms to this end. We also prove that the only such orthogonal system consisting of a polynomial sequence multiplied by a weight function is the Hermite functions. The paper is accompanied by a number of examples illustrating our argument., Author(s): Arieh Iserles [sup.1] , Marcus Webb [sup.2] Author Affiliations: (1) grid.5335.0, 0000000121885934, Department of Applied Mathematics and Theoretical Physics Centre for Mathematical Sciences, University of Cambridge, , Wilberforce Road, [...]

In this paper we consider filtering and smoothing of partially observed chaotic dynamical systems that are discretely observed, with an additive Gaussian noise in the observation. These models are found in a wide variety of real applications and include the Lorenz 96' model. In the context of a fixed observation interval T, observation time step h and Gaussian observation variance [Formula omitted], we show under assumptions that the filter and smoother are well approximated by a Gaussian with high probability when h and [Formula omitted] are sufficiently small. Based on this result we show that the maximum a posteriori (MAP) estimators are asymptotically optimal in mean square error as [Formula omitted] tends to 0. Given these results, we provide a batch algorithm for the smoother and filter, based on Newton's method, to obtain the MAP. In particular, we show that if the initial point is close enough to the MAP, then Newton's method converges to it at a fast rate. We also provide a method for computing such an initial point. These results contribute to the theoretical understanding of widely used 4D-Var data assimilation method. Our approach is illustrated numerically on the Lorenz 96' model with state vector up to 1 million dimensions, with code running in the order of minutes. To our knowledge the results in this paper are the first of their type for this class of models., Author(s): Daniel Paulin [sup.1] [sup.2] , Ajay Jasra [sup.1] , Dan Crisan [sup.3] , Alexandros Beskos [sup.4] Author Affiliations: (Aff1) 0000 0001 2180 6431, grid.4280.e, Department of Statistics and Applied [...]

This paper provides an explicit polynomial rate of asymptotic regularity for (in general inconsistent) feasibility problems in Hilbert space. In particular, we give a quantitative version of Bauschke's solution of the zero displacement problem as well as of various generalizations of this problem. The results in this paper have been obtained by applying a general proof-theoretic method for the extraction of effective bounds from proofs due to the author ('proof mining') to Bauschke's proof., Author(s): Ulrich Kohlenbach [sup.1] Author Affiliations: (Aff1) 0000 0001 0940 1669, grid.6546.1, Department of Mathematics, Technische Universität Darmstadt, , Schlossgartenstraße 7, 64289, Darmstadt, Germany Introduction In a remarkable paper [3], [...]

In this paper, we describe in detail a model of geometric-functional variability between fshapes. These objects were introduced for the first time by Charlier et al. (J Found Comput Math, 2015 (See CR15). http://arxiv.org/abs/1404.6039 http://arxiv.org/abs/1404.6039 ) and are basically the combination of classical deformable manifolds with additional scalar signal map. Building on the aforementioned work, this paper's contributions are several. We first extend the original [Formula omitted] model in order to represent signals of higher regularity on their geometrical support with more regular Hilbert norms (typically Sobolev). We describe the bundle structure of such fshape spaces with their adequate geodesic distances, encompassing in one common framework usual shape comparison and image metamorphoses. We then propose a formulation of matching between any two fshapes from the optimal control perspective, study existence of optimal controls and derive Hamiltonian equations and conservation laws describing the dynamics of geodesics. Secondly, we tackle the discrete counterpart of these problems and equations through appropriate finite elements interpolation schemes on triangular meshes. At last, we show a few results of metamorphosis matchings on several synthetic and real data examples in order to highlight the key specificities of the approach., Author(s): N. Charon [sup.1] , B. Charlier [sup.2] , A. Trouvé [sup.3] Author Affiliations: (Aff1) 0000 0001 2171 9311, grid.21107.35, CIS, Johns Hopkins University, , Baltimore, MD, USA (Aff2) 0000 [...]

Hermite interpolation property is desired in applied and computational mathematics. Hermite and vector subdivision schemes are of interest in CAGD for generating subdivision curves and in computational mathematics for building Hermite wavelets to numerically solve partial differential equations. In contrast to well-studied scalar subdivision schemes, Hermite and vector subdivision schemes employ matrix-valued masks and vector input data, which make their analysis much more complicated and difficult than their scalar counterparts. Under the spectral condition or the spectral chain, analysis of Hermite subdivision schemes through factorization of matrix-valued masks has been extensively studied in the literature and sufficient conditions have been given for the convergence of Hermite subdivision schemes through the contractivity of their derived subdivision schemes. We contribute to the study of Hermite subdivision schemes from a different perspective by investigating vector subdivision operators acting on vector polynomials and by establishing connections among Hermite subdivision schemes, vector cascade algorithms, and refinable vector functions. This approach allows us to characterize and construct all masks for Hermite subdivision schemes, to explain the spectral condition and spectral chain in the literature, to characterize convergence and smoothness of Hermite subdivision schemes using vector cascade algorithms, and to provide simple factorizations of Hermite masks through the normal form of matrix-valued masks such that the Hermite subdivision scheme is convergent if and only if its derived subdivision scheme is contractive. We also constructively prove that there always exist arbitrarily smooth convergent Hermite subdivision schemes, whose basis vector functions are splines and have linearly independent shifts. Several examples of Hermite subdivision schemes with short support and high smoothness are presented to illustrate the results in this paper., Author(s): Bin Han [sup.1] Author Affiliations: (1) grid.17089.37, 0000 0001 2190 316X, Department of Mathematical and Statistical Sciences, University of Alberta, , T6G 2G1, Edmonton, AB, Canada Introduction, Motivations, and [...]

In this paper, we present a novel arbitrary-order discrete de Rham (DDR) complex on general polyhedral meshes based on the decomposition of polynomial spaces into ranges of vector calculus operators and complements linked to the spaces in the Koszul complex. The DDR complex is fully discrete, meaning that both the spaces and discrete calculus operators are replaced by discrete counterparts, and satisfies suitable exactness properties depending on the topology of the domain. In conjunction with bespoke discrete counterparts of [Formula omitted]-products, it can be used to design schemes for partial differential equations that benefit from the exactness of the sequence but, unlike classical (e.g., Raviart-Thomas-Nédélec) finite elements, are nonconforming. We prove a complete panel of results for the analysis of such schemes: exactness properties, uniform Poincaré inequalities, as well as primal and adjoint consistency. We also show how this DDR complex enables the design of a numerical scheme for a magnetostatics problem, and use the aforementioned results to prove stability and optimal error estimates for this scheme., Author(s): Daniele A. Di Pietro [sup.1], Jérôme Droniou [sup.2] Author Affiliations: (1) grid.121334.6, 0000 0001 2097 0141, IMAG, Univ Montpellier, CNRS, , Montpellier, France (2) grid.1002.3, 0000 0004 1936 7857, [...]

Rate distortion theory is concerned with optimally encoding signals from a given signal class [Formula omitted] using a budget of R bits, as [Formula omitted]. We say that [Formula omitted]can be compressed at rates if we can achieve an error of at most [Formula omitted] for encoding the given signal class; the supremal compression rate is denoted by [Formula omitted]. Given a fixed coding scheme, there usually are some elements of [Formula omitted] that are compressed at a higher rate than [Formula omitted] by the given coding scheme; in this paper, we study the size of this set of signals. We show that for certain 'nice' signal classes [Formula omitted], a phase transition occurs: We construct a probability measure [Formula omitted] on [Formula omitted] such that for every coding scheme [Formula omitted] and any [Formula omitted], the set of signals encoded with error [Formula omitted] by [Formula omitted] forms a [Formula omitted]-null-set. In particular, our results apply to all unit balls in Besov and Sobolev spaces that embed compactly into [Formula omitted] for a bounded Lipschitz domain [Formula omitted]. As an application, we show that several existing sharpness results concerning function approximation using deep neural networks are in fact generically sharp. In addition, we provide quantitative and non-asymptotic bounds on the probability that a random [Formula omitted] can be encoded to within accuracy [Formula omitted] using R bits. This result is subsequently applied to the problem of approximately representing [Formula omitted] to within accuracy [Formula omitted] by a (quantized) neural network with at most W nonzero weights. We show that for any [Formula omitted] there are constants c, C such that, no matter what kind of 'learning' procedure is used to produce such a network, the probability of success is bounded from above by [Formula omitted]., Author(s): Philipp Grohs [sup.1] [sup.2], Andreas Klotz [sup.1], Felix Voigtlaender [sup.3] [sup.4] Author Affiliations: (1) grid.10420.37, 0000 0001 2286 1424, Faculty of Mathematics, University of Vienna, , Oskar-Morgenstern-Platz 1, 1090, [...]

Characterising intractable high-dimensional random variables is one of the fundamental challenges in stochastic computation. The recent surge of transport maps offers a mathematical foundation and new insights for tackling this challenge by coupling intractable random variables with tractable reference random variables. This paper generalises the functional tensor-train approximation of the inverse Rosenblatt transport recently developed by Dolgov et al. (Stat Comput 30:603-625, 2020) to a wide class of high-dimensional non-negative functions, such as unnormalised probability density functions. First, we extend the inverse Rosenblatt transform to enable the transport to general reference measures other than the uniform measure. We develop an efficient procedure to compute this transport from a squared tensor-train decomposition which preserves the monotonicity. More crucially, we integrate the proposed order-preserving functional tensor-train transport into a nested variable transformation framework inspired by the layered structure of deep neural networks. The resulting deep inverse Rosenblatt transport significantly expands the capability of tensor approximations and transport maps to random variables with complicated nonlinear interactions and concentrated density functions. We demonstrate the efficiency of the proposed approach on a range of applications in statistical learning and uncertainty quantification, including parameter estimation for dynamical systems and inverse problems constrained by partial differential equations., Author(s): Tiangang Cui [sup.1], Sergey Dolgov [sup.2] Author Affiliations: (1) grid.1002.3, 0000 0004 1936 7857, School of Mathematics, , 3800, Monash University, VIC, Australia (2) grid.7340.0, 0000 0001 2162 1699, [...]

In this paper we initiate the study of tropical Voronoi diagrams. We start out with investigating bisectors of finitely many points with respect to arbitrary polyhedral norms. For this more general scenario we show that bisectors of three points are homeomorphic to a non-empty open subset of Euclidean space, provided that certain degenerate cases are excluded. Specializing our results to tropical bisectors then yields structural results and algorithms for tropical Voronoi diagrams., Author(s): Francisco Criado [sup.1], Michael Joswig [sup.1] [sup.2], Francisco Santos [sup.3] Author Affiliations: (1) grid.6734.6, 0000 0001 2292 8254, TU Berlin, Chair of Discrete Mathematics/Geometry, , Berlin, Germany (2) grid.419532.8, [...]

This paper develops nonasymptotic growth and concentration bounds for a product of independent random matrices. These results sharpen and generalize recent work of Henriksen-Ward, and they are similar in spirit to the results of Ahlswede-Winter and of Tropp for a sum of independent random matrices. The argument relies on the uniform smoothness properties of the Schatten trace classes., Author(s): De Huang [sup.1] , Jonathan Niles-Weed [sup.2] , Joel A. Tropp [sup.1] , Rachel Ward [sup.3] Author Affiliations: (1) grid.20861.3d, 0000000107068890, Department of Computing and Mathematical Sciences, California Institute [...]

In this paper, we address the problem of constructing [Formula omitted] cubic spline functions on a given arbitrary triangulation [Formula omitted]. To this end, we endow every triangle of [Formula omitted] with a Wang-Shi macro-structure. The [Formula omitted] cubic space on such a refined triangulation has a stable dimension and optimal approximation power. Moreover, any spline function in this space can be locally built on each of the macro-triangles independently via Hermite interpolation. We provide a simplex spline basis for the space of [Formula omitted] cubics defined on a single macro-triangle which behaves like a Bernstein/B-spline basis over the triangle. The basis functions inherit recurrence relations and differentiation formulas from the simplex spline construction, they form a nonnegative partition of unity, they admit simple conditions for [Formula omitted] joins across the edges of neighboring triangles, and they enjoy a Marsden-like identity. Also, there is a single control net to facilitate control and early visualization of a spline function over the macro-triangle. Thanks to these properties, the complex geometry of the Wang-Shi macro-structure is transparent to the user. Stable global bases for the full space of [Formula omitted] cubics on the Wang-Shi refined triangulation [Formula omitted] are deduced from the local simplex spline basis by extending the concept of minimal determining sets., Author(s): Tom Lyche [sup.1] , Carla Manni [sup.2] , Hendrik Speleers [sup.2] Author Affiliations: (1) grid.5510.1, 0000 0004 1936 8921, Department of Mathematics, University of Oslo, , Oslo, Norway (2) [...]

In this paper, we investigate the approximation of a diffusion model problem with contrasted diffusivity for various nonconforming approximation methods. The essential difficulty is that the Sobolev smoothness index of the exact solution may be just barely larger than 1. The lack of smoothness is handled by giving a weak meaning to the normal derivative of the exact solution at the mesh faces. We derive robust and quasi-optimal error estimates. Quasi-optimality means that the approximation error is bounded, up to a generic constant, by the best approximation error in the discrete trial space, and robustness means that the generic constant is independent of the diffusivity contrast. The error estimates use a mesh-dependent norm that is equivalent, at the discrete level, to the energy norm and that remains bounded as long as the exact solution has a Sobolev index strictly larger than 1. Finally, we briefly show how the analysis can be extended to the Maxwell's equations., Author(s): Alexandre Ern [sup.1] [sup.2] , Jean-Luc Guermond [sup.1] Author Affiliations: (1) grid.264756.4, 0000 0004 4687 2082, Department of Mathematics, Texas A&M University, , 3368 TAMU, 77843, College Station, TX, [...]

We study the problem of recovering an unknown signal [Formula omitted] given measurements obtained from a generalized linear model with a Gaussian sensing matrix. Two popular solutions are based on a linear estimator [Formula omitted] and a spectral estimator [Formula omitted]. The former is a data-dependent linear combination of the columns of the measurement matrix, and its analysis is quite simple. The latter is the principal eigenvector of a data-dependent matrix, and a recent line of work has studied its performance. In this paper, we show how to optimally combine [Formula omitted] and [Formula omitted]. At the heart of our analysis is the exact characterization of the empirical joint distribution of [Formula omitted] in the high-dimensional limit. This allows us to compute the Bayes-optimal combination of [Formula omitted] and [Formula omitted], given the limiting distribution of the signal [Formula omitted]. When the distribution of the signal is Gaussian, then the Bayes-optimal combination has the form [Formula omitted] and we derive the optimal combination coefficient. In order to establish the limiting distribution of [Formula omitted], we design and analyze an approximate message passing algorithm whose iterates give [Formula omitted] and approach [Formula omitted]. Numerical simulations demonstrate the improvement of the proposed combination with respect to the two methods considered separately., Author(s): Marco Mondelli [sup.1], Christos Thrampoulidis [sup.2], Ramji Venkataramanan [sup.3] Author Affiliations: (1) grid.33565.36, 0000000404312247, Institute of Science and Technology (IST) Austria, , Am Campus 1, 3400, Klosterneuburg, Austria (2) [...]

Quasi-Monte Carlo (QMC) quadrature rules using higher-order digital nets and sequences have been shown to achieve the almost optimal rate of convergence of the worst-case error in Sobolev spaces of arbitrary fixed smoothness [Formula omitted], [Formula omitted]. In a recent paper by the authors, it was proved that randomly digitally shifted order [Formula omitted] digital nets in prime base b achieve the best possible rate of convergence of the root mean square worst-case error of order [Formula omitted] for [Formula omitted], where N and s denote the number of points and the dimension, respectively, which implies the existence of an optimal order QMC rule. More recently, the authors provided an explicit construction of such an optimal order QMC rule by using Chen-Skriganov's digital nets in conjunction with Dick's digit interlacing composition. These results were for fixed number of points. In this paper, we give a more general result on an explicit construction of optimal order QMC rules for arbitrary fixed smoothness [Formula omitted] including the endpoint case [Formula omitted]. That is, we prove that the projection of any infinite-dimensional order [Formula omitted] digital sequence in prime base b onto the first s coordinates achieves the best possible rate of convergence of the worst-case error of order [Formula omitted] for [Formula omitted]. The explicit construction presented in this paper is not only easy to implement but also extensible in both N and s., Author(s): Takashi Goda [sup.1] , Kosuke Suzuki [sup.2] [sup.3] , Takehito Yoshiki [sup.2] [sup.4] Author Affiliations: (Aff1) 0000 0001 2151 536X, grid.26999.3d, Graduate School of Engineering, The University of Tokyo, [...]

In this paper, we develop the theory of the discrete moving frame in two different ways. In the first half of the paper, we consider a discrete moving frame defined on a lattice variety and the equivalence classes of global syzygies that result from the first fundamental group of the variety. In the second half, we consider the continuum limit of discrete moving frames as a local lattice coalesces to a point. To achieve a well-defined limit of discrete frames, we construct multispace, a generalisation of the jet bundle that also generalises Olver's one-dimensional construction. Using interpolation to provide coordinates, we prove that it is a manifold containing the usual jet bundle as a submanifold. We show that continuity of a multispace moving frame ensures that the discrete moving frame converges to a continuous one as lattices coalesce. The smooth frame is, at the same time, the restriction of the multispace frame to the embedded jet bundle. We prove further that the discrete invariants and syzygies approximate their smooth counterparts. In effect, a frame on multispace allows smooth frames and their discretisations to be studied simultaneously. In our last chapter we discuss two important applications, one to the discrete variational calculus, and the second to discrete integrable systems. Finally, in an appendix, we discuss a more general result concerning equicontinuous families of discretisations of moving frames, which are consistent with a smooth frame., Author(s): Gloria Marí Beffa [sup.2] , Elizabeth L. Mansfield [sup.1] Author Affiliations: (1) SMSAS, University of Kent, 0000 0001 2232 2818, grid.9759.2, , CT27NF, Canterbury, England (2) Mathematics Department, University [...]

Kurdyka-Lojasiewicz (KL) exponent plays an important role in estimating the convergence rate of many contemporary first-order methods. In particular, a KL exponent of [Formula omitted] for a suitable potential function is related to local linear convergence. Nevertheless, KL exponent is in general extremely hard to estimate. In this paper, we show under mild assumptions that KL exponent is preserved via inf-projection. Inf-projection is a fundamental operation that is ubiquitous when reformulating optimization problems via the lift-and-project approach. By studying its operation on KL exponent, we show that the KL exponent is [Formula omitted] for several important convex optimization models, including some semidefinite-programming-representable functions and some functions that involve [Formula omitted]-cone reducible structures, under conditions such as strict complementarity. Our results are applicable to concrete optimization models such as group-fused Lasso and overlapping group Lasso. In addition, for nonconvex models, we show that the KL exponent of many difference-of-convex functions can be derived from that of their natural majorant functions, and the KL exponent of the Bregman envelope of a function is the same as that of the function itself. Finally, we estimate the KL exponent of the sum of the least squares function and the indicator function of the set of matrices of rank at most k., Author(s): Peiran Yu [sup.1] , Guoyin Li [sup.2] , Ting Kei Pong [sup.1] Author Affiliations: (1) grid.16890.36, 0000 0004 1764 6123, Department of Applied Mathematics, The Hong Kong Polytechnic University, [...]

Learning mappings of data on manifolds is an important topic in contemporary machine learning, with applications in astrophysics, geophysics, statistical physics, medical diagnosis, biochemistry, and 3D object analysis. This paper studies the problem of learning real-valued functions on manifolds through filtered hyperinterpolation of input-output data pairs where the inputs may be sampled deterministically or at random and the outputs may be clean or noisy. Motivated by the problem of handling large data sets, it presents a parallel data processing approach which distributes the data-fitting task among multiple servers and synthesizes the fitted sub-models into a global estimator. We prove quantitative relations between the approximation quality of the learned function over the entire manifold, the type of target function, the number of servers, and the number and type of available samples. We obtain the approximation rates of convergence for distributed and non-distributed approaches. For the non-distributed case, the approximation order is optimal., Author(s): Guido Montúfar [sup.1] [sup.2], Yu Guang Wang [sup.2] [sup.3] [sup.4] Author Affiliations: (1) grid.19006.3e, 0000 0000 9632 6718, Department of Mathematics and Department of Statistics, University of California, , [...]

Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e. manifolds defined as the zero set of some multivariate multivalued smooth function [Formula omitted]. A natural (and efficient) way to approximate an isomanifold is to consider its piecewise-linear (PL) approximation based on a triangulation [Formula omitted] of the ambient space [Formula omitted]. In this paper, we give conditions under which the PL approximation of an isomanifold is topologically equivalent to the isomanifold. The conditions are easy to satisfy in the sense that they can always be met by taking a sufficiently fine and thick triangulation [Formula omitted]. This contrasts with previous results on the triangulation of manifolds where, in arbitrary dimensions, delicate perturbations are needed to guarantee topological correctness, which leads to strong limitations in practice. We further give a bound on the Fréchet distance between the original isomanifold and its PL approximation. Finally, we show analogous results for the PL approximation of an isomanifold with boundary., Author(s): Jean-Daniel Boissonnat [sup.1] , Mathijs Wintraecken [sup.2] Author Affiliations: (1) grid.5328.c, 0000 0001 2186 3954, Université Côte d'Azur, Inria, , Sophia-Antipolis, France (2) grid.33565.36, 0000000404312247, IST, , Austria, Klosterneuburg, [...]

This paper studies the saddle point problem of polynomials. We give an algorithm for computing saddle points. It is based on solving Lasserre's hierarchy of semidefinite relaxations. Under some genericity assumptions on defining polynomials, we show that: (i) if there exists a saddle point, our algorithm can get one by solving a finite hierarchy of Lasserre-type semidefinite relaxations; (ii) if there is no saddle point, our algorithm can detect its nonexistence., Author(s): Jiawang Nie [sup.1], Zi Yang [sup.1], Guangming Zhou [sup.2] Author Affiliations: (1) grid.266100.3, 0000 0001 2107 4242, Department of Mathematics, University of California San Diego, , 9500 Gilman Drive, [...]

While it is well-known that nonlinear methods of approximation can often perform dramatically better than linear methods, there are still questions on how to measure the optimal performance possible for such methods. This paper studies nonlinear methods of approximation that are compatible with numerical implementation in that they are required to be numerically stable. A measure of optimal performance, called stable manifold widths, for approximating a model class K in a Banach space X by stable manifold methods is introduced. Fundamental inequalities between these stable manifold widths and the entropy of K are established. The effects of requiring stability in the settings of deep learning and compressed sensing are discussed., Author(s): Albert Cohen [sup.1] , Ronald DeVore [sup.2] , Guergana Petrova [sup.2] , Przemyslaw Wojtaszczyk [sup.3] Author Affiliations: (1) grid.462844.8, 0000 0001 2308 1657, Laboratoire Jacques-Louis Lions, Sorbonne Université, , [...]

Randomized trace estimation is a popular and well-studied technique that approximates the trace of a large-scale matrix B by computing the average of [Formula omitted] for many samples of a random vector X. Often, B is symmetric positive definite (SPD) but a number of applications give rise to indefinite B. Most notably, this is the case for log-determinant estimation, a task that features prominently in statistical learning, for instance in maximum likelihood estimation for Gaussian process regression. The analysis of randomized trace estimates, including tail bounds, has mostly focused on the SPD case. In this work, we derive new tail bounds for randomized trace estimates applied to indefinite B with Rademacher or Gaussian random vectors. These bounds significantly improve existing results for indefinite B, reducing the number of required samples by a factor n or even more, where n is the size of B. Even for an SPD matrix, our work improves an existing result by Roosta-Khorasani and Ascher (Found Comput Math, 15(5):1187-1212, 2015) for Rademacher vectors. This work also analyzes the combination of randomized trace estimates with the Lanczos method for approximating the trace of f(B). Particular attention is paid to the matrix logarithm, which is needed for log-determinant estimation. We improve and extend an existing result, to not only cover Rademacher but also Gaussian random vectors., Author(s): Alice Cortinovis [sup.1] , Daniel Kressner [sup.1] Author Affiliations: (1) grid.5333.6, 0000000121839049, Institute of Mathematics, EPF Lausanne, , 1015, Lausanne, Switzerland Introduction > This paper is concerned with approximating [...]

This paper concerns characterizations of approximation classes associated with adaptive finite element methods with isotropic h-refinements. It is known from the seminal work of Binev, Dahmen, DeVore and Petrushev that such classes are related to Besov spaces. The range of parameters for which the inverse embedding results hold is rather limited, and recently, Gaspoz and Morin have shown, among other things, that this limitation disappears if we replace Besov spaces by suitable approximation spaces associated with finite element approximation from uniformly refined triangulations. We call the latter spaces multievel approximation spaces and argue that these spaces are placed naturally halfway between adaptive approximation classes and Besov spaces, in the sense that it is more natural to relate multilevel approximation spaces with either Besov spaces or adaptive approximation classes, than to go directly from adaptive approximation classes to Besov spaces. In particular, we prove embeddings of multilevel approximation spaces into adaptive approximation classes, complementing the inverse embedding theorems of Gaspoz and Morin. Furthermore, in the present paper, we initiate a theoretical study of adaptive approximation classes that are defined using a modified notion of error, the so-called total error, which is the energy error plus an oscillation term. Such approximation classes have recently been shown to arise naturally in the analysis of adaptive algorithms. We first develop a sufficiently general approximation theory framework to handle such modifications, and then apply the abstract theory to second-order elliptic problems discretized by Lagrange finite elements, resulting in characterizations of modified approximation classes in terms of memberships of the problem solution and data into certain approximation spaces, which are in turn related to Besov spaces. Finally, it should be noted that throughout the paper we paid equal attention to both conforming and non-conforming triangulations., Author(s): Tsogtgerel Gantumur [sup.1] Author Affiliations: (1) Department of Mathematics and Statistics, McGill University, 0000 0004 1936 8649, grid.14709.3b, , 805 Sherbrooke West, H3A 0B9, Montreal, QC, Canada Introduction Among [...]

In this paper, we consider the problem of minimizing the sum of two convex functions subject to linear linking constraints. The classical alternating direction type methods usually assume that the two convex functions have relatively easy proximal mappings. However, many problems arising from statistics, image processing and other fields have the structure that while one of the two functions has an easy proximal mapping, the other function is smoothly convex but does not have an easy proximal mapping. Therefore, the classical alternating direction methods cannot be applied. To deal with the difficulty, we propose in this paper an alternating direction method based on extragradients. Under the assumption that the smooth function has a Lipschitz continuous gradient, we prove that the proposed method returns an [Formula omitted]-optimal solution within [Formula omitted] iterations. We apply the proposed method to solve a new statistical model called fused logistic regression. Our numerical experiments show that the proposed method performs very well when solving the test problems. We also test the performance of the proposed method through solving the lasso problem arising from statistics and compare the result with several existing efficient solvers for this problem; the results are very encouraging., Author(s): Tianyi Lin [sup.1] , Shiqian Ma [sup.1] , Shuzhong Zhang [sup.2] Author Affiliations: (1) 0000 0004 1937 0482grid.10784.3aDepartment of Systems Engineering and Engineering Management, The Chinese University of Hong [...]

Polynomial factorization in conventional sense is an ill-posed problem due to its discontinuity with respect to coefficient perturbations, making it a challenge for numerical computation using empirical data. As a regularization, this paper formulates the notion of numerical factorization based on the geometry of polynomial spaces and the stratification of factorization manifolds. Furthermore, this paper establishes the existence, uniqueness, Lipschitz continuity, condition number, and convergence of the numerical factorization to the underlying exact factorization, leading to a robust and efficient algorithm with a MATLAB implementation capable of accurate polynomial factorizations using floating point arithmetic even if the coefficients are perturbed., Author(s): Wenyuan Wu [sup.1] , Zhonggang Zeng [sup.2] Author Affiliations: (1) Chongqing Key Laboratory of Automated Reasoning and Cognition, Chongqing Institute of Green and Intelligent Technology, CAS, Chongqing, China (2) [...]

In this paper, we analyze several methods for approximating gradients of noisy functions using only function values. These methods include finite differences, linear interpolation, Gaussian smoothing, and smoothing on a sphere. The methods differ in the number of functions sampled, the choice of the sample points, and the way in which the gradient approximations are derived. For each method, we derive bounds on the number of samples and the sampling radius which guarantee favorable convergence properties for a line search or fixed step size descent method. To this end, we use the results in Berahas et al. (Global convergence rate analysis of a generic line search algorithm with noise, arXiv:1910.04055, 2019) and show how each method can satisfy the sufficient conditions, possibly only with some sufficiently large probability at each iteration, as happens to be the case with Gaussian smoothing and smoothing on a sphere. Finally, we present numerical results evaluating the quality of the gradient approximations as well as their performance in conjunction with a line search derivative-free optimization algorithm., Author(s): Albert S. Berahas [sup.1], Liyuan Cao [sup.2], Krzysztof Choromanski [sup.3], Katya Scheinberg [sup.4] Author Affiliations: (1) grid.214458.e, 0000000086837370, Department of Industrial and Operations Engineering, University of Michigan, , Ann [...]

This paper introduces a new symbolic-numeric strategy for finding semidiscretizations of a given PDE that preserve multiple local conservation laws. We prove that for one spatial dimension, various one-step time integrators from the literature preserve fully discrete local conservation laws whose densities are either quadratic or a Hamiltonian. The approach generalizes to time integrators with more steps and conservation laws of other kinds; higher-dimensional PDEs can be treated by iterating the new strategy. We use the Boussinesq equation as a benchmark and introduce new families of schemes of order two and four that preserve three conservation laws. We show that the new technique is practicable for PDEs with three dependent variables, introducing as an example new families of second-order schemes for the potential Kadomtsev-Petviashvili equation., Author(s): Gianluca Frasca-Caccia [sup.1], Peter E. Hydon [sup.1] Author Affiliations: (1) grid.9759.2, 0000 0001 2232 2818, School of Mathematics, Statistics and Actuarial Science University of Kent, , Canterbury, CT2 7FS, [...]

In 1995 Jean-Claude Hausmann proved that a compact Riemannian manifold X is homotopy equivalent to its Rips complex [Formula omitted] for small values of parameter r. He then conjectured that the connectivity of Rips complexes is a monotone function in r, a statement which has been supported by all known examples up to present. In this paper, we prove that [Formula omitted] equipped with a certain Riemannian metric is a counter-example to Hausmann's conjecture. Our proof combines the Stability Theorem of persistent homology, a persistent version of Hausmann's Theorem, and an approximation theorem of Ferry and Okun., Author(s): Ziga Virk [sup.1] Author Affiliations: (1) grid.8954.0, 0000 0001 0721 6013, University of Ljubljana, , Ljubljana, Slovenia Introduction > One of the basic tasks of computational topology is reconstruction [...]

We provide a new upper bound for sampling numbers [Formula omitted] associated with the compact embedding of a separable reproducing kernel Hilbert space into the space of square integrable functions. There are universal constants [Formula omitted] (which are specified in the paper) such that gn2[less than or equal to]Clog(n)n[summation]k[greater than or equal to]âcn[right floor][sigma]k2,n[greater than or equal to]2,where [Formula omitted] is the sequence of singular numbers (approximation numbers) of the Hilbert-Schmidt embedding [Formula omitted]. The algorithm which realizes the bound is a least squares algorithm based on a specific set of sampling nodes. These are constructed out of a random draw in combination with a down-sampling procedure coming from the celebrated proof of Weaver's conjecture, which was shown to be equivalent to the Kadison-Singer problem. Our result is non-constructive since we only show the existence of a linear sampling operator realizing the above bound. The general result can for instance be applied to the well-known situation of [Formula omitted] in [Formula omitted] with [Formula omitted]. We obtain the asymptotic bound gn[less than or equal to]Cs,dn-slog(n)(d-1)s+1/2,which improves on very recent results by shortening the gap between upper and lower bound to [Formula omitted]. The result implies that for dimensions [Formula omitted] any sparse grid sampling recovery method does not perform asymptotically optimal., Author(s): Nicolas Nagel [sup.1], Martin Schäfer [sup.1], Tino Ullrich [sup.1] Author Affiliations: (1) grid.6810.f, 0000 0001 2294 5505, Faculty of Mathematics, TU Chemnitz, , 09107, Chemnitz, Germany Introduction > In [...]

In this paper, we review recent progress on two related issues. Firstly, the discretisation of partial differential equations of quantum mechanics in a semiclassical regime. Due to the presence of a small parameter, such equations exhibit high oscillations and multiscale behaviour, rendering them difficult to discretise. We describe a methodology, using symmetric Zassenhaus splittings in a free Lie algebra, which allows for their exceedingly fast and accurate numerics. The imperative of preserving the unitarity of the underlying flow takes us to the second theme of this paper, approximation of derivatives by skew-symmetric matrices. Here, we identify a gap in the elementary theory of finite-difference approximations: in the presence of Dirichlet boundary conditions, it is impossible to approximate the derivative to order higher than two on a uniform grid! This motivates the investigation of skew symmetry on non-uniform grids, an endeavour which, although still in its infancy, is already replete with interesting results. We conclude by discussing a number of generalisations and open problems., Author(s): Arieh Iserles[sup.1] Author Affiliations: (1) Department of Applied Mathematics and Theoretical Physics, Centre for Mathematical Sciences, University of Cambridge, Wilberfoce Rd., CB3 0WA, CambridgeUK Introduction Computational partial differential equations [...]

The complex or non-Hermitian orthogonal polynomials with analytic weights are ubiquitous in several areas such as approximation theory, random matrix models, theoretical physics and in numerical analysis, to mention a few. Due to the freedom in the choice of the integration contour for such polynomials, the location of their zeros is a priori not clear. Nevertheless, numerical experiments, such as those presented in this paper, show that the zeros not simply cluster somewhere on the plane, but persistently choose to align on certain curves, and in a very regular fashion. The problem of the limit zero distribution for the non-Hermitian orthogonal polynomials is one of the central aspects of their theory. Several important results in this direction have been obtained, especially in the last 30 years, and describing them is one of the goals of the first parts of this paper. However, the general theory is far from being complete, and many natural questions remain unanswered or have only a partial explanation. Thus, the second motivation of this paper is to discuss some 'mysterious' configurations of zeros of polynomials, defined by an orthogonality condition with respect to a sum of exponential functions on the plane, that appeared as a results of our numerical experiments. In this apparently simple situation the zeros of these orthogonal polynomials may exhibit different behaviors: for some of them we state the rigorous results, while others are presented as conjectures (apparently, within a reach of modern techniques). Finally, there are cases for which it is not yet clear how to explain our numerical results, and where we cannot go beyond an empirical discussion., Author(s): A. Martinez-Finkelshtein[sup.1] , E. A. Rakhmanov[sup.2] Author Affiliations: (1) Department of Mathematics, University of Almeria, AlmeriaSpain (2) Department of Mathematics, University of South Florida, Tampa, FLUSA Introduction One of [...]

In this paper, we propose and analyze zeroth-order stochastic approximation algorithms for nonconvex and convex optimization, with a focus on addressing constrained optimization, high-dimensional setting, and saddle point avoiding. To handle constrained optimization, we first propose generalizations of the conditional gradient algorithm achieving rates similar to the standard stochastic gradient algorithm using only zeroth-order information. To facilitate zeroth-order optimization in high dimensions, we explore the advantages of structural sparsity assumptions. Specifically, (i) we highlight an implicit regularization phenomenon where the standard stochastic gradient algorithm with zeroth-order information adapts to the sparsity of the problem at hand by just varying the step size and (ii) propose a truncated stochastic gradient algorithm with zeroth-order information, whose rate of convergence depends only poly-logarithmically on the dimensionality. We next focus on avoiding saddle points in nonconvex setting. Toward that, we interpret the Gaussian smoothing technique for estimating gradient based on zeroth-order information as an instantiation of first-order Stein's identity. Based on this, we provide a novel linear-(in dimension) time estimator of the Hessian matrix of a function using only zeroth-order information, which is based on second-order Stein's identity. We then provide a zeroth-order variant of cubic regularized Newton method for avoiding saddle points and discuss its rate of convergence to local minima., Author(s): Krishnakumar Balasubramanian [sup.1], Saeed Ghadimi [sup.2] Author Affiliations: (1) grid.27860.3b, 0000 0004 1936 9684, Department of Statistics, University of California, , Davis, CA, USA (2) grid.46078.3d, 0000 0000 8644 [...]

The paper deals with the problem of extrapolating data derived from sampling a [Formula omitted] function at scattered sites on a Lipschitz region [Formula omitted] in [Formula omitted] to points outside of [Formula omitted] in a computationally efficient way. While extrapolation problems go back to Whitney and many such problems have had successful theoretical resolutions, practical, computationally efficient implementations seem to be lacking. The goal here is to provide one way of obtaining such a method in a solid mathematical framework. The method utilized is a novel two-step moving least squares procedure (MLS) where the second step incorporates an error term obtained from the first MLS step. While the utility of the extrapolation degrades as a function of the distance to the boundary of [Formula omitted], the method gives rise to improved meshfree approximation error estimates when using the local Lagrange kernels related to certain radial basis functions., Author(s): Anat Amir [sup.1] , David Levin [sup.1] , Francis J. Narcowich [sup.2] , Joseph D. Ward [sup.2] Author Affiliations: (1) grid.12136.37, 0000 0004 1937 0546, School of Mathematical Sciences, [...]

We are given a uniformly elliptic coefficient field that we regard as a realization of a stationary and finite-range ensemble of coefficient fields. Given a right-hand side supported in a ball of size [Formula omitted] and of vanishing average, we are interested in an algorithm to compute the solution near the origin, just using the knowledge of the given realization of the coefficient field in some large box of size [Formula omitted]. More precisely, we are interested in the most seamless artificial boundary condition on the boundary of the computational domain of size L. Motivated by the recently introduced multipole expansion in random media, we propose an algorithm. We rigorously establish an error estimate on the level of the gradient in terms of [Formula omitted], using recent results in quantitative stochastic homogenization. More precisely, our error estimate has an a priori and an a posteriori aspect: with a priori overwhelming probability, the prefactor can be bounded by a constant that is computable without much further effort, on the basis of the given realization in the box of size L. We also rigorously establish that the order of the error estimate in both L and [Formula omitted] is optimal, where in this paper we focus on the case of [Formula omitted]. This amounts to a lower bound on the variance of the quantity of interest when conditioned on the coefficients inside the computational domain, and relies on the deterministic insight that a sensitivity analysis with respect to a defect commutes with stochastic homogenization. Finally, we carry out numerical experiments that show that this optimal convergence rate already sets in at only moderately large L, and that more naive boundary conditions perform worse both in terms of rate and prefactor., Author(s): Jianfeng Lu [sup.1], Felix Otto [sup.2] Author Affiliations: (1) grid.26009.3d, 0000 0004 1936 7961, Mathematics Department, Duke University, , Box 90320, 27708, Durham, NC, USA (2) grid.419532.8, Max Planck [...]

This paper introduces a new notion of a Fenchel conjugate, which generalizes the classical Fenchel conjugation to functions defined on Riemannian manifolds. We investigate its properties, e.g., the Fenchel-Young inequality and the characterization of the convex subdifferential using the analogue of the Fenchel-Moreau Theorem. These properties of the Fenchel conjugate are employed to derive a Riemannian primal-dual optimization algorithm and to prove its convergence for the case of Hadamard manifolds under appropriate assumptions. Numerical results illustrate the performance of the algorithm, which competes with the recently derived Douglas-Rachford algorithm on manifolds of nonpositive curvature. Furthermore, we show numerically that our novel algorithm may even converge on manifolds of positive curvature., Author(s): Ronny Bergmann [sup.1], Roland Herzog [sup.1], Maurício Silva Louzeiro [sup.1], Daniel Tenbrinck [sup.2], José Vidal-Núñez [sup.3] Author Affiliations: (1) grid.6810.f, 0000 0001 2294 5505, Faculty of Mathematics, Technische Universität [...]

This paper is concerned with the derivation and properties of differential complexes arising from a variety of problems in differential equations, with applications in continuum mechanics, relativity, and other fields. We present a systematic procedure which, starting from well-understood differential complexes such as the de Rham complex, derives new complexes and deduces the properties of the new complexes from the old. We relate the cohomology of the output complex to that of the input complexes and show that the new complex has closed ranges, and, consequently, satisfies a Hodge decomposition, Poincaré-type inequalities, well-posed Hodge-Laplacian boundary value problems, regular decomposition, and compactness properties on general Lipschitz domains., Author(s): Douglas N. Arnold [sup.1] , Kaibo Hu [sup.1] Author Affiliations: (1) grid.17635.36, 0000000419368657, University of Minnesota, , Minneapolis, MN, USA Introduction Differential complexes are an important tool in the [...]

Certifying function nonnegativity is a ubiquitous problem in computational mathematics, with especially notable applications in optimization. We study the question of certifying nonnegativity of signomials based on the recently proposed approach of Sums-of-AM/GM-Exponentials (SAGE) decomposition due to the second author and Shah. The existence of a SAGE decomposition is a sufficient condition for nonnegativity of a signomial, and it can be verified by solving a tractable convex relative entropy program. We present new structural properties of SAGE certificates such as a characterization of the extreme rays of the cones associated to these decompositions as well as an appealing form of sparsity preservation. These lead to a number of important consequences such as conditions under which signomial nonnegativity is equivalent to the existence of a SAGE decomposition; our results represent the broadest-known class of nonconvex signomial optimization problems that can be solved efficiently via convex relaxation. The analysis in this paper proceeds by leveraging the interaction between the convex duality underlying SAGE certificates and the face structure of Newton polytopes. After proving our main signomial results, we direct our machinery toward the topic of globally nonnegative polynomials. This leads to (among other things) efficient methods for certifying polynomial nonnegativity, with complexity independent of the degree of a polynomial., Author(s): Riley Murray [sup.1], Venkat Chandrasekaran [sup.1], Adam Wierman [sup.1] Author Affiliations: (1) grid.20861.3d, 0000000107068890, California Institute of Technology, , 91125, Pasadena, CA, USA Introduction The problem of certifying function [...]

This paper studies a Laplace operator on semi-discrete surfaces. A semi-discrete surface is represented by a mapping into three-dimensional Euclidean space possessing one discrete variable and one continuous variable. It can be seen as a limit case of a quadrilateral mesh, or as a semi-discretization of a smooth surface. Laplace operators on both smooth and discrete surfaces have been an object of interest for a long time, also from the viewpoint of applications. There are a wealth of geometric objects available immediately once a Laplacian is defined, e.g., the mean curvature normal. We define our semi-discrete Laplace operator to be the limit of a discrete Laplacian on a quadrilateral mesh, which converges to the semi-discrete surface. The main result of this paper is that this limit exists under very mild regularity assumptions. Moreover, we show that the semi-discrete Laplace operator inherits several important properties from its discrete counterpart, like symmetry, positive semi-definiteness, and linear precision. We also prove consistency of the semi-discrete Laplacian, meaning that it converges pointwise to the Laplace-Beltrami operator, when the semi-discrete surface converges to a smooth one. This result particularly implies consistency of the corresponding discrete scheme., Author(s): Wolfgang Carl[sup.1] Author Affiliations: (1) Institute of Geometry, Graz University of Technology, Kopernikusgasse 24, 8010, GrazAustria Introduction The Laplace-Beltrami operator on smooth surfaces and Riemannian manifolds is a well-studied [...]

Denoising has to do with estimating a signal from its noisy observations . In this paper, we focus on the 'structured denoising problem,' where the signal possesses a certain structure and has independent normally distributed entries with mean zero and variance [Formula omitted]. We employ a structure-inducing convex function [Formula omitted] and solve to estimate , for some . Common choices for include the norm for sparse vectors, the norm for block-sparse signals and the nuclear norm for low-rank matrices. The metric we use to evaluate the performance of an estimate [Formula omitted] is the normalized mean-squared error . We show that NMSE is maximized as and we find the exact worst-case NMSE, which has a simple geometric interpretation: the mean-squared distance of a standard normal vector to the [Formula omitted]-scaled subdifferential . When [Formula omitted] is optimally tuned to minimize the worst-case NMSE, our results can be related to the constrained denoising problem . The paper also connects these results to the generalized LASSO problem, in which one solves to estimate from noisy linear observations . We show that certain properties of the LASSO problem are closely related to the denoising problem. In particular, we characterize the normalized LASSO cost and show that it exhibits a 'phase transition' as a function of number of observations. We also provide an order-optimal bound for the LASSO error in terms of the mean-squared distance. Our results are significant in two ways. First, we find a simple formula for the performance of a general convex estimator. Secondly, we establish a connection between the denoising and linear inverse problems., Author(s): Samet Oymak[sup.1] , Babak Hassibi[sup.2] Author Affiliations: (1) Department of Electrical Engineering and Computer Science, UC Berkeley, 94720, Berkeley, CA, USA (2) Department of Electrical Engineering, Caltech, 91125, Pasadena, [...]

This paper is concerned with the question of reconstructing a vector in a finite-dimensional complex Hilbert space when only the magnitudes of the coefficients of the vector under a redundant linear map are known. We present new invertibility results as well as an iterative algorithm that finds the least-square solution, which is robust in the presence of noise. We analyze its numerical performance by comparing it to the Cramer-Rao lower bound., Author(s): Radu Balan[sup.1] Author Affiliations: (1) Department of Mathematics and Center for Scientific Computation and Mathematical Modeling, University of Maryland, College Park, 20742, College Park, MD, USA Introduction This paper [...]