New results on multi-dimensional linear discriminant analysis

Fisher linear discriminant analysis is a well-known technique for dimensionality reduction and classification. The method was first formulated in 1936 by Fisher. In this paper we concentrate on three different formulations of the multi-dimensional problem. We provide a mathematical explanation why two of the formulations are equivalent and prove that this equivalency can be extended to a broader class of objective functions. The second contribution is a rate of convergence of a fixed point method for solving the third model.     

Extragradient and extrapolation methods with generalized Bregman distances for saddle point problems

In this paper, we introduce two Bregman-type algorithmic frameworks to generalize the extragradient and extrapolation methods. With the help of relative Lipschitzness and the Bregman distance tool, the iteration properties of the proposed frameworks are analyzed. As applied to smooth convex-concave saddle point problems, our theory rediscovers the main results in Mokhtari et al. (2020) [14] for wider frameworks under weaker assumptions via a conceptually different approach.     

Range-Renewal Processes: SLLNs and Power Laws*

Given n samples(viewed as an n-tuple) of a γ-regular discrete distribution π,in this article the authors concern with the weighted and unweighted graphs induced by the n samples. They first prove a series of SLLN results(of Dvoretzky-Erd¨os’ type). Then they show that the vertex weights of the graphs under investigation obey asymptotically power law distributions with exponent 1 + γ. They also give a conjecture that the degrees of unweighted graphs would exhibit asymptotically power law distribu...     

Efficient simulation of general stochastic hybrid systems

General Stochastic Hybrid System (SHS) are characterised by Stochastic Differential Equations (SDEs) with discontinuities and Poisson jump processes. SHS are useful in model based design of Cyber-Physical System (CPS) controllers under uncertainty. Industry standard model based design tools such as Simulink/Stateflow® are inefficient when simulating, testing, and validating SHS, because of dependence on fixed-step Euler–Maruyama (EM) integration and discontinuity detection. We present a novel efficient adaptive step-size simulation/integration technique for general SHSs modelled as a network of Stochastic Hybrid Automatons (SHAs). We propose a simulation algorithm where each SHA in the network executes synchronously with the other, at an integration step-size computed using adaptive step-size integration. Ito’ multi-dimensional lemma and the inverse sampling theorem are leveraged to compute the integration step-size by making the SDEs and Poisson jump rate integration dependent upon discontinuities. Existence and convergence analysis along with experimental results show that the proposed technique is substantially faster than Simulink/Stateflow®when simulating general SHSs.     

Controllability of the wave equation with moving point control

This paper deals with approximate and exact controllability of the wave equation in finite time with interior point control acting along a curve specified in advance in the system's spatial domain. The structure of the control input is dual to the structure of the observations which describe the measurements of velocity and gradient of the solution of the dual system, obtained from the moving point sensor. A relevant formalization of such a control problem is discussed, based on transposition. For any given timeinterval [0,T] the existence of the curves providing approximate controllability inH _D ^–[n/2]–1 ()×H _D ^–[n/2]–1 () (wheren stands for the space dimension) is established with controls fromL ²(0,T; R ⁿ +1). The same curves ensure exact controllability inL ²() × H^–1() if controls are allowed to be selected in [L (0,T; R ⁿ+1)]. Required curves can be constructed to be continuous on [0,T).This work was supported in part by NSF Grant ECS 89-13773 and NASA Grant NAG-1-1081.     

Randomized algorithms for the separation of point sets and for solving quadratic programs

A randomized algorithm for finding a hyperplane separating two finite point sets in the Euclidean space ^d and a randomized algorithm for solving linearly constrained general convex quadratic problems are proposed. The expected running time of the separating algorithm isO(dd! (m + n)), wherem andn are cardinalities of sets to be separated. The expected running time of the algorithm for solving quadratic problems isO(dd! s) wheres is the number of inequality constraints. These algorithms are based on the ideas of Seidel's linear programming algorithm [6]. They are closely related to algorithms of [8], [2], and [9] and belong to an abstract class of algorithms investigated in [1]. The algorithm for solving quadratic problems has some features of the one proposed in [7].This research was done when the author was supported by the Alexander von Humboldt Foundation, Germany.On leave from the Institute of Mathematics and Mechanics, Ural Department of the Russian Academy of Sciences, 620219 Ekaterinburg, S. Kovalevskaya str. 16, Russia.     

Covering with blocks in the non-symmetric case

Considering an infinite string of i.i.d. random letters drawn from a finite alphabet we define the cover timeW _n as the number of random letters needed until each pattern of lenghtn appears at least once as a substring. Sharp weak and a.s. limit results onW _n are known in the symmetric case, i.e., when the random letters are uniformly distributed over the alphabet. In this paper we determine the limit distribution ofW _n in the nonsymmetric case asn. Generalizations in terms of point processes are also proved.Dedicated to Endre Csáki on his 60th birthday.     

New results for diffusion in Lorentz lattice gas cellular automata

New calculations to over ten million time steps have revealed a more complex diffusive behavior than previously reported of a point particle on a square and triangular lattice randomly occupied by mirror or rotator scatterers. For the square lattice fully occupied by mirrors where extended closed particle orbits occur, anomalous diffusion was still found. However, for a not fully occupied lattice the superdiffusion, first noticed by Owczarek and Prellberg for a particular concentration, obtains for all concentrations. For the square lattice occupied by rotators and the triangular lattice occupied by mirrors or rotators, an absence of diffusion (trapping) was found for all concentrations, except on critical lines, where anomalous diffusion (extended closed orbits) occurs and hyperscaling holds for all closed orbits withuniversal exponentsd _f =7/4 and =15/7. Only one point on these critical lines can be related to a corresponding percolation problem. The questions arise therefore whether the other critical points can be mapped onto a new percolation-like problem and of the dynamical significance of hyperscaling.     

Stochastic phase lockings in a relaxation oscillator forced by a periodic input with additive noise: A first-passage-time approach

Noise effects on phase lockings in a system consisting of a piecewise-linear van der Pol relaxation oscillator driven by a periodic input are studied. The problem of finding the period of the oscillator is reduced to the first-passage-time problem of the Ornstein-Uhlenbeck process with time-varying boundary. The probability density functions of the first-passage time are used to define the operator which governs a transition of an input phase density after one cycle of the oscillator. Phase lockings in a stochastic sense are investigated on the basis of the density evolution by the operator.     

A law of the iterated logarithm for processes with independent increments

ＡＬＡＷＯＦＴＨＥＩＴＥＲＡＴＥＤＬＯＧＡＲＩＴＨＭＦＯＲＰＲＯＣＥＳＳＥＳＷＩＴＨＩＮＤＥＰＥＮＤＥＮＴＩＮＣＲＥＭＥＮＴＳＷＡＮＧＪＩＡＧＡＮＧ（汪嘉冈）（ＥａｓｔＣｈｉｎａＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ,Ｓｈａｎｇ...