Root n estimates of vectors of integrated density partial derivative functionals

Based on a random sample of size \(n\) from an unknown \(d\) -dimensional density \(f\) , the nonparametric estimations of a single integrated density partial derivative functional as well as a vector of such functionals are considered. These single and vector functionals are important in a number of contexts. The purpose of this paper is to derive the information bounds for such estimations and propose estimates that are asymptotically optimal. The proposed estimates are constructed in the frequency domain using the sample characteristic function. For every \(d\) and sufficiently smooth \(f\) , it is shown that the proposed estimates are asymptotically normal, attain the optimal \(O_p(n^{-1/2})\) convergence rate and achieve the (conjectured) information bounds. In simulation studies the superior performances of the proposed estimates are clearly demonstrated.     

On Packing \mathbb {R}^3 with Thin Tori

We show that $\mathbb {R}^3$ can be packed at a density of $0.222\ldots $ with tori whose minor radius goes to zero. Furthermore, we show that the same torus arrangement yields an asymptotically optimal number of pairwise-linked tori.     

Existence of Wave Operators with Time-Dependent Modifiers for the Schrödinger Equations with Long-Range Potentials on Scattering Manifolds

We construct time-dependent wave operators for Schrödinger equations with long-range potentials on a manifold M with asymptotically conic structure. We use the two space scattering theory formalism, and a reference operator on a space of the form ${\mathbb{R} \times \partial M}$ , where ${\partial M}$ is the boundary of M at infinity. We construct exact solutions to the Hamilton–Jacobi equation on the reference system ${\mathbb{R} \times \partial M}$ and prove the existence of the modified wave operators.     

Abandonment versus blocking in many-server queues: asymptotic optimality in the QED regime

We consider a controlled queueing system of the $G/M/n/B+GI$ G / M / n / B + G I type, with many servers and impatient customers. The queue-capacity $B$ B is the control process. Customers who arrive at a full queue are blocked and customers who wait too long in the queue abandon. We study the tradeoff between blocking and abandonment, with cost accumulated over a random, finite time-horizon, which yields a queueing control problem (QCP). In the many-server quality and efficiency-driven (QED) regime, we formulate and solve a diffusion control problem (DCP) that is associated with our QCP. The DCP solution is then used to construct asymptotically optimal controls (of the threshold type) for QCP. A natural motivation for our QCP is telephone call centers, hence the QED regime is natural as well. QCP then captures the tradeoff between busy signals and customer abandonment, and our solution specifies an asymptotically optimal number of trunk-lines.     

Sample average approximation of stochastic dominance constrained programs

In this paper we study optimization problems with second-order stochastic dominance constraints. This class of problems allows for the modeling of optimization problems where a risk-averse decision maker wants to ensure that the solution produced by the model dominates certain benchmarks. Here we deal with the case of multi-variate stochastic dominance under general distributions and nonlinear functions. We introduce the concept of ${\mathcal{C}}$ -dominance, which generalizes some notions of multi-variate dominance found in the literature. We apply the Sample Average Approximation (SAA) method to this problem, which results in a semi-infinite program, and study asymptotic convergence of optimal values and optimal solutions, as well as the rate of convergence of the feasibility set of the resulting semi-infinite program as the sample size goes to infinity. We develop a finitely convergent method to find an ${\epsilon}$ -optimal solution of the SAA problem. An important aspect of our contribution is the construction of practical statistical lower and upper bounds for the true optimal objective value. We also show that the bounds are asymptotically tight as the sample size goes to infinity.     

Sensitivity of best recovery in the Sobolev spaces W_\infty ^{r,d} , \widetilde W_\infty ^{r,d}for perturbed sampling

Let $I^d $ be the d‐dimensional cube, $I^d = [0,1]^d $ , and let $F \ni f \mapsto Sf \in L_\infty (I^d ) $ be a linear operator acting on the Sobolev space F, where Fis either $$$$ or $$$$ where $$\left\| f \right\|_F = \sum\limits_{\left| m \right| = r} {\mathop {{\text{esssup}}}\limits_{x \in I^d } \left| {\frac{{\partial f^{\left| m \right|} }} {{\partial x_1^{m_1 } \partial x_2^{m_2 } \cdot \cdot \cdot \partial x_d^{m_d } }}(x)} \right|.} $$ We assume that the problem elements fsatisfy the condition $\sum\nolimits_{\left| m \right| = r} {{\text{esssup}}} _{x \in I^d } \left| {f^{(m)} (x)} \right| \leqslant 1 $ and that Sis continuous with respect to the supremum norm. We study sensitivity of optimal recovery of Sfrom inexact samples of ftaken at npoints forming a uniform grid on $I^d $ . We assume that the inaccuracy in reading the sample vector is measured in the pth norm and bounded by a nonnegative number δ. The sensitivity is defined by the difference between the optimal errors corresponding to the exact and perturbed readings, respectively. Our main result is that this difference is bounded by $\mathcal{A}\delta $ , where $\mathcal{A} $ is a positive constant independent of the number of samples. This indicates that the curse of dimension, which badly affects the optimal errors, does not extend to sensitivity.     

Guaranteed clustering and biclustering via semidefinite programming

Identifying clusters of similar objects in data plays a significant role in a wide range of applications. As a model problem for clustering, we consider the densest \(k\) -disjoint-clique problem, whose goal is to identify the collection of \(k\) disjoint cliques of a given weighted complete graph maximizing the sum of the densities of the complete subgraphs induced by these cliques. In this paper, we establish conditions ensuring exact recovery of the densest \(k\) cliques of a given graph from the optimal solution of a particular semidefinite program. In particular, the semidefinite relaxation is exact for input graphs corresponding to data consisting of \(k\) large, distinct clusters and a smaller number of outliers. This approach also yields a semidefinite relaxation with similar recovery guarantees for the biclustering problem. Given a set of objects and a set of features exhibited by these objects, biclustering seeks to simultaneously group the objects and features according to their expression levels. This problem may be posed as that of partitioning the nodes of a weighted bipartite complete graph such that the sum of the densities of the resulting bipartite complete subgraphs is maximized. As in our analysis of the densest \(k\) -disjoint-clique problem, we show that the correct partition of the objects and features can be recovered from the optimal solution of a semidefinite program in the case that the given data consists of several disjoint sets of objects exhibiting similar features. Empirical evidence from numerical experiments supporting these theoretical guarantees is also provided.     

Linear deviations of the classes\tilde W_p^\alpha and approximations in spaces of multipliers

We consider the problem of the asymptotically best linear method of approximation in the metric of L_s[?π, π] of the set \(\tilde W_p^\alpha (1)\) of periodic functions with a bounded in L_p[?π, π] fractional derivative, by functions from \(\tilde W_p^\beta (M)\) ,β >α, for sufficiently large M, and the problem about the best approximation in L_s[?π, π] of the operator of differentiation on \(\tilde W_p^\alpha (1)\) by continuous linear operators whose norm (as operators from L_r[?π, π] into L_q[?π, π])does not exceed M. These problems are reduced to the approximation of an individual element in the space of multipliers, and this allows us to obtain estimates that are exact in the sense of the order.     

An approach to constrained global optimization based on exact penalty functions

In the field of global optimization many efforts have been devoted to solve unconstrained global optimization problems. The aim of this paper is to show that unconstrained global optimization methods can be used also for solving constrained optimization problems, by resorting to an exact penalty approach. In particular, we make use of a non-differentiable exact penalty function ${P_q(x;\varepsilon)}$ . We show that, under weak assumptions, there exists a threshold value ${\bar \varepsilon >0 }$ of the penalty parameter ${\varepsilon}$ such that, for any ${\varepsilon \in (0, \bar \varepsilon]}$ , any global minimizer of P _q is a global solution of the related constrained problem and conversely. On these bases, we describe an algorithm that, by combining an unconstrained global minimization technique for minimizing P _q for given values of the penalty parameter ${\varepsilon}$ and an automatic updating of ${\varepsilon}$ that occurs only a finite number of times, produces a sequence {x ^k } such that any limit point of the sequence is a global solution of the related constrained problem. In the algorithm any efficient unconstrained global minimization technique can be used. In particular, we adopt an improved version of the DIRECT algorithm. Some numerical experimentation confirms the effectiveness of the approach.     

Decomposition of Geodesics in the Wasserstein Space and the Globalization Problem

We will prove a decomposition for Wasserstein geodesics in the following sense: let (X, d, m) be a non-branching metric measure space verifying ${\mathsf{CD}_{loc}(K,N)}$ or equivalently ${\mathsf{CD}^{*}(K,N)}$ . We prove that every geodesic ${\mu_{t}}$ in the L ²-Wasserstein space, with ${\mu_{t} \ll m}$ , is decomposable as the product of two densities, one corresponding to a geodesic with support of codimension one verifying ${\mathsf{CD}^{*}(K,N-1)}$ , and the other associated with a precise one dimensional measure, provided the length map enjoys local Lipschitz regularity. The motivation for our decomposition is in the use of the component evolving like ${\mathsf{CD}^{*}}$ in the globalization problem. For a particular class of optimal transportation we prove the linearity in time of the other component, obtaining therefore the global ${\mathsf{CD}(K,N)}$ for ${\mu_{t}}$ . The result can be therefore interpret as a globalization theorem for ${\mathsf{CD}(K,N)}$ for this class of optimal transportation, or as a “self-improving property” for ${\mathsf{CD}^{*}(K,N)}$ . Assuming more regularity, namely in the setting of infinitesimally strictly convex metric measure space, the one dimensional density is the product of two differentials giving more insight on the density decomposition.     

Unified optimization of \hbox {H}_{\infty } index and upper stability bound for singularly perturbed systems

In this paper, unified optimization problem for the upper stability bound \(\varepsilon ^{*}\) and the \(\hbox {H}_{\infty }\) performance index \(\gamma \) based on state feedback is considered for singularly perturbed systems. First, a sufficient condition for the existence of state feedback controller is presented in terms of linear matrix inequalities such that the resulting closed-loop system is asymptotically stable if \(0<\varepsilon <\varepsilon ^{*}\) and also guarantees \(\hbox {H}_{\infty }\) performance index. Furthermore, a new algorithm to optimize these two indices simultaneously is proposed based on Nash game theory which transfers multi-objective problem into a single objective problem as well we determines the objective weights. Then an optimal state feedback controller can be derived. Finally, some numerical examples are provided to demonstrate the effectiveness and correctness of the proposed results.     

Global solutions of non-Lipschitz S_{2}–S_{p} minimization over the positive semidefinite cone

The \(S_2\) – \(S_p\) minimization over the positive semidefinite cone is the semidefinite least squares problem with Schatten \(p\) -quasi ( \(0 ) norm regularization term. It has wide applications in many areas including compressed sensing, control, statistics, signal and image processing, etc. In this paper, by developing the symmetric matrix \(\mathrm {p}\) -thresholding operator representation theory, we establish the necessary condition for global optimal solutions of \(S_2\) – \(S_p\) minimization, and also provide the exact lower bound for the positive eigenvalues at global optimal solutions.     

Horoball packings to the totally asymptotic regular simplex in the hyperbolic n-space

In Szirmai (Acta Mathematica Hungarica 136/1-2:39–55, 2012) we generalized the notion of simplicial density function for horoballs in the extended hyperbolic space ${\overline{\mathbf{H}}^3}$ , where we allowed horoballs in different types centered at various vertices of a totally asymptotic tetrahedron. By this new aspect, in this paper we study the locally densest horoball packing arrangements and their densities with respect to totally asymptotic regular simplices in the hyperbolic n-space ${\overline{\mathbf{H}}^n}$ extended with its absolute figure, where the ideal centers of horoballs lie in the vertices of a totally asymptotic regular tetrahedron. We will prove that, in this sense, the well known Böröczky–Florian density upper bound for “congruent ball and horoball” packings of ${\overline{\mathbf{H}}^3}$ does not remain valid for the analogous packing of ${\overline{\mathbf{H}}^n}$ , for n ≥ 4. Although locally optimal ball arrangements do not seem to have extensions to the whole n-dimensional hyperbolic space. Moreover, we determine an explicit formula for the density of the above locally optimal horoball packings, allowing horoballs of different types (i.e. they are differently packed in their ideal simplex).     

Asymptotics of Discrete Riesz d-Polarization on Subsets of d-Dimensional Manifolds

We prove a conjecture of T. Erdélyi and E.B. Saff, concerning the form of the dominant term (as N?→?∞) of the N-point Riesz d-polarization constant for an infinite compact subset A of a d-dimensional C ¹-manifold embedded in ? ^m (d?≤?m). Moreover, if we assume further that the d-dimensional Hausdorff measure of A is positive, we show that any asymptotically optimal sequence of N-point configurations for the N-point d-polarization problem on A is asymptotically uniformly distributed with respect to \(\mathcal H_d|_A\) . These results also hold for finite unions of such sets A provided that their pairwise intersections have \(\mathcal H_d\) -measure zero.     

ParNes: a rapidly convergent algorithm for accurate recovery of sparse and approximately sparse signals

In this article, we propose an algorithm, nesta-lasso, for the lasso problem, i.e., an underdetermined linear least-squares problem with a 1-norm constraint on the solution. We prove under the assumption of the restricted isometry property (rip) and a sparsity condition on the solution, that nesta-lasso is guaranteed to be almost always locally linearly convergent. As in the case of the algorithm nesta, proposed by Becker, Bobin, and Candès, we rely on Nesterov’s accelerated proximal gradient method, which takes $O(\sqrt {1/\varepsilon })$ iterations to come within $\varepsilon > 0$ of the optimal value. We introduce a modification to Nesterov’s method that regularly updates the prox-center in a provably optimal manner. The aforementioned linear convergence is in part due to this modification. In the second part of this article, we attempt to solve the basis pursuit denoising (bpdn) problem (i.e., approximating the minimum 1-norm solution to an underdetermined least squares problem) by using nesta-lasso in conjunction with the Pareto root-finding method employed by van den Berg and Friedlander in their spgl1 solver. The resulting algorithm is called parnes. We provide numerical evidence to show that it is comparable to currently available solvers.     

Multiplicity of periodic solutions to symmetric delay differential equations

By applying the method based on the usage of the equivariant gradient degree introduced by G?ba (1997) and the cohomological equivariant Conley index introduced by Izydorek (2001), we establish an abstract result for G-invariant strongly indefinite asymptotically linear functionals showing that the equivariant invariant ${\omega(\nabla \Phi)}$ , expressed as that difference of the G-gradient degrees at infinity and zero, contains rich numerical information indicating the existence of multiple critical points of ${\Phi}$ exhibiting various symmetric properties. The obtained results are applied to investigate an asymptotically linear delay differential equation $$x\prime = - \nabla f \big ({x \big (t - \frac{\pi}{2} \big )} \big ), \quad x \in V \qquad \quad (*)$$ (here ${f : V \rightarrow \mathbb{R}}$ is a continuously differentiable function satisfying additional assumptions) with Γ-symmetries (where Γ is a finite group) using a variational method introduced by Guo and Yu (2005). The equivariant invariant ${\omega(\nabla \Phi) = n_{1}({\bf H}_{1}) + n_{2}({\bf H}_{2}) + \cdots + n_{m}({\bf H}_{m})}$ in the case n _k ≠ 0 (for maximal twisted orbit types (H _k )) guarantees the existence of at least |n _k | different G-orbits of periodic solutions with symmetries at least (H _k). This result generalizes the result by Guo and Yu (2005) obtained in the case without symmetries. The existence of large number of nonconstant periodic solutions for (*) (classified according to their symmetric properties) is established for several groups Γ, with the exact value of ${\omega(\,\nabla \Phi)}$ evaluated.     

An exponential inequality for the distribution function of the kernel density estimator, with applications to adaptive estimation

It is shown that the uniform distance between the distribution function $F_n^K(h)$ of the usual kernel density estimator (based on an i.i.d. sample from an absolutely continuous law on ${\mathbb{R}}$ ) with bandwidth h and the empirical distribution function F _n satisfies an exponential inequality. This inequality is used to obtain sharp almost sure rates of convergence of $\|F_n^K(h_n)-F_n\|_\infty$ under mild conditions on the range of bandwidths h _n , including the usual MISE-optimal choices. Another application is a Dvoretzky–Kiefer–Wolfowitz-type inequality for $\|F_n^{K}(h)-F\|_\infty$ , where F is the true distribution function. The exponential bound is also applied to show that an adaptive estimator can be constructed that efficiently estimates the true distribution function F in sup-norm loss, and, at the same time, estimates the density of F—if it exists (but without assuming it does)—at the best possible rate of convergence over Hölder-balls, again in sup-norm loss.     

Hitting Times of Bessel Processes

Let $T_1^{(\mu)}$ be the first hitting time of the point 1 by the Bessel process with index μ?∈?? starting from x?>?1. Using an integral formula for the density $q_x^{(\mu)}(t)$ of $T_1^{(\mu)}$ , obtained in Byczkowski and Ryznar (Stud Math 173(1):19–38, 2006), we prove sharp estimates of the density of $T_1^{(\mu)}$ which exhibit the dependence both on time and space variables. Our result provides optimal uniform estimates for the density of the hitting time of the unit ball by the Brownian motion in ? ⁿ , which improve existing bounds. Another application is to provide sharp estimates for the Poisson kernel for half-spaces for hyperbolic Brownian motion in real hyperbolic spaces.