L/sup p/ approximation of Sigma-Pi neural networks

A feedforward Sigma-Pi neural network with a single hidden layer of m neurons is given by /sup m//spl Sigma//sub j=1/c/sub j/g(n/spl Pi//sub k=1/x/sub k/-/spl theta//sub k//sup j///spl lambda//sub k//sup j/) where c/sub j/, /spl theta//sub k//sup j/, /spl lambda//sub k//spl isin/R. We investigate the approximation of arbitrary functions f: R/sup n//spl rarr/R by a Sigma-Pi neural network in the L/sup p/ norm. An L/sup p/ locally integrable function g(t) can approximate any given function, if and only if g(t) can not be written in the form /spl Sigma//sub j=1//sup n//spl Sigma//sub k=0//sup m//spl alpha//sub jk/(ln|t|)/sup j-1/t/sub k/.     

Output regulation of periodic signals for DPS: an infinite-dimensional signal Generator

In this note, we consider output regulation and disturbance rejection of periodic signals via state feedback in the setting of exponentially stabilizable linear infinite-dimensional systems. We show that if an infinite-dimensional exogenous system is generating periodic reference signals, solvability of the state feedback regulation problem is equivalent to solvability of the so called equations. This result allows us to consider asymptotic tracking of periodic reference signals which only have absolutely summable Fourier coefficients, while in related existing work the reference signals are confined to be infinitely smooth. We also discuss solution of the regulator equations and construct the actual feedback law to achieve output regulation in the single-input-single-output (SISO) case: The output regulation problem is solvable if the transfer function of the stabilized plant does not have zeros at the frequencies i/spl omega//sub n/ of the periodic reference signals and if the sequence ([CR(i/spl omega//sub n/, A+BK)B]/sup -1/ /spl times/(Q/spl phi//sub n/-CR(i/spl omega//sub n/, A+BK)P/spl phi//sub n/)) /sub n/spl isin/z//spl isin/l/sup n2/. A one-dimensional heat equation is used as an illustrative example.     

Channel assignment with separation for interference avoidance in wireless networks

Given an integer /spl sigma/>1, a vector (/spl delta//sub 1/, /spl delta//sub 2/,..., /spl delta//sub /spl sigma/-1/), of nonnegative integers, and an undirected graph G=(V, E), an L(/spl delta//sub 1/, /spl delta//sub 2/,..., /spl delta//sub /spl sigma/-1/)-coloring of G is a function f from the vertex set V to a set of nonnegative integers, such that |f(u)-f(v)|/spl ges//spl delta//sub i/, if d(u,v)=i, for 1相似文献   

Remarks on the L/sup p/-input converging-state property

Let X /spl sub/ /spl Ropf//sup N/ and consider a system x/spl dot/ = f(x,u), f : X /spl times/ /spl Ropf//sup M/ /spl rarr/ /spl Ropf//sup N/, with the property that the associated autonomous system x/spl dot/ = f (x,0) has an asymptotically stable compactum C with region of attraction A. Assume that x is a solution of the former, defined on [0,/spl infin/), corresponding to an input function u. Assume further that, for each compact K /spl sub/ X, there exists k > 0 such that |f(z,v) - f(z,0)| /spl les/ k|v| for all (z,v) /spl isin/ /spl times/ /spl Ropf//sup M/. A simple proof is given of the following L/sup p/-input converging-state property: if u /spl isin/ L/sup p/ for some p /spl isin/ [1,/spl infin/) and x has an /spl omega/-limit point in A, then x approaches C.     

An exact stability analysis test for single-parameter polynomially-dependent linear systems

We provide a new condition for testing the stability of a single-parameter, polynomially-dependent linear system of polynomial degree N of the form x/spl dot/=A(/spl rho/)x, A(/spl rho/)=/spl Sigma//sub i=0//sup N//spl rho//sup i/ A/sub i/ (1) over a compact interval. The test is nonconservative and can be cast as a convex feasibility problem in terms of a pair of linear matrix inequalities (LMIs).     

Improving load balance with flexibly assignable tasks

In many applications of parallel computing, distribution of the data unambiguously implies distribution of work among processors. But, there are exceptions where some tasks can be assigned to one of several processors without altering the total volume of communication. In this paper, we study the problem of exploiting this flexibility in assignment of tasks to improve load balance. We first model the problem in terms of network flow and use combinatorial techniques for its solution. Our parametric search algorithms use maximum flow algorithms for probing on a candidate optimal solution value. We describe two algorithms to solve the assignment problem with log W/sub T/ and |P| probe calls, where W/sub T/ and |P|, respectively, denote the total workload and number of processors. We also define augmenting paths and cuts for this problem, and show that any algorithm based on augmenting paths can be used to find an optimal solution for the task assignment problem. We then consider a continuous version of the problem and formulate it as a linearly constrained optimization problem, i.e., min /spl par/Ax/spl par//spl infin/, s.t. Bx=d. To avoid solving an intractable /spl infin/-norm optimization problem, we show that, in this case, minimizing the 2-norm is sufficient to minimize the /spl infin/-norm, which reduces the problem to the well-studied linearly constrained least squares problem. The continuous version of the problem has the advantage of being easily amenable to parallelization. Our experiments with molecular dynamics and overlapped domain decomposition applications proved the effectiveness of our methods with significant improvements in load balance. We also discuss how our techniques can be extended to heterogeneous parallel computers.     

Computation of the frequency response of multilinear affine systems

Deals with the problem of computing the frequency response of an uncertain transfer function whose numerator and denominator polynomials are multiples of independent uncertain polynomials of the form P(s, q) = l/sub o/ (q) + l/sub 1/ (q) s + /spl middot//spl middot//spl middot/ + l/sub n/, (q) s/sup n/ whose coefficients depend linearly on q = [q/sub 1/, q/sub 2/, ..., q/sub q/]/sup T/ and the uncertainty box is Q = {q: q/sub i/ /spl epsiv/ [q/sub i/, q/sub i/], i = 1, 2,..., q}. Using the geometric structure of the value set of P(s, q), a powerful edge elimination procedure is proposed for computing the Bode, Nyquist, and Nichols envelopes of these uncertain systems. A numerical example is included to illustrate the benefit of the method presented.     

Designing asymmetric Hopfield-type associative memory with higher order hamming stability

The problem of optimal asymmetric Hopfield-type associative memory (HAM) design based on perceptron-type learning algorithms is considered. It is found that most of the existing methods considered the design problem as either 1) finding optimal hyperplanes according to normal distance from the prototype vectors to the hyperplane surface or 2) obtaining weight matrix W=[w/sub ij/] by solving a constraint optimization problem. In this paper, we show that since the state space of the HAM consists of only bipolar patterns, i.e., V=(v/sub 1/,v/sub 2/,...,v/sub N/)/sup T//spl isin/{-1,+1}/sup N/, the basins of attraction around each prototype (training) vector should be expanded by using Hamming distance measure. For this reason, in this paper, the design problem is considered from a different point of view. Our idea is to systematically increase the size of the training set according to the desired basin of attraction around each prototype vector. We name this concept the higher order Hamming stability and show that conventional minimum-overlap algorithm can be modified to incorporate this concept. Experimental results show that the recall capability as well as the number of spurious memories are all improved by using the proposed method. Moreover, it is well known that setting all self-connections w/sub ii//spl forall/i to zero has the effect of reducing the number of spurious memories in state space. From the experimental results, we find that the basin width around each prototype vector can be enlarged by allowing nonzero diagonal elements on learning of the weight matrix W. If the magnitude of w/sub ii/ is small for all i, then the condition w/sub ii/=0/spl forall/i can be relaxed without seriously affecting the number of spurious memories in the state space. Therefore, the method proposed in this paper can be used to increase the basin width around each prototype vector with the cost of slightly increasing the number of spurious memories in the state space.     

Learning capability and storage capacity of two-hidden-layer feedforward networks

The problem of the necessary complexity of neural networks is of interest in applications. In this paper, learning capability and storage capacity of feedforward neural networks are considered. We markedly improve the recent results by introducing neural-network modularity logically. This paper rigorously proves in a constructive method that two-hidden-layer feedforward networks (TLFNs) with 2/spl radic/(m+2)N (/spl Lt/N) hidden neurons can learn any N distinct samples (x/sub i/, t/sub i/) with any arbitrarily small error, where m is the required number of output neurons. It implies that the required number of hidden neurons needed in feedforward networks can be decreased significantly, comparing with previous results. Conversely, a TLFN with Q hidden neurons can store at least Q/sup 2//4(m+2) any distinct data (x/sub i/, t/sub i/) with any desired precision.     

Stochastic stabilization of nonlinear systems in feedforward form with noisy outputs

We study the problem of globally stabilizing through measurement feedback a class of uncertain stochastic nonlinear systems in feedforward (or upper triangular) form, with state equations affected by a Wiener process adapted to a given filtration of /spl sigma/-algebras and measurements affected by a sample continuous and strongly Markov stochastic process adapted to the same filtration of /spl sigma/-algebras. We propose a step-by step design, based on splitting the system /spl Sigma/ into one-dimensional interconnected systems /spl Sigma//sub j/, j=1,...,n. Moreover, we introduce the notion of practical stability in probability, which corresponds to having a large probability of being the state small in norm whenever the noise affecting the measurements has a "small" second order moment.     

Transient response control via characteristic ratio assignment

This note develops an approach to directly control the transient response of linear time-invariant control systems. We begin by considering all-pole transfer functions of order n for which we introduce a set of parameters /spl alpha//sub i/, i=1,...n called the characteristic ratios. We also introduce a generalized time constant /spl tau/. We prove that /spl alpha//sub 1/ and /spl tau/ can be used to characterize the system overshoot to a step input and the speed of response, respectively. By independently adjusting /spl alpha//sub 1/ and /spl tau/ in all-pole systems, arbitrarily small or no overshoot as well as arbitrarily fast speed of response can be achieved. These formulas are used to develop a procedure to design feedback controllers with feedforward or two parameter output feedback type for achieving time response specifications. For a minimum phase plant we show that arbitrary transient response specifications, namely one with independently specified overshoot and specified rise time or speed of response can be exactly attained.     

A min-max approach to fuzzy clustering, estimation, and identification

This study, for any unknown physical process y=f(x/sub 1/,...,x/sub n/), is concerned with the: 1) fuzzy partition of n-dimensional input space X=X/sub 1//spl times//spl middot//spl middot//spl middot//spl times/X/sub n/ into K different clusters, 2) estimating the process behavior y/spl circ/=f(x/spl circ/) for a given input x/spl circ/=(x/spl circ//sub 1/,/spl middot//spl middot//spl middot/,x/spl circ//sub n/)/spl isin/X, and 3) fuzzy approximation of the process, with uncertain input-output identification data {(x(k)/spl plusmn//spl delta/x/sub k/),(y(k)/spl plusmn/v/sub k/)}/sub k=1,.../, using a Sugeno type fuzzy inference system. A unified min-max approach (that attempts to minimize the worst-case effect of data uncertainties and modeling errors on estimation performance), is suggested to provide robustness against data uncertainties and modeling errors. The proposed method of min-max fuzzy parameters estimation does not make any assumption and does not require a priori knowledge of upper bounds, statistics, and distribution of data uncertainties and modeling errors. To show the feasibility of the approach, simulation studies and a real-world application of physical fitness classification based on the fuzzy interpretation of physiological parameters, have been provided.     

A necessary algebraic condition for controllability and observability of linear time-varying systems

In this note, we give an algebraic condition which is necessary for the system x'(t)=A(t)x(t)+B(t)u(t), y(t)=C(t)x(t), either to be totally controllable or to be totally observable, where x/spl isin//spl Ropf//sup d/, u/spl isin//spl Ropf//sup p/, y/spl isin//spl Ropf//sup q/, and the matrix functions A, B and C are (d-2), (d-1) and (d-1) times continuously differentiable, respectively. All conditions presented here are in terms of known quantities and therefore easily verified. Our conditions can be used to rule out large classes of time-varying systems which cannot be controlled and/or observed no matter what the nonzero time-varying coefficients are. This work is motivated by the deep result of Silverman and Meadows.     

Constructing edge-disjoint spanning trees in product networks

A Cartesian product network is obtained by applying the cross operation on two graphs. We study the problem of constructing the maximum number of edge-disjoint spanning trees (abbreviated to EDSTs) in Cartesian product networks. Let G=(V/sub G/, E/sub G/) be a graph having n/sub 1/ EDSTs and F=(V/sub F/, E/sub F/) be a graph having n/sub 2/ EDSTs. Two methods are proposed for constructing EDSTs in the Cartesian product of G and F, denoted by G/spl times/F. The graph G has t/sub 1/=|E/sub G/|/spl middot/n/sub 1/(|V/sub G/|-1) more edges than that are necessary for constructing n/sub 1/ EDSTs in it, and the graph F has t2=|E/sub F/'-n/sub 2/(|V/sub F/|-1) more edges than that are necessary for constructing n/sub 2/ EDSTs in it. By assuming that t/sub 1//spl ges/n/sub 1/ and t/sub 2//spl ges/n/sub 2/, our first construction shows that n/sub 1/+n/sub 2/ EDSTS can be constructed in G/spl times/F. Our second construction does not need any assumption and it constructs n/sub 1/+n/sub 2/-1 EDSTs in G/spl times/F. By applying the proposed methods, it is easy to construct the maximum numbers of EDSTs in many important Cartesian product networks, such as hypercubes, tori, generalized hypercubes, mesh connected trees, and hyper Petersen networks.     

The sector bound approach to quantized feedback control

This paper studies a number of quantized feedback design problems for linear systems. We consider the case where quantizers are static (memoryless). The common aim of these design problems is to stabilize the given system or to achieve certain performance with the coarsest quantization density. Our main discovery is that the classical sector bound approach is nonconservative for studying these design problems. Consequently, we are able to convert many quantized feedback design problems to well-known robust control problems with sector bound uncertainties. In particular, we derive the coarsest quantization densities for stabilization for multiple-input-multiple-output systems in both state feedback and output feedback cases; and we also derive conditions for quantized feedback control for quadratic cost and H/sub /spl infin// performances.     

Fuzzy H/sub /spl infin// output feedback control design for singularly perturbed systems with pole placement constraints: an LMI approach

This paper examines the problem of designing an H/sub /spl infin// output feedback controller with pole placement constraints for singular perturbed Takagi-Sugeno (TS) fuzzy models. We propose a fuzzy H/sub /spl infin// output feedback controller that not only guarantees the /spl Lscr//sub 2/-gain of the mapping from the exogenous input noise to the regulated output to be less than some prescribed value, but also ensures closed-loop poles of each subsystem are in a prespecified linear matrix inequality (LMI) region. In order to alleviate the numerical stiffness caused by the singular perturbation /spl epsiv/, the design technique is formulated in terms of a family of /spl epsiv/-independent linear matrix inequalities. The proposed approach can be applied both standard and nonstandard singularly perturbed nonlinear systems. A numerical example is provided to illustrate the design developed in this paper.     

多处理器任务调度问题的新近似算法

研究任务有多种处理方式的多处理器任务调度问题（MTS）的求解算法，给出求解这种问题的二阶段方法：第1阶段为指派问题，第二阶段调度问题Pm｜fixj｜Cmax，从而得到一个新的求解Pm｜setj｜Cmax。近似算法的方法，并针对P4｜fixj｜Cmax给出了具体算法，证明这种近似算法是一个2-逼近度算法，是文献中在4-处理器问题上的推广。     

Sparse component analysis and blind source separation of underdetermined mixtures

In this letter, we solve the problem of identifying matrices S /spl isin/ /spl Ropf//sup n/spl times/N/ and A /spl isin/ /spl Ropf//sup m/spl times/n/ knowing only their multiplication X = AS, under some conditions, expressed either in terms of A and sparsity of S (identifiability conditions), or in terms of X (sparse component analysis (SCA) conditions). We present algorithms for such identification and illustrate them by examples.     

A strip-splitting-based optimal algorithm for decomposing a query window into maximal quadtree blocks

Decomposing a query window into maximal quadtree blocks is a fundamental problem in quadtree-based spatial database. Recently, Proietti presented the first optimal algorithm for solving this problem. Given a query window of size n/sub 1//spl times/n/sub 2/, Proietti's algorithm takes O(n/sub 1/) time, where n/sub 1/=max(n/sub 1/, n/sub 2/). Based on a strip-splitting approach, we present a new optimal algorithm for solving the same problem. Experimental results reveal that our proposed algorithm is quite competitive with Proietti's algorithm.     

Temporal logic query checking: a tool for model exploration

Temporal logic query checking was first introduced by W. Chan in order to speed up design understanding by discovering properties not known a priori. A query is a temporal logic formula containing a special symbol ?/sub 1/, known as a placeholder. Given a Kripke structure and a propositional formula /spl phi/, we say that /spl phi/ satisfies the query if replacing the placeholder by /spl phi/ results in a temporal logic formula satisfied by the Kripke structure. A solution to a temporal logic query on a Kripke structure is the set of all propositional formulas that satisfy the query. Query checking helps discover temporal properties of a system and, as such, is a useful tool for model exploration. In this paper, we show that query checking is applicable to a variety of model exploration tasks, ranging from invariant computation to test case generation. We illustrate these using a Cruise Control System. Additionally, we show that query checking is an instance of a multi-valued model checking of Chechik et al. This approach enables us to build an implementation of a temporal logic query checker, TLQSolver, on top of our existing multi-valued model checker /sub /spl chi//Chek. It also allows us to decide a large class of queries and introduce witnesses for temporal logic queries-an essential notion for effective model exploration.