The use of random weights for the training of multilayer networks of neurons with Heaviside characteristics

Artificial neural networks have, in recent years, been very successfully applied in a wide range of areas. A major reason for this success has been the existence of a training algorithm called backpropagation. This algorithm relies upon the neural units in a network having input/output characteristics that are continuously differentiable. Such units are significantly less easy to implement in silicon than are neural units with Heaviside (step-function) characteristics. In this paper, we show how a training algorithm similar to backpropagation can be developed for 2-layer networks of Heaviside units by treating the network weights (i.e., interconnection strengths) as random variables. This is then used as a basis for the development of a training algorithm for networks with any number of layers by drawing upon the idea of internal representations. Some examples are given to illustrate the performance of these learning algorithms.     

On the parallel complexity of hierarchical clustering and CC‐complete problems

Complex data sets are often unmanageable unless they can be subdivided and simplified in an intelligent manner. Clustering is a technique that is used in data mining and scientific analysis for partitioning a data set into groups of similar or nearby items. Hierarchical clustering is an important and well‐studied clustering method involving both top‐down and bottom‐up subdivisions of data. In this article we address the parallel complexity of hierarchical clustering. We describe known sequential algorithms for top‐down and bottom‐up hierarchical clustering. The top‐down algorithm can be parallelized, and when there are n points to be clustered, we provide an O(log n)‐time, n²‐processor Crew Pram algorithm that computes the same output as its corresponding sequential algorithm. We define a natural decision problem based on bottom‐up hierarchical clustering, and add this HIERARCHICAL CLUSTERING PROBLEM (HCP) to the slowly growing list of CC‐complete problems, thereby showing that HCP is one of the computationally most difficult problems in the COMPARATOR CIRCUIT VALUE PROBLEM class. This class contains a variety of interesting problems, and now for the first time a problem from data mining as well. By proving that HCP is CC‐complete, we have demonstrated that HCP is very unlikely to have an NC algorithm. This result is in sharp contrast to the NC algorithm which we give for the top‐down sequential approach, and the result surprisingly shows that the parallel complexities of the top‐down and bottom‐up approaches are different, unless CC equals NC. In addition, we provide a compendium of all known CC‐complete problems. © 2008 Wiley Periodicals, Inc. Complexity, 2008     

Image compression with a dynamic autoassociative neural network

Image compression using neural networks has been attempted with some promise. Among the architectures, feedforward backpropagation networks (FFBPN) have been used in several attempts. Although it is demonstrated that using the mean quadratic error function is equivalent to applying the Karhunen-Loeve transformation method, promise still arises from directed learning possibilities, generalization abilities and performance of the network once trained. In this paper we propose an architecture and an improved training method to attempt to solve some of the shortcomings of traditional data compression systems based on feedforward neural networks trained with backpropagation—the dynamic autoassociation neural network (DANN).The successful application of neural networks to any task requires proper training of the network. In this research, this issue is taken as the main consideration in the design of DANN. We emphasize the convergence of the learning process proposed by DANN. This process provides an escape mechanism, by adding neurons in a random state, to avoid the local minima trapping seen in traditional PFBPN. Also, DANN's training algorithm constrains the error for every pattern to an allowed interval to balance the training for every pattern, thus improving the performance rates in recognition and generalization. The addition of these two mechanisms to DANN's training algorithm has the result of improving the final quality of the images processed by DANN.The results of several tasks presented to DANN-based compression are compared and contrasted with the performance of an FFBPN-based system applied to the same task. These results indicate that DANN is superior to FFBPN when applied to image compression.     

Fibonacci solitaire

Fibonacci Solitaire is a combinatorial algorithm which associates with a permutation of [n]={1,…,n} a partition of [n] into couples and singletons. We study the output configuration when the algorithm is applied to a random permutation, with emphasis on the large n‐asymptotics. We show that the set of singletons, properly scaled, resembles a familiar ‘stick‐breaking’ Poisson configuration, whereas the configuration of couples becomes close to uniform. © 2002 John Wiley & Sons, Inc. Random Struct. Alg., 20, 71–88, 2002     

Turán problems for integer‐weighted graphs

A multigraph is (k,r)‐dense if every k‐set spans at most r edges. What is the maximum number of edges ex_?(n,k,r) in a (k,r)‐dense multigraph on n vertices? We determine the maximum possible weight of such graphs for almost all k and r (e.g., for all r>k³) by determining a constant m=m(k,r) and showing that ex_?(n,k,r)=m +O(n), thus giving a generalization of Turán's theorem. We find exact answers in many cases, even when negative integer weights are also allowed. In fact, our main result is to determine the maximum weight of (k,r)‐dense n‐vertex multigraphs with arbitrary integer weights with an O(n) error term. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 195–225, 2002     

Quasi‐Toeplitz splitting iteration methods for unsteady space‐fractional diffusion equations

We construct a class of quasi‐Toeplitz splitting iteration methods to solve the two‐sided unsteady space‐fractional diffusion equations with variable coefficients. By making full use of the structural characteristics of the coefficient matrix, the method only requires computational costs of O(n log n) with n denoting the number of degrees of freedom. We develop an appropriate circulant matrix to replace the Toeplitz matrix as a preconditioner. We discuss the spectral properties of the quasi‐circulant splitting preconditioned matrix. Numerical comparisons with existing approaches show that the present method is both effective and efficient when being used as matrix splitting preconditioners for Krylov subspace iteration methods.     

Multi‐periodic eigensolutions to the Dirac operator and applications to the generalized Helmholtz equation on flat cylinders and on the n‐torus

In this paper, we study the solutions to the generalized Helmholtz equation with complex parameter on some conformally flat cylinders and on the n‐torus. Using the Clifford algebra calculus, the solutions can be expressed as multi‐periodic eigensolutions to the Dirac operator associated with a complex parameter λ∈?. Physically, these can be interpreted as the solutions to the time‐harmonic Maxwell equations on these manifolds. We study their fundamental properties and give an explicit representation theorem of all these solutions and develop some integral representation formulas. In particular, we set up Green‐type formulas for the cylindrical and toroidal Helmholtz operator. As a concrete application, we explicitly solve the Dirichlet problem for the cylindrical Helmholtz operator on the half cylinder. Finally, we introduce hypercomplex integral operators on these manifolds, which allow us to represent the solutions to the inhomogeneous Helmholtz equation with given boundary data on cylinders and on the n‐torus. Copyright © 2009 John Wiley & Sons, Ltd.     

Schensted-Type Correspondences and Plactic Monoids for Types B n and D n

We use Kashiwara's theory of crystal bases to study plactic monoids for U _q(so _2n+1) and U _q(so _2n ). Simultaneously we describe a Schensted type correspondence in the crystal graphs of tensor powers of vector and spin representations and we derive a Jeu de Taquin for type B from the Sheats sliding algorithm.     

Odd‐sized partitions of Russell‐sets

In the setting of ZF, i.e., Zermelo–Fraenkel set theory without the Axiom of Choice (AC), we study partitions of Russell‐sets into sets each with exactly n elements (called n ‐ary partitions), for some integer n. We show that if n is odd, then a Russell‐set X has an n ‐ary partition if and only if |X | is divisible by n. Furthermore, we establish that it is relative consistent with ZF that there exists a Russell‐set X such that |X | is not divisible by any finite cardinal n > 1 (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

The structured total least‐squares approach for non‐linearly structured matrices

In this paper, an extension of the structured total least‐squares (STLS) approach for non‐linearly structured matrices is presented in the so‐called ‘Riemannian singular value decomposition’ (RiSVD) framework. It is shown that this type of STLS problem can be solved by solving a set of Riemannian SVD equations. For small perturbations the problem can be reformulated into finding the smallest singular value and the corresponding right singular vector of this Riemannian SVD. A heuristic algorithm is proposed. Some examples of Vandermonde‐type matrices are used to demonstrate the improved accuracy of the obtained parameter estimator when compared to other methods such as least squares (LS) or total least squares (TLS). Copyright © 2002 John Wiley & Sons, Ltd.     

Extremal solutions to a system of n nonlinear differential equations and regularly varying functions

The strongly increasing and strongly decreasing solutions to a system of n nonlinear first order equations are here studied, under the assumption that both the coefficients and the nonlinearities are regularly varying functions. We establish conditions under which such solutions exist and are (all) regularly varying functions, we derive their index of regular variation and establish asymptotic representations. Several applications of the main results are given, involving n‐th order nonlinear differential equations, equations with a generalized ?‐Laplacian, and nonlinear partial differential systems.     

On the well‐posedness of the Euler equations in the Triebel‐Lizorkin spaces

We prove local‐in‐time unique existence and a blowup criterion for solutions in the Triebel‐Lizorkin space for the Euler equations of inviscid incompressible fluid flows in ?ⁿ, n ≥ 2. As a corollary we obtain global persistence of the initial regularity characterized by the Triebel‐Lizorkin spaces for the solutions of two‐dimensional Euler equations. To prove the results, we establish the logarithmic inequality of the Beale‐Kato‐Majda type, the Moser type of inequality, as well as the commutator estimate in the Triebel‐Lizorkin spaces. The key methods of proof used are the Littlewood‐Paley decomposition and the paradifferential calculus by J. M. Bony. © 2002 John Wiley & Sons, Inc.     

Aging properties of the residual life length of k‐out‐of‐n systems with independent but non‐identical components

The k‐out‐of‐n structure is a very popular type of redundancy in fault‐tolerant systems, it has founded wide applications in industrial and military systems during the past several decades. This paper will investigate the residual life length of a k‐out‐of‐n system with independent (not necessarily identical) components, given that the (n?k)th failure has occurred at time t?0. Behaviour of PF₂, IFR, DRHR, DMRL, NBU(2) and NBUC classes of life distributions are derived in terms of the monotonicity of the residual life given the time of the (n?k)th failure. Copyright © 2004 John Wiley & Sons, Ltd.     

A Newton‐type algorithm for solving an extremal constrained interpolation problem

Given convex scattered data in R³ we consider the constrained interpolation problem of finding a smooth, minimal L _p‐norm (1 < p < ∞) interpolation network that is convex along the edges of an associated triangulation. In previous work the problem has been reduced to the solution of a nonlinear system of equations. In this paper we formulate and analyse a Newton‐type algorithm for solving the corresponding type of systems. The correctness of the application of the proposed method is proved and its superlinear (in some cases quadratic) convergence is shown. Copyright © 2000 John Wiley & Sons, Ltd.     

Three‐dimensional internal gravity‐capillary waves in finite depth

We consider three‐dimensional inviscid‐irrotational flow in a two‐layer fluid under the effects of gravity and surface tension, where the upper fluid is bounded above by a rigid lid and the lower fluid is bounded below by a flat bottom. We use a spatial dynamics approach and formulate the steady Euler equations as an infinite‐dimensional Hamiltonian system, where an unbounded spatial direction x is considered as a time‐like coordinate. In addition, we consider wave motions that are periodic in another direction z. By analyzing the dispersion relation, we detect several bifurcation scenarios, two of which we study further: a type of 00(is)(iκ₀) resonance and a Hamiltonian Hopf bifurcation. The bifurcations are investigated by performing a center‐manifold reduction, which yields a finite‐dimensional Hamiltonian system. For this finite‐dimensional system, we establish the existence of periodic and homoclinic orbits, which correspond to, respectively, doubly periodic travelling waves and oblique travelling waves with a dark or bright solitary wave profile in the x direction. The former are obtained using a variational Lyapunov‐Schmidt reduction and the latter by first applying a normal form transformation and then studying the resulting canonical system of equations.     

Asymptotic expansions in n−1 for percolation critical values on the n‐Cube and ℤn

We use the lace expansion to prove that the critical values for nearest‐neighbor bond percolation on the n‐cube {0, 1}ⁿ and on the integer lattice ?ⁿ have asymptotic expansions, with rational coefficients, to all orders in powers of n^?1. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

Wave solutions for variants of the KdV–Burger and the K(n,n)–Burger equations by the generalized G′/G‐expansion method

An application of the ‐expansion method to search for exact solutions of nonlinear partial differential equations is analyzed. This method is used for variants of the Korteweg–de Vries–Burger and the K(n,n)–Burger equations. The generalized ‐expansion method was used to construct periodic wave and solitary wave solutions of nonlinear evolution equations. This method is developed for searching exact traveling wave solutions of nonlinear partial differential equations. It is shown that the generalized ‐expansion method, with the help of symbolic computation, provides a straightforward and powerful mathematical tool for solving nonlinear problems. Copyright © 2017 John Wiley & Sons, Ltd.     

An efficient indirect RBFN‐based method for numerical solution of PDEs

This article presents an efficient indirect radial basis function network (RBFN) method for numerical solution of partial differential equations (PDEs). Previous findings showed that the RBFN method based on an integration process (IRBFN) is superior to the one based on a differentiation process (DRBFN) in terms of solution accuracy and convergence rate (Mai‐Duy and Tran‐Cong, Neural Networks 14(2) 2001, 185). However, when the problem dimensionality N is greater than 1, the size of the system of equations obtained in the former is about N times as big as that in the latter. In this article, prior conversions of the multiple spaces of network weights into the single space of function values are introduced in the IRBFN approach, thereby keeping the system matrix size small and comparable to that associated with the DRBFN approach. Furthermore, the nonlinear systems of equations obtained are solved with the use of trust region methods. The present approach yields very good results using relatively low numbers of data points. For example, in the simulation of driven cavity viscous flows, a high Reynolds number of 3200 is achieved using only 51 × 51 data points. © 2005 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2005     

One line and n points

We analyze a randomized pivoting process involving one line and n points in the plane. The process models the behavior of the RANDOM ‐EDGE simplex algorithm on simple polytopes with n facets in dimension n ? 2. We obtain a tight O(log² n) bound for the expected number of pivot steps. This is the first nontrivial bound for RANDOM ‐EDGE , which goes beyond bounds for specific polytopes. The process itself can be interpreted as a simple algorithm for certain 2‐variable linear programming problems, and we prove a tight Θ(n) bound for its expected runtime. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2003