Mathematics (math)

  • PDF
    We establish a tight characterization of the worst-case rates for the excess risk of agnostic learning with sample compression schemes and for uniform convergence for agnostic sample compression schemes. In particular, we find that the optimal rates of convergence for size-$k$ agnostic sample compression schemes are of the form $\sqrt{\frac{k \log(n/k)}{n}}$, which contrasts with agnostic learning with classes of VC dimension $k$, where the optimal rates are of the form $\sqrt{\frac{k}{n}}$.
  • PDF
    We generalize the index polynomial invariant to the case of virtual tangles. Three polynomial invariants result from this generalization; we give a brief overview of their definition and some basic properties.
  • PDF
    We combine conditional variational autoencoders (VAE) with adversarial censoring in order to learn invariant representations that are disentangled from nuisance/sensitive variations. In this method, an adversarial network attempts to recover the nuisance variable from the representation, which the VAE is trained to prevent. Conditioning the decoder on the nuisance variable enables clean separation of the representation, since they are recombined for model learning and data reconstruction. We show this natural approach is theoretically well-founded with information-theoretic arguments. Experiments demonstrate that this method achieves invariance while preserving model learning performance, and results in visually improved performance for style transfer and generative sampling tasks.
  • PDF
    Visible light communications (VLC) is an emerging field in technology and research. Estimating the channel taps is a major requirement for designing reliable communication systems. Due to the nonlinear characteristics of the VLC channel those parameters cannot be derived easily. They can be calculated by means of software simulation. In this work, a novel methodology is proposed for the prediction of channel parameters using neural networks. Measurements conducted in a controlled experimental setup are used to train neural networks for channel tap prediction. Our experiment results indicate that neural networks can be effectively trained to predict channel taps under different environmental conditions.
  • PDF
    In this work, we present a new derivative-free optimization method and investigate its use for training neural networks. Our method is motivated by the Ensemble Kalman Filter (EnKF), which has been used successfully for solving optimization problems that involve large-scale, highly nonlinear dynamical systems. A key benefit of the EnKF method is that it requires only the evaluation of the forward propagation but not its derivatives. Hence, in the context of neural networks it alleviates the need for back propagation and reduces the memory consumption dramatically. However, the method is not a pure "black-box" global optimization heuristic as it efficiently utilizes the structure of typical learning problems. We propose an important modification of the EnKF that enables us to prove convergence of our method to the minimizer of a strongly convex function. Our method also bears similarity with implicit filtering and we demonstrate its potential for minimizing highly oscillatory functions using a simple example. Further, we provide numerical examples that demonstrate the potential of our method for training deep neural networks.
  • PDF
    Robust principal component analysis (RPCA) is a well-studied problem with the goal of decomposing a matrix into the sum of low-rank and sparse components. In this paper, we propose a nonconvex feasibility reformulation of RPCA problem and apply an alternating projection method to solve it. To the best of our knowledge, we are the first to propose a method that solves RPCA problem without considering any objective function, convex relaxation, or surrogate convex constraints. We demonstrate through extensive numerical experiments on a variety of applications, including shadow removal, background estimation, face detection, and galaxy evolution, that our approach matches and often significantly outperforms current state-of-the-art in various ways.
  • PDF
    The stochastic gradient descent has been widely used for solving composite optimization problems in big data analyses. Many algorithms and convergence properties have been developed. The composite functions were convex primarily and gradually nonconvex composite functions have been adopted to obtain more desirable properties. The convergence properties have been investigated, but only when either of composite functions is nonconvex. There is no convergence property when both composite functions are nonconvex, which is named the \textitdoubly-nonconvex case.To overcome this difficulty, we assume a simple and weak condition that the penalty function is \textitquasiconvex and then we obtain convergence properties for the stochastic doubly-nonconvex composite optimization problem.The convergence rate obtained here is of the same order as the existing work.We deeply analyze the convergence rate with the constant step size and mini-batch size and give the optimal convergence rate with appropriate sizes, which is superior to the existing work. Experimental results illustrate that our method is superior to existing methods.
  • PDF
    Efficient high-order time integration schemes are necessary to capture the complex processes involved in atmospheric flows over long periods of time. In this work, we propose a high-order, implicit-explicit numerical scheme that combines Multi-Level Spectral Deferred Corrections (MLSDC) and the Spherical Harmonics (SH) transform to solve the wave-propagation problems arising from the shallow-water equations on the rotating sphere. The iterative temporal integration is based on a sequence of corrections distributed on coupled space-time levels to perform a significant portion of the calculations on a coarse representation of the problem and hence to reduce the time-to-solution while preserving accuracy. In our scheme, referred to as MLSDC-SH, the spatial discretization plays a key role in the efficiency of MLSDC, since the SH basis allows for consistent transfer functions between space-time levels that preserve important physical properties of the solution. We study the performance of the MLSDC-SH scheme with shallow-water test cases commonly used in numerical atmospheric modeling. We use this suite of test cases, which gradually adds more complexity to the nonlinear system of governing partial differential equations, to perform a detailed analysis of the convergence rate of MLSDC-SH upon refinement in time. We illustrate the good stability properties of MLSDC-SH and show that the proposed scheme achieves up to eighth-order accuracy in time. Finally, we study the conditions in which MLSDC-SH achieves its theoretical speedup, and we show that it can significantly reduce the computational cost compared to single-level Spectral Deferred Corrections (SDC).
  • PDF
    The goal of this paper is to study a distributed version of the gradient temporal-difference (GTD) learning algorithm for multiagent Markov decision processes (MDPs). The temporal-difference (TD) learning is a reinforcement learning (RL) algorithm which learns an infinite horizon discounted cost function (or value function) for a given fixed policy without the model knowledge. In the distributed RL case each agent receives local reward through a local processing. Information exchange over sparse and random communication networks allows the agents to learn the global value function corresponding to a global reward, which is a sum of local rewards. In this paper, the problem is converted into a constrained convex optimization problem with a consensus constraint. Then, we propose a stochastic primal-dual distributed GTD algorithm and prove that it almost surely converges to a set of stationary points of the optimization problem.
  • PDF
    This paper considers a distributed convex optimization problem over a time-varying multi-agent network, where each agent has its own decision variables that should be set so as to minimize its individual objective subject to local constraints and global coupling equality constraints. Over directed graphs, a distributed algorithm is proposed that incorporates the push-sum protocol into dual subgradient methods. Under the convexity assumption, the optimality of primal and dual variables, and constraint violations is first established. Then the explicit convergence rates of the proposed algorithm are obtained. Finally, some numerical experiments on the economic dispatch problem are provided to demonstrate the efficacy of the proposed algorithm.
  • PDF
    Quantum multiparameter estimation involves estimating multiple parameters simultaneously and was shown to be more accurate than estimating the parameters individually. Our interest here is to determine multiparameter quantum Cramer-Rao bounds (QCRBs) for noisy metrology. We do so, in particular, using anti-symmetric logarithmic derivatives (ALDs) for the quantum Fisher information matrix (QFIM). A recent work studied the simultaneous estimation of all three components of a magnetic field using a pure probe state and unitary evolution. Here, we consider the more practical problem of simultaneously estimating multiple parameters using a mixed probe state. We found that the QCRB so obtained using ALDs depends only on the first and second order reduced density operators of the probe state. Moreover, recent works have studied upper bounds to single-parameter as well as multiple-parameter QFIs for systems under arbitrary evolution. We here present an upper bound to the noisy multiparameter QFIM in the most general form using the ALD-approach.
  • PDF
    Hybrid precoding design is challenging for millimeter-wave (mmWave) massive MIMO. Most prior hybrid precoding schemes are designed to maximize the sum spectral efficiency (SSE), while seldom investigate the bit-error-rate (BER). Therefore, we propose an over-sampling codebook (OSC)-based hybrid minimum sum-mean-square-error (min-SMSE) precoding scheme for mmWave multi-user three-dimensional (3D)-MIMO systems to optimize the BER, where multi-user transmission with multiple data streams for each user is considered. Specifically, given the effective baseband channel consisting of the real channel and analog precoding, we first design the digital precoder/combiner based on min-SMSE criterion to optimize the BER. To further reduce the SMSE between the transmit and receive signals, we propose an OSC-based joint analog precoder/combiner (JAPC) design. Simulation results show that the proposed scheme can achieve the better performance than its conventional counterparts.
  • PDF
    Convolution has been playing a prominent role in various applications in science and engineering for many years. It is the most important operation in convolutional neural networks. There has been a recent growth of interests of research in generalizing convolutions on curved domains such as manifolds and graphs. However, existing approaches cannot preserve all the desirable properties of Euclidean convolutions, namely compactly supported filters, directionality, transferability across different manifolds. In this paper we develop a new generalization of the convolution operation, referred to as parallel transport convolution (PTC), on Riemannian manifolds and their discrete counterparts. PTC is designed based on the parallel transportation which is able to translate information along a manifold and to intrinsically preserve directionality. PTC allows for the construction of compactly supported filters and is also robust to manifold deformations. This enables us to preform wavelet-like operations and to define deep convolutional neural networks on curved domains.
  • PDF
    Distributed optimization has gained a surge of interest in recent years. In this paper we propose a distributed projection free algorithm named Distributed Conditional Gradient Sliding(DCGS). Compared to the state-of-the-art distributed Frank-Wolfe algorithm, our algorithm attains the same communication complexity under much more realistic assumptions. In contrast to the consensus based algorithm, DCGS is based on the primal-dual algorithm, yielding a modular analysis that can be exploited to improve linear oracle complexity whenever centralized Frank-Wolfe can be improved. We demonstrate this advantage and show that the linear oracle complexity can be reduced to almost the same order of magnitude as the communication complexity, when the feasible set is polyhedral. Finally we present experimental results on Lasso and matrix completion, demonstrating significant performance improvement compared to the existing distributed Frank-Wolfe algorithm.
  • PDF
    This article deals with the following simpler version of an open problem in system realization theory which has several important engineering applications: Given a collection of masses and a set of linear springs with a specified cost and stiffness, a resource constraint in terms of a budget on the total cost, the problem is to determine an optimal connection of masses and springs so that the resulting structure is as stiff as possible, i.e., the structure is connected and its smallest non-zero natural frequency is as large as possible. In this article, algebraic connectivity, or its mechanical analog - the smallest non-zero natural frequency of a connected structure was chosen as a performance objective. Algebraic connectivity determines the convergence rate of consensus protocols and error attenuation in Unmanned Aerial Vehicle (UAV) formations and is chosen to be a performance objective as it can be viewed as a measure of robustness in UAV communication networks to random node failures. Underlying the mechanical and UAV network synthesis problems is a Mixed Integer Semi-Definite Program (MISDP), an NP-hard problem. The novel contributions of this article lies in developing efficient algorithms to solve the MISDPs based on iterative primal-dual algorithm, cutting-plane methods for polyhedral outer-approximation, capturing the feasible set of MISDPs using Fiedler vectors or Laplacian with equivalency guarantees, and efficient neighborhood-search-based heuristic algorithms.
  • PDF
    The main computational cost in the training of and prediction with Convolution Neural Networks (CNNs) typically stems from the convolution. In this paper, we present three novel ways to parameterize the convolution more efficiently, significantly decreasing the computational complexity. Commonly used CNNs filter the input data using a series of spatial convolutions with compact stencils that couple features from all channels and point-wise nonlinearities. In this paper, we propose three architectures that are cheaper to couple the channel dimension and thereby reduce both the number of trainable weights and the computational cost of the CNN. The first architecture is inspired by tensor-products and imposes a circulant coupling of the channels. The second and third architectures arise as discretizations of a new type of residual neural network (ResNet) that is inspired by Partial Differential Equations (PDEs) or reaction-diffusion type. The coupling patterns of the first two architectures are applicable to a large class of CNNs. We outline in our numerical experiments that the proposed architectures, although considerably reducing the number of trainable weights, yield comparable accuracy to existing CNNs that are fully coupled in the channel dimension.
  • PDF
    We use a numerical method to compute a database of three-point branched covers of the complex projective line of small degree. We report on some interesting features of this data set, including issues of descent.
  • May 22 2018 math.DG arXiv:1805.07660v1
    PDF
    We study the geometry of Engel structures, which are 2-plane fields on 4-manifolds satisfying a generic condition, that are compatible with other geometric structures. A complex Engel structure is an Engel 2-plane field on a complex surface for which the 2-planes are complex lines. We solve the equivalence problems for complex Engel structures and use the resulting structure equations to classify homogeneous complex Engel structures. This allows us to determine all compact, homogeneous examples. Compact manifolds that support homogeneous complex Engel structures are diffeomorphic to $S^1\times SU(2)$ or quotients of $\mathbb{C}^2$, $S^1\times SU(2)$, $S^1\times G$ or $H$ by co-compact lattices, where $G$ is the connected and simply-connected Lie group with Lie algebra $\mathfrak{sl}_2(\mathbb{R})$ and $H$ is a solvable Lie group.
  • PDF
    We continue the study of enriched infinity categories, using a definition equivalent to that of Gepner and Haugseng. In our approach enriched infinity categories are associative monoids in an especially designed monoidal category of enriched quivers. We prove that, in case the monoidal structure in the basic category M comes from direct product, our definition is essentially equivalent to the approach via Segal objects. Furthermore, we compare our notion with the notion of category left-tensored over M, and prove a version of Yoneda lemma in this context.
  • PDF
    In this paper we consider Multiple-Input-Multiple-Output (MIMO) detection using deep neural networks. We introduce two different deep architectures: a standard fully connected multi-layer network, and a Detection Network (DetNet) which is specifically designed for the task. The structure of DetNet is obtained by unfolding the iterations of a projected gradient descent algorithm into a network. We compare the accuracy and runtime complexity of the purposed approaches and achieve state-of-the-art performance while maintaining low computational requirements. Furthermore, we manage to train a single network to detect over an entire distribution of channels. Finally, we consider detection with soft outputs and show that the networks can easily be modified to produce soft decisions.
  • PDF
    The nodal set of a Laplacian eigenfunction forms a partition of the underlying manifold or graph. Another natural partition is based on the gradient vector field of the eigenfunction (on a manifold) or on the extremal points of the eigenfunction (on a graph). The submanifolds (or subgraphs) of this partition are called Neumann domains. This paper reviews the subject, as appears in a few recent works and points out some open questions and conjectures. The paper concerns both manifolds and metric graphs and the exposition allows for a comparison between the results obtained for each of them.
  • PDF
    We propose a deep generative Markov State Model (DeepGenMSM) learning framework for inference of metastable dynamical systems and prediction of trajectories. After unsupervised training on time series data, the model contains (i) a probabilistic encoder that maps from high-dimensional configuration space to a small-sized vector indicating the membership to metastable (long-lived) states, (ii) a Markov chain that governs the transitions between metastable states and facilitates analysis of the long-time dynamics, and (iii) a generative part that samples the conditional distribution of configurations in the next time step. The model can be operated in a recursive fashion to generate trajectories to predict the system evolution from a defined starting state and propose new configurations. The DeepGenMSM is demonstrated to provide accurate estimates of the long-time kinetics and generate valid distributions for molecular dynamics (MD) benchmark systems. Remarkably, we show that DeepGenMSMs are able to make long time-steps in molecular configuration space and generate physically realistic structures in regions that were not seen in training data.
  • PDF
    In the present paper, we introduce a multi-type display calculus for dynamic epistemic logic, which we refer to as Dynamic Calculus. The display-approach is suitable to modularly chart the space of dynamic epistemic logics on weaker-than-classical propositional base. The presence of types endows the language of the Dynamic Calculus with additional expressivity, allows for a smooth proof-theoretic treatment, and paves the way towards a general methodology for the design of proof systems for the generality of dynamic logics, and certainly beyond dynamic epistemic logic. We prove that the Dynamic Calculus adequately captures Baltag-Moss-Solecki's dynamic epistemic logic, and enjoys Belnap-style cut elimination.
  • PDF
    We give analogues of the Auslander correspondence for two classes of triangulated categories satisfying certain finiteness conditions. The first class is triangulated categories with additive generators and we consider their endomorphism algebras as the Auslander algebras. For the second one, we introduce the notion of $[1]$-additive generators and consider their graded endormorphism algebras as the Auslander algebras. We give a homological characterization of the Auslander algebras for each class. Along the way, we also show that the algebraic triangle structures on the homotopy categories are unique up to equivalence.
  • PDF
    A pair $(A,B)$ of square $(0,1)$-matrices is called a Lehman pair if $AB^T=J+kI$ for some integer $k\in\{-1,1,2,3,\ldots\}$, and the matrices $A$ and $B$ are called Lehman pair. This terminology arises because Lehman showed that the rows of minimum weight in any non-degenerate minimally nonideal (mni) matrix $M$ form a square Lehman submatrix of $M$. In this paper, we view a Lehman matrix as the bipartite adjacency matrix of a regular bipartite graph, focussing in particular on the case where the graph is cubic. From this perspective, we identify two constructions that generate cubic Lehman graphs from smaller Lehman graphs. The most prolific of these constructions involves repeatedly replacing suitable pairs of edges with a particular $6$-vertex subgraph that we call a $3$-rung ladder segment. Two decades ago, Lütolf and Margot initiated a computational study of mni matrices and constructed a catalogue containing (among other things) a listing of all cubic Lehman matrices with $k =1$ of order up to $17 \times 17$. We verify their catalogue (which has just one omission), and extend the computational results to $20 \times 20$ matrices. Of the $908$ cubic Lehman matrices (with $k=1$) of order up to $20 \times 20$, only two do not arise from our $3$-rung ladder construction. However these exceptions can be derived from our second construction, and so our two constructions cover all known cubic Lehman matrices with $k=1$.
  • PDF
    We present an approach for variational regularization of inverse and imaging problems for recovering functions with values in a set of vectors. We introduce regularization functionals, which are derivative-free double integrals of such functions. These regularization functionals are motivated from double integrals, which approximate Sobolev semi-norms of intensity functions. These were introduced in Bourgain, Brézis and Mironescu, "Another Look at Sobolev Spaces". In: Optimal Control and Partial Differential Equations-Innovations and Applications, IOS press, Amsterdam, 2001. For the proposed regularization functionals we prove existence of minimizers as well as a stability and convergence result for functions with values in a set of vectors.
  • PDF
    Network embeddings map the nodes of a given network into $d$-dimensional Euclidean space $\mathbb{R}^d$. Ideally, this mapping is such that `similar' nodes are mapped onto nearby points, such that the embedding can be used for purposes such as link prediction (if `similar' means being `more likely to be connected') or classification (if `similar' means `being more likely to have the same label'). In recent years various methods for network embedding have been introduced. These methods all follow a similar strategy, defining a notion of similarity between nodes (typically deeming nodes more similar if they are nearby in the network in some metric), a distance measure in the embedding space, and minimizing a loss function that penalizes large distances for similar nodes or small distances for dissimilar nodes. A difficulty faced by existing methods is that certain networks are fundamentally hard to embed due to their structural properties, such as (approximate) multipartiteness, certain degree distributions, or certain kinds of assortativity. Overcoming this difficulty, we introduce a conceptual innovation to the literature on network embedding, proposing to create embeddings that maximally add information with respect to such structural properties (e.g. node degrees, block densities, etc.). We use a simple Bayesian approach to achieve this, and propose a block stochastic gradient descent algorithm for fitting it efficiently. Finally, we demonstrate that the combination of information such structural properties and a Euclidean embedding provides superior performance across a range of link prediction tasks. Moreover, we demonstrate the potential of our approach for network visualization.
  • PDF
    This paper studies the unconditional strong convergence rate for a fully discrete scheme of semilinear stochastic evolution equations, under a generalized Lipschitz-type condition on both drift and diffusion operators. Applied to the one-dimensional stochastic advection-diffusion-reaction equation with multiplicative white noise, the main theorem shows that the spatial and temporal strong convergence orders are $1/2$ and $1/4$, respectively. This is the first optimal strong approximation result for semilinear SPDEs with gradient term driven by non-trace class noises. Numerical tests are performed to verify theoretical analysis.
  • PDF
    A dessin d'enfant, or dessin, is a bicolored graph embedded into a Riemann surface. Acyclic dessins can be described analytically by pre-images of certain polynomials, called Shabat polynomials, and also algebraically by their monodromy groups, that is, the group generated by rotations of edges about black and white vertices. In this paper we investigate the Shabat polynomials and monodromy groups of planar acyclic dessins that are uniquely determined by their passports.
  • PDF
    Principal Component Analysis (PCA) finds the best linear representation of data, and is an indispensable tool in many learning and inference tasks. Classically, principal components of a dataset are interpreted as the directions that preserve most of its "energy", an interpretation that is theoretically underpinned by the celebrated Eckart-Young-Mirsky Theorem. This paper introduces many other ways of performing PCA, with various geometric interpretations, and proves that the corresponding family of non-convex programs have no spurious local optima; these programs therefore behave like convex problems and are amenable to a variety of convex solvers. Beyond providing new geometric interpretations and enhancing our theoretical understanding of PCA, our findings might pave the way for entirely new approaches to structured dimensionality reduction, such as sparse PCA and nonnegative matrix factorisation. More specifically, we study an unconstrained formulation of PCA using determinant optimisation that might provide an elegant alternative to the deflating scheme, commonly used in sparse PCA.
  • PDF
    Deep networks, especially Convolutional Neural Networks (CNNs), have been successfully applied in various areas of machine learning as well as to challenging problems in other scientific and engineering fields. This paper introduces Butterfly-Net, a low-complexity CNN with structured hard-coded weights and sparse across-channel connections, which aims at an optimal hierarchical function representation of the input signal. Theoretical analysis of the approximation power of Butterfly-Net to the Fourier representation of input data shows that the error decays exponentially as the depth increases. Due to the ability of Butterfly-Net to approximate Fourier and local Fourier transforms, the result can be used for approximation upper bound for CNNs in a large class of problems. The analysis results are validated in numerical experiments on the approximation of a 1D Fourier kernel and of solving a 2D Poisson's equation.
  • PDF
    For one parameter subgroup action on a finite volume homogeneous space, we consider the set of points admitting divergent on average trajectories. We show that the Hausdorff dimension of this set is strictly less than the manifold dimension of the homogeneous space. As a corollary we know that the Hausdorff dimension of the set of points admitting divergent trajectories is not full, which proves a conjecture of Y. Cheung.
  • PDF
    When confronted with massive data streams, summarizing data with dimension reduction methods such as PCA raises theoretical and algorithmic pitfalls. Principal curves act as a nonlinear generalization of PCA and the present paper proposes a novel algorithm to automatically and sequentially learn principal curves from data streams. We show that our procedure is supported by regret bounds with optimal sublinear remainder terms. A greedy local search implementation that incorporates both sleeping experts and multi-armed bandit ingredients is presented, along with its regret bound and performance on a toy example and seismic data.
  • PDF
    A major challenge in the study of dynamical systems is that of model discovery: turning data into models that are not just predictive, but provide insight into the nature of the underlying dynamical system that generated the data. This problem is made more difficult by the fact that many systems of interest exhibit diverse behaviors across multiple time scales. We introduce a number of data-driven strategies for discovering nonlinear multiscale dynamical systems and their embeddings from data. We consider two canonical cases: (i) systems for which we have full measurements of the governing variables, and (ii) systems for which we have incomplete measurements. For systems with full state measurements, we show that the recent sparse identification of nonlinear dynamical systems (SINDy) method can discover governing equations with relatively little data and introduce a sampling method that allows SINDy to scale efficiently to problems with multiple time scales. Specifically, we can discover distinct governing equations at slow and fast scales. For systems with incomplete observations, we show that the Hankel alternative view of Koopman (HAVOK) method, based on time-delay embedding coordinates, can be used to obtain a linear model and Koopman invariant measurement system that nearly perfectly captures the dynamics of nonlinear quasiperiodic systems. We introduce two strategies for using HAVOK on systems with multiple time scales. Together, our approaches provide a suite of mathematical strategies for reducing the data required to discover and model nonlinear multiscale systems.
  • PDF
    We construct a statistical indicator for the detection of short-term asset price bubbles based on the information content of bid and ask market quotes for plain vanilla put and call options. Our construction makes use of the martingale theory of asset price bubbles and the fact that such scenarios where the price for an asset exceeds its fundamental value can in principle be detected by analysis of the asymptotic behavior of the implied volatility surface. For extrapolating this implied volatility, we choose the SABR model, mainly because of its decent fit to real option market quotes for a broad range of maturities and its ease of calibration. As main theoretical result, we show that under lognormal SABR dynamics, we can compute a simple yet powerful closed-form martingale defect indicator by solving an ill-posed inverse calibration problem. In order to cope with the ill-posedness and to quantify the uncertainty which is inherent to such an indicator, we adopt a Bayesian statistical parameter estimation perspective. This allows us to incorporate any available prior knowledge in a fully explicit way. We probe the resulting posterior densities with a combination of optimization and adaptive Markov chain Monte Carlo methods, thus providing a full-blown uncertainty estimation of all the underlying parameters and the martingale defect indicator. Finally, we provide a real-market test of the proposed option-based indicator.
  • PDF
    We study the set of continuous functions that admit no spurious local optima (i.e. local minima that are not global minima) which we term \textitglobal functions. They satisfy various powerful properties for analyzing nonconvex and nonsmooth optimization problems. For instance, they satisfy a theorem akin to the fundamental uniform limit theorem in the analysis regarding continuous functions. Global functions are also endowed with useful properties regarding the composition of functions and change of variables. Using these new results, we show that a class of nonconvex and nonsmooth optimization problems arising in tensor decomposition applications are global functions. This is the first result concerning nonconvex methods for nonsmooth objective functions. Our result provides a theoretical guarantee for the widely-used $\ell_1$ norm to avoid outliers in nonconvex optimization.
  • PDF
    Kleinian singularities, i.e., the varieties corresponding to the algebras of invariants of Kleinian groups are of fundamental importance for Algebraic geometry, Representation theory and Singularity theory. The filtered deformations of these algebras of invariants were classified by Slodowy (the commutative case) and Losev (the general case). To an inclusion of Kleinian groups, there is the corresponding inclusion of algebras of invariants. We classify deformations of these inclusions when a smaller subgroup is normal in the larger.
  • PDF
    We introduce new techniques allowing one to construct diagonals of bounded Hilbert space operators and operator tuples under "Blaschke-type" assumptions. This provides a new framework for a number of results in the literature and identifies, often large, subsets in the set of diagonals of arbitrary bounded operators (and their tuples). Moreover, our approach leads to substantial generalizations of the results due to Bourin, Herrero and Stout having assumptions of a similar nature.
  • PDF
    We compute the $GL_{r+1}$-equivariant Chow class of the $GL_{r+1}$-orbit closure of any point $(x_1, \ldots, x_n) \in (\mathbb{P}^r)^n$ in terms of the rank polytope of the matroid represented by $x_1, \ldots, x_n \in \mathbb{P}^r$. Using these classes and generalizations involving point configurations in higher dimensional projective spaces, we define for each $d\times n$ matrix $M$ an $n$-ary operation $[M]_\hbar$ on the small equivariant quantum cohomology ring of $\mathbb{P}^r$, which is the $n$-ary quantum product when $M$ is an invertible matrix. We prove that $M \mapsto [M]_\hbar$ is a valuative matroid polytope association. Like the quantum product, these operations satisfy recursive properties encoding solutions to enumerative problems involving point configurations of given moduli in a relative setting. As an application, we compute the number of line sections with given moduli of a general degree $2r+1$ hypersurface in $\mathbb{P}^r$, generalizing the known case of quintic plane curves.
  • PDF
    We confirm Huh's conjectural list of all projective hypersurfaces with isolated singularities and polar degree equal to 2. We prove a precise version of a general conjecture on the polar degree stated by Huh.
  • PDF
    In this work, we describe the geometric and probabilistic properties of a noncommutative 2- torus in a magnetic field. We study the volume invariance, integrated scalar curvature and volume form by using the method of perturbation by inner derivation of the magnetic Laplacian in the noncommutative 2-torus. Then, we analyze the magnetic stochastic process describing the motion of a particle subject to a uniform magnetic field on the noncommutative 2-torus, derive and discuss the related main properties.
  • PDF
    Suppose that $T^*$ is an $\omega_1$-Aronszajn tree with no stationary antichain. We introduce a forcing axiom PFA($T^*$) for proper forcings which preserve these properties of $T^*$. We prove that PFA($T^*$) implies many of the strong consequences of PFA, such as the failure of very weak club guessing, that all of the cardinal characteristics of the continuum are greater than $\omega_1$, and the $P$-ideal dichotomy. On the other hand, PFA($T^*$) implies some of the consequences of diamond principles, such as the existence of Knaster forcings which are not stationarily Knaster.
  • PDF
    Suppose $(B,\pi)$ is an open book supporting $(Y,\xi)$, where the binding $B$ is possibly disconnected, and $K$ is a braid about this open book. Then $B\cup K$ is naturally a transverse link in $(Y,\xi)$. We prove that the transverse link invariant in knot Floer homology, \[\widehatt(B∪K)∈\widehatHFK(-Y,B∪K),\]defined in [BVV13] is always nonzero. This generalizes the main results of Etnyre and Vela-Vick in [VV11, EVV10]. As an application, we show that if $K$ is braided about an open book with connected binding, and has fractional Dehn twist coefficient greater than one, then $\widehat{t}(K)\ne 0$. This generalizes a result of Plamenevskaya [PLA15] for classical braids.
  • PDF
    Firstly, we shall introduce the so-called snapping out Walsh's Brownian motion and present its relation with Walsh's Brownian motion. Then the stiff problem related to Walsh's Brownian motion will be described and we shall build a phase transition for it. The snapping out Walsh's Brownian motion corresponds to the so-called semi-permeable pattern of this stiff problem.
  • PDF
    There are only 10 Euclidean forms, that is flat closed three dimensional manifolds: six are orientable and four are non-orientable. The aim of this paper is to describe all types of $n$-fold coverings over orientable Euclidean manifolds $\mathcal{G}_{2}$ and $\mathcal{G}_{4}$, and calculate the numbers of non-equivalent coverings of each type. We classify subgroups in the fundamental groups $\pi_1(\mathcal{G}_{2})$ and $\pi_1(\mathcal{G}_{4})$ up to isomorphism and calculate the numbers of conjugated classes of each type of subgroups for index $n$. The manifolds $\mathcal{G}_{2}$ and $\mathcal{G}_{4}$ are uniquely determined among the others orientable forms by their homology groups $H_1(\mathcal{G}_{2})=\mathbb{Z}_2\times \mathbb{Z}_2 \times \mathbb{Z}$ and $H_1(\mathcal{G}_{4})=\mathbb{Z}_2 \times \mathbb{Z}$.
  • PDF
    For a Distributed Storage System (DSS), the \textitFractional Repetition (FR) code is a class in which replicas of encoded data packets are stored on distributed chunk servers, where the encoding is done using the Maximum Distance Separable (MDS) code. The FR codes allow for exact uncoded repair with minimum repair bandwidth. In this paper, FR codes are constructed using finite binary sequences. The condition for universally good FR codes is calculated on such sequences. For some sequences, the universally good FR codes are explored.
  • PDF
    For a graph $G$ with vertex set $V(G)$, the Steiner distance $d(S)$ of $S\subseteq V(G)$ is the smallest number of edges in a connected subgraph of $G$ that contains $S$. Such a subgraph is necessarily a tree called a Steiner tree for $S$. The Steiner distance is a type of multi-way metric measuring the size of a Steiner tree between vertices of a graph and it generalizes the geodetic distance. The Steiner Wiener index is the sum of all Steiner distances in a graph and it generalizes the Wiener index. A simple method for calculating the Steiner Wiener index of block graphs is presented.
  • PDF
    We prove $W^{2,\varepsilon}$ estimates for viscosity supersolutions of fully nonlinear, uniformly elliptic equations where $\varepsilon$ decays polynomially with respect to the ellipticity ratio of the equations.
  • PDF
    The Laplace operator $\mathcal{L}$ is discontinuous from $L^{p}\left(\mathbb{R}_{+}\right)$ into $L^{q}\left(\mathbb{R}_{+}\right)$ unless $1\leq p\leq 2$ and $q$ is its conjugate Lebesgue exponent. To better understand where this discontinuity comes from, we investigate two separate weaker problems: $$ \mathcalL:L^p\left(\mathbbR_+\right) \longrightarrow L^q\left(\Omega\right),\u2009\Omega⊂\mathbbR_+\:\textis bounded and measurable,\qquad (I)$$ $$ \mathcalL:L^p\left(\mathbbR_+\right)\longrightarrow L^q\left([s,∞[\,\right),\u2009s>0.,\qquad (II) $$ It turns out (I) holds true precisely if $\,\frac{1}{p}+\frac{1}{q}>1\,$ or $\,\frac{1}{p}+\frac{1}{q}=1,\,1\leq p \leq 2$, whereas (II) is valid precisely if $\,\frac{1}{p}+\frac{1}{q}<1\,$ or $\,\frac{1}{p}+\frac{1}{q}=1,\,1\leq p \leq 2$. Consequently, neither (I) nor (II) is true whenever $\,\frac{1}{p}+\frac{1}{q}=1,\,2< p \leq \infty$.
  • PDF
    We survey some recent works on standard Young tableaux of bounded height. We focus on consequences resulting from numerous bijections to lattice walks in Weyl chambers.

Recent comments

Stefano Pirandola Apr 23 2018 12:23 UTC

The most important reading here is Sam Braunstein's foundational paper: https://authors.library.caltech.edu/3827/1/BRAprl98.pdf published in January 98, already containing the key results for the strong convergence of the CV protocol. This is a must-read for those interested in CV quantum informatio

...(continued)
Mark M. Wilde Apr 23 2018 12:09 UTC

One should also consult my paper "Strong and uniform convergence in the teleportation simulation of bosonic Gaussian channels" https://arxiv.org/abs/1712.00145v4 posted in January 2018, in this context.

Stefano Pirandola Apr 23 2018 11:46 UTC

Some quick clarifications on the Braunstein-Kimble (BK) protocol for CV teleportation
and the associated teleportation simulation of bosonic channels.
(Disclaimer: the following is rather technical and CVs might not be so popular on this blog...so I guess this post will get a lot of dislikes :)

1)

...(continued)
Danial Dervovic Mar 01 2018 12:08 UTC

Hello again Māris, many thanks for your patience. Your comments and questions have given me much food for thought, and scope for an amended version of the paper -- please see my responses below.

Please if any of the authors of [AST17 [arXiv:1712.01609](https://arxiv.org/abs/1712.01609)] have any fu

...(continued)
Danial Dervovic Feb 05 2018 15:03 UTC

Thank you Māris for the extremely well thought-out and articulated points here.

I think this very clearly highlights the need to think explicitly about the precompute time if using the lifting to directly simulate the quantum walk, amongst other things.

I wish to give a well-considered respons

...(continued)
Māris Ozols Feb 01 2018 17:53 UTC

This paper considers the problem of using "lifted" Markov chains to simulate the mixing of coined quantum walks. The Markov chain has to approximately (in the total variational distance) sample from the distribution obtained by running the quantum walk for a randomly chosen time $t \in [0,T]$ follow

...(continued)
Marco Piani Jan 28 2018 11:21 UTC

Hi Mizanur,

thanks to you for taking into account my comment. I am not sure of the jargon and nomenclature in mathematics; are/were the maps that are completely positive and also completely co-positive known as PPT maps? What I was pointing out is that in the quantum information community the nam

...(continued)
Mizanur Rahaman Jan 27 2018 19:06 UTC

Hi Marco, thanks for pointing out the possible confusion. I will make it clear in the revised version. I think in this context what I should clearly state is that I am considering linear maps
which are completely positive and co-completely positive, that is, the map \Phi and \Phi\circleT
are compl

...(continued)
Marco Piani Jan 24 2018 03:34 UTC

Great work! One thing that might potentially confuse readers is the use of "PPT channel" to indicate that the partial action of the channel produces a PPT state. There might be some ambiguity in literature, but many call "PPT channels" those channels that act jointly on two parties, and that preserv

...(continued)
Mizanur Rahaman Jan 23 2018 23:20 UTC

Thanks for the comment. I was not aware of the "entanglement breaking index" paper.
I will include it in a revised version. I will make a remark about the other deduction as well.
Thanks.