Universal approximation capability of EBF neural networks with arbitrary activation functions

The purpose of this paper is to investigate the approximation capability of elliptic basis function (EBF) neural networks. The main results are: (1) A necessary and sufficient condition for a functionS (R ¹) to be qualified as an activation function in the hidden layer of an EBF neural network is given. (2) Every nonzero functionG L ²(R ⁿ ) is qualified to be an activation function in the elliptic neural network to approximate any function in L²(Rⁿ). (3) As applications, we give new proofs of the theorems concerning the approximation capability of affine basis function (ABF) neural networks and generalized radial basis function (GRBF) neural networks (including radial basis function neural networks) with arbitrary activation functions. In particular, we solve the problem of the approximation capability of sigma-pi neural networks.Work was supported in part by CNSF, the Shanghai Science Foundations and Doctoral Program of Education Commissions of China.     

Gaussian radial basis functions and inner product spaces

An approximation result is given concerning Gaussian radial basis functions in a general inner product space. Applications are described concerning the classification of the elements of disjoint sets of signals, and also the approximation of continuous real functions defined on all of ⁿ using radial basis function (RBF) networks. More specifically, it is shown that an important large class of classification problems involving signals can be solved using a structure consisting of only a generalized RBF network followed by a quantizer. It is also shown that Gaussian radial basis functions defined on ⁿ can uniformly approximate arbitrarily well over all of ⁿ any continuous real functionalf on ⁿ that meets the condition that |f(x)|0 as x.     

Integral expressions for the numerical evaluation of product form expressions over irregular multidimensional integer state spaces

We consider stochastic systems defined over irregular, multidimensional, integer spaces that have a product form steady state distribution. Examples of such systems include closed and BCMP type of queuing networks, polymerization and genetic models. In these models the system state is a vector of integers, n=[n ₁,...,n _M ] and the steady state solution has product form of the type (n)= _i=1 ^M f _i (n _i ). To obtain useful statistics from such product form solutions, (n) has to be summed over some subset of the space over which it is defined. We consider situations when these subsets are defined by a set of equalities and inequalities with integer coefficients, as is most often the case and provide integral expressions to obtain these sums. Typically, a brute force technique to obtain the sum is computationally very expensive. Algorithmic solutions are available for only specific forms of f _i (n _i ) and shapes of the state space. In this paper we derive general integral expressions for arbitrary state spaces and arbitrary f _i (n _i ). The expressions that we derive here become especially useful if the generating functions f _i (n _i ) can be expressed as a ratio of polynomials in which case, exact closed form expressions can be obtained for the sums. We demonstrate the wide applicability of the integral expressions that we derive here through three examples in which we model finite highway cellular systems, copy networks in multicast packet switches and a BCMP queuing network modeling a multiuser computer system.     

Iteration and functional expansions

In a recent paper on nonlocal expansions necessary and sufficient conditions are given under whichf ^–1 has a generalized power series expansion, whenf is an invertible locally Lipschitz map between certain general subsets of a complex Banach space. Here we establish the validity of a conceptually interesting algorithm for obtaining the expansion.Basically, we show that a certain contraction mapping iteration generates iterates ₁, ₂,... such that each _k yields all of the terms of the generalized power series expansion off ^–1 up to order (k + 1), assuming merely that the expansion off ^–1 exists. An earlier different result along related lines is mentioned.     

Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks

Connected dominating set (CDS) has been proposed as virtual backbone or spine of wireless ad hoc networks. Three distributed approximation algorithms have been proposed in the literature for minimum CDS. In this paper, we first reinvestigate their performances. None of these algorithms have constant approximation factors. Thus these algorithms cannot guarantee to generate a CDS of small size. Their message complexities can be as high as O(n ²), and their time complexities may also be as large as O(n ²) and O(n ³). We then present our own distributed algorithm that outperforms the existing algorithms. This algorithm has an approximation factor of at most 8, O(n) time complexity and O(nlogn) message complexity. By establishing the (nlogn) lower bound on the message complexity of any distributed algorithm for nontrivial CDS, our algorithm is thus message-optimal.     

Energy-Efficient Broadcasting in All-Wireless Networks

In all-wireless networks, minimizing energy consumption is crucial as in most cases the nodes are battery-operated. We focus on the problem of power-optimal broadcast, for which it is well known that the broadcast nature of radio transmissions can be exploited to optimize energy consumption. This problem appears to be difficult to solve [30]. We provide a formal proof of NP-completeness for the general case and give an NP-completeness result for the geometric case; in the former, the network topology is represented by a generic graph with arbitrary weights, whereas in the latter a Euclidean distance is considered. For the general case, we show that it cannot be approximated better than O(logN), where N is the total number of nodes. We then describe an approximation algorithm that achieves the O(logN) approximation ratio. We also describe a new heuristic, Embedded Wireless Multicast Advantage. We show that it compares well with other proposals and we explain how it can be distributed.     

Power Consumption of Quasi-adiabatic Logic Gates

A computer simulation is carried out to investigate the power consumption of major quasi-adiabatic logic gates. Anomalously high dissipation is found at low clock rates. An explanation for the anomaly and a method of eliminating this are proposed. For the dissipated energy W and the clock rate f, it is found that W f C ^{1 +} as f tends to infinity, where is essentially less than unity. The mechanism of the phenomenon is identified. Rules are established that govern the power consumption of the logic gates. It is concluded that they should help one to strike a balance between power consumption and speed, to optimize power characteristics, and to predict the performance of future models made by better process technologies.     

Time-delay neural networks, volterra series, and rates of approximation

We consider a large family of approximately-finite-memory causal time-invariant mapsG from an input setS to a set of -valued functions, with the members of both sets of functions defined on the nonnegative integers, and we give an upper bound on the error in approximating aG using a two-stage structure consisting of a tapped delay line followed by a static neural network. As an application, information is given concerning the long-standing problem of determining the order of a Volterra-series approximation so that a given quality of approximation can be achieved. We also give corresponding results for the approximation of not necessarily causal input-output maps with inputs and outputs that may depend on more than one variable. These results are of interest, for example, in connection with image processing.     

Design and design methods for unified multiplier and inverter and its application for HECC

This paper describes two novel architectures for a unified multiplier and inverter (UMI) in GF(2^m): the UMI merges multiplier and inverter into one unified data-path. As such, the area of the data-path is reduced. We present two options for hyperelliptic curve cryptography (HECC) using UMIs: an FPGA-based high-performance implementation (Type-I) and an ASIC-based lightweight implementation (Type-II). The use of a UMI combined with affine coordinates brings a smaller data-path, smaller memory and faster scalar multiplication.Both implementations use curves defined by h(x)=x and f(x)=x⁵+f₃x³+x²+f₀. The high throughput version uses 2316 slices and 2016 bits of block RAM on a Xilinx Virtex-II FPGA, and finishes one scalar multiplication in . The lightweight version uses only 14.5 kGates, and one scalar multiplication takes 450 ms.     

Selecting Forwarding Neighbors in Wireless Ad Hoc Networks

Broadcasting is a fundamental operation which is frequent in wireless ad hoc networks. A simple broadcasting mechanism, known as flooding, is to let every node retransmit the message to all its 1-hop neighbors when receiving the first copy of the message. Despite its simplicity, flooding is very inefficient and can result in high redundancy, contention, and collision. One approach to reducing the redundancy is to let each node forward the message only to a small subset of 1-hop neighbors that cover all of the node's 2-hop neighbors. In this paper we propose two practical heuristics for selecting the minimum number of forwarding neighbors: an O(nlogn) time algorithm that selects at most 6 times more forwarding neighbors than the optimum, and an O(nlog² n) time algorithm with an improved approximation ratio of 3, where n is the number of 1- and 2-hop neighbors. The best previously known algorithm, due to Bronnimann and Goodrich [2], guarantees O(1) approximation in O(n ³ logn) time.     

A doubling procedure for constructing minimal broadcast networks

Broadcast is the task of disseminating a message from any node to all the other nodes in a network. A minimal broadcast network (mbn) withn nodes is a communication network in which a message originated at any node can be broadcasted in [log₂ n] time units. An optimal broadcast network (obn) is an mbn with minimum number of edges. No method is known for constructing an obn with an arbitrary number of nodes. In this paper, a new method called the doubling procedure is presented to construct mbn's with 2n and 2n–1 nodes when an obn or a good mbn withn nodes is known. The new construction method is based on the concepts of center node and center node set of an mbn. An algorithm is proposed to find a center node set of a given mbn. It is shown that an obn with 2n nodes can be constructed based on a known obn withn nodes for alln 9,n=15, 31 and 63,n=2 ^m –1 andn=2 ^m ,mZ ⁺, by applying the doubling procedure. This method also generates the best mbn's for some values of [n64.     

Digital Modulator with Bandpass Delta-Sigma Modulator

A digital quadrature modulator with a bandpass -modulator is presented that interpolates orthogonal input carriers by 16 and performs a digital quadrature modulation at carrier frequencies f_s/4, –f_s/4 (f_s is the sampling frequency). After quadrature modulation, the signal is converted into an analogue IF signal using a bandpass modulator and a 1-bit D/A converter. The die area of the chip is 5.2 mm² (0.13 m CMOS technology). The total power consumption is 139 mW at 1.5 V with a clock frequency of 700 MHz (D/A converter full-scale output current 11.5 mA).     

Novel Ion-Lens Configurations: A Further Step to 2-nm Ion-Beam Lithography

Composite axially symmetric immersion ion lenses are considered that consist of an electrostatic and a magnetic lens. For the first time, their performance is evaluated over the entire range of operating conditions: from the case of a zero magnetic field to the case of a zero ion energy on the target. Operating conditions are characterized in terms of = W _t/W ₀, where W ₀ is the energy of an ion at the boundary of the region in which the trajectories are parallel to the axis and W _t is that on the target. For the first time, simple analytical approximations are derived for C _c/r, C _s/r, f/r, and NI, where C _c is the chromatic-aberration coefficient, C _s is the third-order spherical-aberration coefficient, f is the focal distance, NI is the magnetomotive force of the coil, and r is the outer radius of the coil. The behavior of the four quantities is explored as a function of . The following conclusions are drawn: (i) The aberrations are maximum for a zero magnetic field. (ii) The aberration coefficients decrease monotonically with increasing NIand decreasing , the lens changing from an accelerating to a decelerating one. (iii) If , then C _s/r – ^1/4, C _c/r – ^1/6, f/r– ^1/3, and NI – ^–1/2. (iv) The lenses are suitable for resistless heavy-ion projection lithography and can provide 20 × 10¹¹ pixels of area 2 × 2 nm² for an exposed area of 3 × 3 mm². (v) Used in heavy-ion microprobe systems, the lenses could enable resistless lithography over much larger areas than existing equipment.     

An optical sensor for hydrogen sulfide detection in open path using WMS-2f/1f technique

An optical hydrogen sulfide (H2S) sensor based on wavelength modulation spectroscopy with the second harmonic (2f) corrected by the first harmonic (1f) signal (WMS-2f/1f) is developed using a distributed feedback (DFB) laser emitting at 1.578 µm and a homemade gas cell with 1-m-long optical path length. The novel sensor is constructed by an electrical cabinet and an optical reflecting and receiving end. The DFB laser is employed for targeting a strong H2S line at 6 336.62 cm-1 in the fundamental absorption band of H2S. The sensor performance, including the minimum detection limit and the stability, can be improved by reducing the laser intensity drift and common mode noise by means of the WMS-2f/1f technique. The experimental results indicate that the linearity and response time of the sensor are 0.999 26 and 6 s (in concentration range of 15.2—45.6 mg/m3), respectively. The maximum relative deviation for continuous detection (60 min) of 30.4 mg/m3 H2S is 0.48% and the minimum detection limit obtained by Allan variance is 79 μg/m3 with optimal integration time of 32 s. The optical H2S sensor can be applied to environmental monitoring and industrial production, and it has significance for real-time online detection in many fields.     

Approximation Algorithms for the Mobile Piercing Set Problem with Applications to Clustering in Ad-Hoc Networks

The main contributions of this paper are two-fold. First, we present a simple, general framework for obtaining efficient constant-factor approximation algorithms for the mobile piercing set (MPS) problem on unit-disks for standard metrics in fixed dimension vector spaces. More specifically, we provide low constant approximations for L ₁ and L norms on a d-dimensional space, for any fixed d>0, and for the L ₂ norm on two- and three-dimensional spaces. Our framework provides a family of fully-distributed and decentralized algorithms, which adapt (asymptotically) optimally to the mobility of disks, at the expense of a low degradation on the best known approximation factors of the respective centralized algorithms: Our algorithms take O(1) time to update the piercing set maintained, per movement of a disk. We also present a family of fully-distributed algorithms for the MPS problem which either match or improve the best known approximation bounds of centralized algorithms for the respective norms and space dimensions.Second, we show how the proposed algorithms can be directly applied to provide theoretical performance analyses for two popular 1-hop clustering algorithms in ad-hoc networks: the lowest-id algorithm and the Least Cluster Change (LCC) algorithm. More specifically, we formally prove that the LCC algorithm adapts in constant time to the mobility of the network nodes, and minimizes (up to low constant factors) the number of 1-hop clusters maintained. While there is a vast literature on simulation results for the LCC and the lowest-id algorithms, these had not been formally analyzed prior to this work.We also present an O(logn)-approximation algorithm for the mobile piercing set problem for nonuniform disks (i.e., disks that may have different radii), with constant update time.     

Distributed Long-Lived List Colouring: How to Dynamically Allocate Frequencies in Cellular Networks

To avoid signal interference in mobile communication it is necessary that the frequencies used for communication within each cell are allocated so that no signal interference occurs with neighbouring cells. We model this channel allocation problem as a generalised list colouring problem and we show how to analytically measure and provide worst-case guarantees regarding request satisfiability. To the best of our knowledge, this has not been done before and gives a new perspective to the problem, as well as a clear direction for further investigation. We propose distributed approaches for solving the problem, which are able to adapt fast to temporal variations in channel demands in different cells, as well as to cope with crash failures, by limiting the failure-locality – the size of the network that can be affected by a faulty station, in terms of the distance from that station. Our first approach is inspired by a relatively recent theorem relating graph colourings and orientations; it achieves the equivalent of the best known sequentially achievable upper bound for request satisfiability, implied by the theorem. It also employs a powerful synchronisation mechanism to achieve worst-case response time that depends only on – the degree of the signal interference graph – and failure locality 4. Our second proposal is a first approach towards exploring what bound in request satisfiability is achievable without the use of extra synchronisation; by employing randomisation in frequency choices, in only one round of communication, a base station can expect to pick f/(4) frequencies, where f is the size of the list at the node; the failure locality of this solution is only 1.     

Stieltjes series and soliton interaction

TheKdV andMkdV multisoliton solutions are found to be generated by rational Stieltjes functions of the non-linearity parameter, each pole of which can be associated with a soliton. The well-known asymptotic emergence of the separate solitons follows at once from the motion of the poles. Successive (n-1/n) Padé approximants to theN-soliton series are considered to show how the solitons are reconstructed from an increasing number of perturbation terms (n N). Their asymptotic behaviour is particularly striking: as time increases the behaviour of then ^th approximation becomes that of an actualn-soliton solution, constituted by then leading solitons. Furthermore, it turns out that each such Padé approximation satisfies a conservation law: the mass of the approximated solution, equal to that of then solitons included, is conserved.Invited paper at the International Seminar on High Energy Physics, and Quantum Field Theory, Serpukhov, 1981. This research was partially supported by the I. I. K. W., Brussels.     

Construction of Time-Relaxed c-Broadcast Networks

C-broadcasting is an information dissemination task where a message, originated at any node in a network, is transmitted to all other nodes with the restriction that each node having the message can transmit it to almost c neighbors simultaneously. If the transmission time of the message is set to be one time unit, a minimal c-broadcast network (c-MBN) is a communication network in which c-broadcasting from any node can be accomplished in log _c+1 n time units, where n is the number of nodes and log _c+1 n is the fastest possible broadcast time. If networks are sparse, additional time units may be required to perform c-broadcasting. A time-relaxed c-broadcast network, denoted as (t,c)-RBN, is a network where c-broadcasting from any node can be completed in log _c+1 n+t time units. In this paper, a network compounding algorithm is proposed to construct large sparse (t,c)-RBNs by linking multiple copies of a time-relaxed network of small size using the structure of another time-relaxed network. Computational results are presented to show the effectiveness of the proposed algorithm.     

Parallel implementation of neural networks

This paper presents systematic methods, based on graph theoretic approach, for mapping of neural networks onto mesh connected SIMD arrays. The methods are applicable to a large class of multilayer network models, which can be represented in terms of sparse matrix vector operations. The class of computers, that the mappings are suitable for, encompasses most of the experimental and commercial mesh-connected SIMD arrays of processors. There are three methods described in the paper, one for the case of a processor array, which is larger or equal to the network size and two for the partitioned case, i.e. array smaller than the input data size. The methods are illustrated on an example of a multilayer perceptron with back-propagation learning, which consists ofn nuerons ande synaptic connections. For the first method, the processor array is assumed to be of sizeN×N, whereN ² n+e, and the required local memory of processors is limited to only a few registers. The implementation of a single iteration of a recall phase according to the method requires 24(N-1) shifts. For this method we have developed a software tool, which generates a sequence of pseudo instructions, such as elemental data shift and arithmetic operations, that implement a given neural network on a given size processor array. For the two partitioned methods, the processor array is of sizeP×P, whereP ²n+e, and the local memory in the processors is of sizeO(K). The faster of the two methods requiresO(N ³/P ³ K) time for an iteration of the recall or learning phase.This research was supported in part by the National Science Foundation under grant MIP-8714689 and IRI-9145810.Preliminary versions of the results contained in this paper appear in the International Conference on Applications-Specific Array Processors 1990 and the IEEE Workshop on VLSI Signal Processing 1990.     

Power Efficient Range Assignment for Symmetric Connectivity in Static Ad Hoc Wireless Networks

In this paper we study the problem of assigning transmission ranges to the nodes of a static ad hoc wireless network so as to minimize the total power consumed under the constraint that enough power is provided to the nodes to ensure that the network is connected. We focus on the Min-Power Symmetric Connectivity problem, in which the bidirectional links established by the transmission ranges are required to form a connected graph. Implicit in previous work on transmission range assignment under asymmetric connectivity requirements is the proof that Min-Power Symmetric Connectivity is NP-hard and that the MST algorithm has a performance ratio of 2. In this paper we make the following contributions: (1) we show that the related Min-Power Symmetric Unicast problem can be solved efficiently by a shortest-path computation in an appropriately constructed auxiliary graph; (2) we give an exact branch and cut algorithm based on a new integer linear program formulation solving instances with up to 35–40 nodes in 1 hour; (3) we establish the similarity between Min-Power Symmetric Connectivity and the classic Steiner Tree problem in graphs, and use this similarity to give a polynomial-time approximation scheme with performance ratio approaching 5/3 as well as a more practical approximation algorithm with approximation factor 11/6; and (4) we give the results of a comprehensive experimental study comparing new and previously proposed heuristics with the above exact and approximation algorithms.