Search

To date few numerical comparisons between multiplier algorithms have been made. The full paper (available from the author) presents a numerical comparison of the algorithms of Hestenes, Tripathi and Narendra, Powell, Haarhoff and Buys, Kort and Bertsekas, and the author, on a variety of nonlinear equality constrained function minimization problems.

In this paper we concern Ourselves with the problem of obtaining high sequence rate sequential machines, machines which are constructed from realistic devices to operate at an input sequence rate which is independent of the machine complexity. To accomplish this result we have only to show a Construction to realize acceptably synchronous devices from badly timed, restricted fan-in and fan-out devices. Once a complete set of synchronous devices is obtained, the results of Arden and Arthurs1,2 apply and we know that any finite state machine has a realization using these devices which accepts input sequence members at a rate which is characteristic of the set of devices, not of the machine. The technique we propose for achieving this result is to produce a lattice of interconnected clock pulse sources called Clock Pulse Propagators. These devices generate clock pulses which are acceptably synchronized with respect to the outputs of neighboring CPP's but are not required to be in synchronization with some machine-wide standard as in current practice. Once it is established that such a network is possible, techniques already known can be applied in the utilization of the clock-pulses to synchronize logic and signals. In this paper, we first present and analyze the use of the assumed clock pulses to synchronize the logic. Lower bounds are developed for the clock-pulse period which depend on the logic device parameters, signal propagation delay and delay variation, and on the size of the region that each CPP serves. As a consequence of this analysis, it is found that in some circumstances, the two phase clock has the potential for higher rate operation than the single phase and is less restrictive in the design constraints imposed for stable operation. The other major portion of the paper is devoted to the presentation of the nature of the CPP, a device based strongly on McNaughton's RBF element3, and the proof that a network of these devices does produce acceptably synchronous clock pulses.

The objective of the work described in this paper is to relate signal-to-noise ratio and signal-to-interference ratio at the input of a receiver employing a quantized pulse position demodulator to the decision errors occurring at the output. This paper describes the receiver model and discusses the assumptions made in its formulation. Assumptions concerning the description of desired signals, interfering signals and random disturbances are also described. On the basis of these, an expression for the receiver output signal-to-noise is obtained which has the form (S/N) o 1+ A where (S/N)i is the input signal-to-noise ratio (S/I)i is the input signal-to-interference ratio A and D are constants related to the receiver model and desired signal description B is a constant involving the description of the noise C is a constant for a particular interfering signal description. The interfering signals for which the constant C is presented in this paper are: a single CW, two CW signals, a pulse position modulated signal similar to the desired signal, a double side-band amplitude modulated signal, a single side-band amplitude modulated signal, narrow-band and wide-band frequency modulated signals, and PCM-FSK type interferers.

This paper concerns switching networks which consist of n identical combinational logic cells interconnected from left to right by alpha communication channels into linear arrays. The synchronous cells in these networks have unit switching delays separating their receipts of external x and left-neighbor alpha inputs from their corresponding productions of external z and right-neighbor alpha outputs. Three basic types of alpha transient behavior are discussed for such networks. In the first type, all transients extend to no more than a bounded number of cells to the right of each x change; in the second, all transients propagate all the way to the right boundary of the network; and in the third, any transient may or may not propagate to the right boundary of the network depending upon the x sequence to the right of the x change in question. In all three cases, necessary and sufficient conditions are given on the type of alpha logic allowed. These conditions are expressed in terms of corresponding alpha state graph structure. The paper's main results hinge on certain properties of a new type of state subgraph, and on an indirect application of permutation groups to the state-pair transition problem. A section of examples proves that individual graphs can contain any mixture of the above three types of transient behavior.

This paper treats variable structure systems with vector control inputs. Each component of the control vector is discontinuous on a corresponding surface in the system coordinate space. In such systems, sliding modes may arise and then trajectories lie on the discontinuity surfaces or their intersections. A so-called method of equivalent control is suggested which allows formal development of equations of such motions. The validity of the sliding mode equations derived through the equivalent control approach is established by introduction into the system of small nonidealities (of hysteresis, time-lag, and a periodic type) which are then made to tend to zero. It is suggested that Liapunov stability concepts be applied to derive the conditions for existence of sliding modes. It follows from the equations describing system evolution in the sliding mode that trajectory characteristics are dependent on the discontinuity surfaces equations. Therefore, proper selection of the surfaces on which the components of the control vector are discontinuous enables one to introduce desired properties into the system response. A desired response can be obtained if the trajectory reaches the intersection of the discontinuity surface starting from any initial state, and that at each point of the intersection the existence conditions for the sliding mode hold. The paper considers different methods of variable structure systems synthesis on the basis of the sliding modes being deliberately introduced into the system. Algorithms are described for controlling plants with both constant and variable parameters, and also plants with external disturbances. A class of systems is indicated in which evolution in the sliding mode possesses invariance with respect to variable parameters and disturbances.

Suppose we are given a polynomial P(x"1,...,x"r) in r>=1 variables, let m bound the degree of P in all variables x"i, [email protected][email protected]?r, and we wish to raise P to the nth power, n>1. In a recent paper which compared the iterative versus the binary method it was shown that their respective computing times were O(m^2^rn^r^+^1) versus O(mn)^2^r) when using single precision arithmetic. In this paper a new algorithm is given whose computing time is shown to be O((mn)^r^+^1). Also if we allow for polynomials with multiprecision integer coefficients, the new algorithm presented here will be faster by a factor of m^r^-^1n^r over the binary method and faster by a factor of m^r^-^1 over the iterative method. Extensive empirical studies of all three methods show that this new algorithm will be superior for polynomials of even relatively small degree, thus guaranteeing a practical as well as a useful result.

A generalized model of automata is defined in which the outputs are sequences of letters (rather than single letters) for each input letter. The output sequences are transmitted without spacing, just as in the case of variable length codes. The paper describes a test for determining whether a given generalized automaton is information lossless, and if so, whether information lossless of finite order. (Decipherable with finite delay.) The codes generated by generalized automata are believed to be even harder to break than ordinary variable length codes. The techniques described in the present paper provide useful tools in the design of such coding procedures.

In this paper we present three equivalent characterizations of what can be termed the zeros of a multivariable system. By establishing this equivalence a connection is made between several large bodies of literature on multivariable system problems. In particular, a polynomial which has arisen quite often in recent work on input isolation, decoupling, model matching, etc. is shown to be identical with a numerator polynomial of the Smith McMillan form of a system transfer function matrix. No proofs are presented here but they can be found in a more inclusive paper being submitted for publication [1].

This paper is concerned with the problem of detecting when two asynchronous control systems are equivalent. The systems investigated in the paper are first represented by means of a formal model called an asynchronous control structure (ACS). This model specifies the constraints imposed on the generation of control signals by a system by means of a simple graphical model called a marked graph. Behavioral equivalence is then characterized in terms of the set of all possible sequences of control signals that can be generated by the system. These sequences are represented by means of another (infinite) marked graph, called a behavior graph. Finally, it is shown that two control systems are equivalent if and only if their behavior graph representations have identical (finite) generating sets.

We pursue in this paper some of the ideas discussed a year ago at the First Annual Symposium on Switching Theory and Logical Design. For a general discussion of threshold logic, and for definitions and motivations of the terms used below, the reader is referred to "Single Stage Threshold Logic" also published in this volume [13]. Also, a general survey of recent papers in the subject has been published elsewhere [14]. The main subject treated below is compound synthesis. The importance of such a study was shown last year: The family of functions of n arguments realizable in a single stage becomes a vanishing fraction of all switching functions of n arguments as n grows (for n = 7 the ratio is about 1028 1/2). We provide an algorithm for determining "2-realizability" -- reallzability with two threshold elements. The general approach produces a good solution in any case, but one guaranteed optimal only for 2-realizable functions. We use here a geometric terminology; this new language is also used in the second section, where "higher" necessary conditions for realizability are discussed. A conjecture that certain of these conditions might be sufficient is disproved; three related conditions are treated in a common language. The final section considers optimal integral single-stage realizations, and disproves a conjecture made last year: That such a realization gives equal arguments equal weights.

In a previous paper [1] we discussed a stochastic projected gradient algorithm (in the context of an adaptive signal detection problem) which can be used to find a constrained optimum point for a concave or convex objective function subject to linear or nonlinear constraints which form a connected region, even when we do not have the objective function available, but only have a noisy estimate of the objective function available. When the constraint consists of only one linear equation, we said that one can prove convergence to the constrained optimum value and bound the rate of convergence of the algorithm to the constrained optimum value. A proof was given in [1] under noise free conditions. The purpose of this short paper is to extend the proof to the noisy case.

This paper surveys some of the unifying approaches used to derive formulae for updating the inverse Hessian approximations in quasi-Newton algorithms and presents a new approach of this kind based on geometric considerations. The paper discusses the intuitive motivations for these approaches and their potential in providing explanations for observed behavior of such algorithms.

This paper concerns switching networks which consist of n identical combinational logic cells interconnected from left to right by "alpha" communication channels into linear arrays. The synchronous cells in these networks have unit switching delays separating their receipts of external x and left-neighbor alpha inputs from their corresponding productions of external z and right-neighbor alpha outputs. Three basic types of alpha transient behavior are discussed for such networks. In the first type, all transients extend to no more than a bounded number of cells to the right of each x change; in the second, all transients propagate all the way to the right boundary of the network; and in the third, any transient may or may not propagate to the right boundary of the network depending upon the x sequence to the right of the x change in question. In all three cases, necessary and sufficient conditions are given on the type of alpha logic allowed. These conditions are expressed in terms of corresponding alpha state graph structure. The paper's main results hinge on certain properties of a new type of state subgraph, and on an indirect application of permutation groups to the state-pair transition problem. A section of examples proves that individual graphs can contain any mixture of the above three types of transient behavior.

This paper concerns switching networks which consist of n identical combinational logic cells interconnected from left to right by alpha communication channels into linear arrays. The synchronous cells in these networks have unit switching delays separating their receipts of external x and left-neighbor alpha inputs from their corresponding productions of external z and right-neighbor alpha outputs. Three basic types of alpha transient behavior are discussed for such networks. In the first type, all transients extend to no more than a bounded number of cells to the right of each x change; in the second, all transients propagate all the way to the right boundary of the network; and in the third, any transient may or may not propagate to the right boundary of the network depending upon the x sequence to the right of the x change in question. In all three cases, necessary and sufficient conditions are given on the type of alpha logic allowed. These conditions are expressed in terms of corresponding alpha state graph structure. The paper's main results hinge on certain properties of a new type of state subgraph, and on an indirect application of permutation groups to the state-pair transition problem. A section of examples proves that individual graphs can contain any mixture of the above three types of transient behavior.

Operational requirements often make it necessary for several transmitters and receivers to operate in close proximity with small frequency separations. The important interference parameters that limit operation under these conditions are transmitter emission spectra, intermodulation, cross-modulation, and desensitization. This paper discusses the EMC problems produced by strong interfering signals in the neighborhood of the receiver tuned frequency. The region of concern, in a typical receiver, may consist of a considerable number of channels on both sides of the receiver-tuned frequency. This paper outlines methods that may be used to calculate the interference resulting from adjacent signals; presents mathematical models that describe the significant effects (such as intermodulation, cross-modulation, and desensitization); and describes methods for utilizing spectrum signature data for evaluating the models for a specific equipment. In addition, for cases where specific receiver measurements are not available, the paper presents general receiver models that have been derived from an analysis of spectrum signature data. The results of the work described in this paper will help to provide an understanding of the basic factors that contribute to the receiver susceptibility to interfering signals in adjacent channels. This information may be used by interference analysts in the calculation of receiver susceptibility and the generation of realistic EMC specifications, and by equipment designers to develop less susceptible equipments.

The optimum operation for the smoothing of time series to minimize mean square error is well known when the signal and noise statistics are completely available. When the statistics of either or both are partially or completely unknown, however, there exists no universally agreed upon optimum procedure. This paper considers the problem of linear smoothing when the noise is additive, signal independent with first and second moments known while the signal statistics are completely unknown. This case is of practical interest since frequently signal assumptions are difficult to make whereas the noise can usually be assumed to be sample-to-sample uncorrelated with mean zero and known variance. This latter assumption of known noise power can be relaxed in some instances as will be discussed in a future paper.

This paper presents some novel approaches which are useful for identifying, filtering, and smoothing a finite number of graphs or signals which are simultaneously present, assuming that some or all of the a priori information about the function of the signals, such as form and parameters, is known. Under some circumstances, such as seismic wave detection in connection with oil exploration experiments, only the discrete data points are available. Traditionally, when these discrete data points are scattered over a two-dimensional space they are processed manually, using a family of templates. The algorithms developed in this work will enable us to process these data points with the use of digital computers. This paper tries to answer the questions such as: "What is the best algorithm to process data of this kind in order to achieve optimal usage of the available data and accuracy of identification?" "What is the required computer memory capacity and speed of convergence of the algorithms?" etc.

Among the performance indices used in the processing of acoustic array signals are those that can be expressed as a ratio of quadratic forms in the beamformer weights. Popular indices in this class include directivity, array gain, efficiency factor, and supergain ratio. This paper presents a technique for optimizing a quadratic-form-ratio performance index over the beamformer weights subject to generally nonzero constraints on the value of the array power pattern in multiple directions. Previous related results include performance optimization with no constraints, with specified pattern nulls, and with constraints on the complex-valued beam pattern. When an array designer is interested just in the beam pattern magnitude, the additional specification of pattern phase required by these techniques generally penalizes the optimization. Only magnitude (power pattern) constraints are imposed in this paper. The optimum weights are shown to satisfy a characteristic equation with quadratic constraints that is related to a more familiar optimization problem for which solution methods exist. Applications include performance maximization with fixed main-lobe beamwidth and/or sidelobe values. Examples are given for a circular array.

The subject of this paper is the analysis of a class of decision/control problems that evolve from common problems of queueing theory in a game theoretic context. These problems possess the conceptual structure of differential games and control theory, while their analysis is based on techniques and concepts of the theory of point processes. Thus, these problems are termed point process games. In this paper typical examples are worked out in detail.

This paper is concerned with System Properties of a class of systems described by functional differential equations of the delay-type. Some results on controlability are presented for a very general class. For linear time invariant delay-systems the above results are put in a more concrete form using spectral decompositions. In this framework, conditions for state and output stabilizability are derived. These conditions constitute the main result of the paper. Detailed proofs and more extensive comments may be found in [1] [2].

This paper presents an extension of the Muller-Bartky theory of asynchronous switching circuits. A circuit specification is a set of vectors whose components are non-negative integers and which satisfies certain other conditions. The j-th component of such a vector represents the number of times which the signal at the j-th node has changed since the circuit was started. The principal result of the paper characterizes the class of circuit specifications which may be realized by semimodular switching circuits. An alternative method of circuit specification is defined and shown to be equivalent.

This paper formulates the problem of determining the optimal stabilization policy for a simple macroeconomic model as a state-regulator problem. In the general case where the government has a finite planning horizon and where investment is generated by a flexible accelerator the optimal government policy is shown to satisfy a first order linear differential equation with variable coefficients. With an infinite horizon these coefficients become constants and upon integrating the equation the optimal government expenditure is seen to be a mixture of a proportional and an integral policy. When the simplet instantaneous accelerator is assumed the policy becomes purely proportional. In the latter part of the paper this case is extended to the situtation where various parameters characterizing the economy are stochastic. Similar control laws are obtained, although in this case the intensity of control will depend upon the noise in the system.

In a recent paper, a bound on the probability of runaway for a decision-directed receiver with unknown a priori probabilities was obtained. The analysis approximated the dependent learning process with a random walk model with independent increments. It is the purpose of this paper to demonstrate that by incorporating the central limit theorem into the above-mentioned analysis, a simple expression for a bound on the probability of runaway can be obtained. Furthermore, by applying a multivariate version of the theorem, the modified technique can be extended to analyze decision-directed receivers with several unknown parameters and the corresponding runaway bounds can be obtained. (By contrast, it is well known that multi-dimensional restricted random walk models are extremely difficult to study.) The results of this study again show that the probability of runaway is quite small even at moderate signal-to-noise conditions.

The paper addresses both the discrete and continuous time linear-quadratic control problem with an arbitrary number of controllers each of which is making proprietary measurements. To force a tractable solution, the structure of the controllers have been fixed, resulting in a time varying matrix parameter optimization problem. Necessary conditions for the solution of the discretized problem are given. The analogous conditions for the continuous case are referenced; viz., the document from which this paper is an abridgement. An example is considered which permits comparison of the solutions developed here to that resulting from the separation principle.

The principal result described in this paper is the equivalence of the following statements: (1) Every set accepted by a nondeterministic one-way two-head finite automaton can be accepted by a deterministic two-way k-head finite automaton, for some k. (2) The context-free language LPΣ (described in the paper) is recognized by a (log n)-tape bounded deterministic Turing machine. (3) Every set accepted by a L(n)-tape bounded nondeterministic Turing machine is recognized by a L(n)-tape bounded deterministic Turing machine, provided L(n) ≥ log n. This work extends results reported earlier by Hartmanis [2], Savitch [9,10], and Lewis, Stearns, and Hartmanis [6].

This paper continues investigations pertaining to recursive bounds on computing resources (such as time or memory) and the amount by which these bounds must be increased if new computations are to occur within the new bound. The paper proves that no recursive operator can increase every recursive bound enough to reach new computations. In other words, given any general recursive operator F[ ], there is an arbitarily large recursive t( ) such that between bound t( ) and bound F[t( )]( ) there is a gap in which no new computation runs. This demonstrates that the gap phenomenon first discovered by Borodin for composition is a deeply intrinsic property of computational complexity measures. Moreover, the Operator Gap Theorem proved here is shown to be the strongest possible gap theorem for general recursive operators. The proof involves a priority argument but is sufficiently self-contained that it can easily be read by a wide audience. The paper also discusses interesting connections between the Operator Gap Theorem and McCreight & Meyer's important result that every complexity class can be named by a function from a measured set.

Hyperbolic or wave like distributed parameter processes occur in a number of physical settings. Several identification techniques are discussed in this paper which are based on orthogonality relationships of these hyperbolic processes in the time variable, and on characteristic theory, respectively. The paper discusses and interprets the parameter identification process, its measurement requirements, and examples of both identifiable and non-identifiable processes.

This paper consists of the following: recursive methods of generating self-dual threshold functions, a class of self-dual threshold functions which have interesting properties, a lower bound of the number of threshold functions, and a lower bound of a maximum weight. Any threshold function can be reduced from a self-dual threshold function by assigning 1 or 0 to some variable. In this paper, discussion is limited to self-dual threshold functions but it does not lose generality.

Neighborhood search has been used with some success in providing approximate solutions to discrete optimization problems. The technique produces solutions which may be locally but not globally optimal. For a particular class of problems this paper describes a method for analyzing the relative effectiveness associated with different neighborhoods in terms of the probability that a local optimum is in fact global. The analysis is then applied to the 5-city Travelling Salesman Problem for which two neighborhoods of like size are compared. It is found that local optimality with respect to one of these neighborhoods is roughly twice as likely to indicate global optimality as is local optimality with respect to the other. It is felt that further development of the techniques described in this paper might lead to computer designed heuristics for certain discrete optimization problems.

We pursue in this paper some of the ideas discussed a year ago at the First Annual Symposium on Switching Theory and Logical Design. For a general discussion of threshold logic, and for definitions and motivations of the terms used below, the reader is referred to "Single Stage Threshold Logic" also published in this volume [13]. Also, a general survey of recent papers in the subject has been published elsewhere [14]. The main subject treated below is compound synthesis. The importance of such a study was shown last year: The family of functions of n arguments realizable in a single stage becomes a vanishing fraction of all switching functions of n arguments as n grows (for n = 7 the ratio is about 1028 1/2). We provide an algorithm for determining "2-realizability" -- reallzability with two threshold elements. The general approach produces a good solution in any case, but one guaranteed optimal only for 2-realizable functions. We use here a geometric terminology; this new language is also used in the second section, where "higher" necessary conditions for realizability are discussed. A conjecture that certain of these conditions might be sufficient is disproved; three related conditions are treated in a common language. The final section considers optimal integral single-stage realizations, and disproves a conjecture made last year: That such a realization gives equal arguments equal weights.

This paper explains our approach to the problem of pattern recognition by serial computer. The rudimentary theory of vision presented here lies within the framework of automata theory. Our goal is to classify the types of patterns that can be recognized by an automaton that scans a finite 2-dimensional tape. For example, we would like to know if an automaton can decide whether or not a given pattern on a tape forms a connected region. Although we have solved a number of problems, we have failed to solve this connectedness problem. This paper merely begins to describe the action of automata in higher dimensions. Our goal now is to generalize the theory presented here and make it applicable to a wide variety of pattern-recognizing machines.

This paper presents a preliminary algorithm for determining the orders of a linear stochastic dynamic system solely from the observation of the system output. The scalar transfer function of the system contains both poles and zeros, however, no a priori information is available about the numbers and values of these poles and zeros. The driving input of this system is assumed to be white. Such a system is called a mixed type process, since it is a combination of the autoregressive (all-pole) and the moving-average (all zero) processes. The objective of this algorithm is thus to determine the number of poles (order of the autoregressive portion of the process) and the number of zeros (order of the moving-average portion of the process) of the mixed type process. The algorithm suggested in this paper is based on a two stage process: first take those output correlations which follow a repetitive pattern to determine the order of the autoregressive portion, then proceed to estimate the autoregressive parameters and lower the index of the correlation until the significant deviation from the repetitive pattern is observed, the order of the moving-average then can be determined.

In this paper two closely related problems in automata theory are considered: 1) What is the time required for a network of elements, each with a limited number of inputs, to compute a finite function? 2) What is the time required for a finite automaton, realized as such a network, to compute its output function? Winograd has considered the first problem, especially for addition and group multiplication [1] and numerical multiplication [2]. By laying bare the methodology implicit in his work, we form a basis upon which we can erect a thoroughgoing analysis of multiplication in groups and semigroups and also can analyze computation of various finite functions. This paper presents the beginning of such an analysis.

The efficacy of Geoffrion's taxonomy of large-scale mathematical programming is being investigated in the context of state-constrained optimal control problems. One algorithm which can be synthesized from this taxonomy is called Generalized Benders Decomposition. In this paper, we first consider its direct application to optimal control. Numerical experience indicates the best performance is achieved when the dynamics are non-linear in the control and relatively few state-constraints are violated during the iteration process. To combat this latter difficulty, the algorithm is combined with parametric penalty methods. Some guidelines are provided on how to achieve improved numerical performance using this combined approach.

This paper deals with the problem of enforcing standards of maximum allowable atmospheric contaminants. This enforcement has to be done by deciding whether the actual level of contaminant is in violation or compliance with the standards. Due to inherent uncertainties, a decision is to be made only if the probability of error is below a prescribed level. The measurements of contaminant are modeled as a set of lognormal random variables with unknown mean and variance. A uniformly most powerful unbiased test is developed to test their mean against a given threshold. It is shown that the test can be carried out in a very simple manner with the help of a decision chart. This is done by plotting a point defined by the sufficient statistics of the observations and reading off the decision. The estimate of the actual level of contaminant is also discussed.

A digital filter produces an output sequence {yn} by operating on an input sequence {xn} in accordance with a specified computational algorithm. We consider in this paper digital filters of the recursive type characterized in the time domain by a linear constant coefficient difference equation.

Let U1,U2,...,Udbe totally ordered sets and let V be a set of n d-dimensional vectors in U1× U2× ... × Ud. A partial ordering is defined on V in a natural way. We consider the problem of finding all maximal elements of V with respect to the partial ordering. The computational complexity of the problem is defined to be the maximum number of required comparisons of two components and is denoted by Cd(n). It is trivial that C1(n) = n-1 and Cd(n) ≤ 0 (n2) for d ≥ 2. previous results are Cd(n) ≤ 0 (n log2n) for d = 2,3. in this paper, we show 1. Cd(n) ≤ 0 (n(log2n)d-2) for d ≥ 4. 2. Cd(n) ≥ ⌈log2n! ⌉ for d ≥ 2.

whose discrete taps could be subjected to arbitrary amplitude and phase weighting and then summed. manner arbitrary impulse responses could be synthesized leading to a universal filte I. .s.:lementation. Although fixed amplitude weighting of taps is rather simply obtained in surface acoustic wave 'liters, nondispersive phase weighting is very difficult. adaptive transversal filter may be composed of a number of fixed orthonormally coded tapped delay lines. It is shown that by changing the amplitude drive to each tapped line input transducer the effect of arbitrary amplitude and phase weighting may be obtained. frequency filters. coded surface wave delay lines. The original paper by Kallman described a transversal filter composed of a tapped delay line

This paper discusses the discrete version of the adaptive observer problem. First, a stable identification scheme for a linear discrete multivariable system when all its state variables are accessible is presented. The scheme is then extended to obtain stable identification laws for a single variable system using only input-output data.

In this paper a frequency-domain adaptive array structure is derived that processes data in selected regions of frequency-wave-number space to provide an MMSE estimate of a signal component of the observed acoustic field. The desired "optimal" processor structure is derived by appealing to the Sherman-Morrison inversion lemma to invert the sum of a diagonal noise matrix and several diadic matrices corresponding to plane-wave propagating signal and interference fields. The structure reduces to a parallel structure of beamformer-gain elements whose beamformer directions (phase delays) and gains are unknown because of a priori ignorance concerning interference directions and levels. The structure is adapted to these uncertainties by forming a stochastic approximation algorithm for the gains of several beams directed to a finite set of possible interference directions.

This paper solves a particular min-max problem where the minimizing variables not only influence the performance index but also constrain the domain of action of the maximizing variables. The problem is approached as minimization of a supremal value function. It is shown here that if a weaker form of the classical sensitivity theorem of non-linear programming holds, then directional derivatives, and in some cases even ordinary derivatives, of the supremal value function exist. The existence of ordinary derivatives is especially useful for computation purposes, in that case the min-max becomes a stationary point under equality constraints with respect to both players separately. The problem originates from a new approach for control design of a dynamic uncertain system when a bound in norm of the approximation error is guaranteed.

This paper discusses the concept of strong instrumental variables and strong instrumental matrix sequences for the estimation of the transfer-function parameters of discrete-time, time-invariant models of linear systems. It is shown that strong instrumental variable estimators are strongly consistent and a sufficient condition for the estimator to be asymtotically unbiased is given. Moreover, it is shown that with a persistently exciting signal of appropriate order for an input, "virtually" any discrete-time, time-invariant, linear system model of appropriate order can be used to generate strong instrumental variables.

This paper considers the problem of estimation of classification error in pattern recognition. A theorem is presented to obtain the changes in the eigenvalues and eigenvectors of matrices of the form S 2 −1 S 1 , when there are changes of first order of smallness in the real symmetric matrices S i , i = 1, 2. Based on this theory a computational algorithm is developed for the estimation of classification error of Fisher classifier, using leaving groups out method.

This paper generalized the approach of Ref. [1] for the design of optimal inputs to MIMO systems with process or driving noise. First an expression for the information matrix is derived and it is shown to consist of two parts, one depending on the designed input and the other depending on the process noise input. The equivalence relationships between D-optimal designs and min-max designs are obtained leading up to numerical algorithms for computing globally optimal designs. Easily computable bounds are derived for the loss in performance due to suboptimal designs. It is shown that the optimal input may be chosen to have a discrete spectrum with a finite number of frequencies.

This paper examines a class of heuristics for maintaining a sequential list in approximately optimal order with respect to the average time required to search for a specified element, assuming that each element is searched for with a fixed probability independent of previous searches performed. The “move to front” and “transposition” heuristics are shown to be optimal to within a constant factor, and the transposition rule is shown to be the more efficient of the two. Empirical evidence suggests that transposition is in fact optimal for any distribution of search probabilities.

Trajectory sensitivity with respect to small random perturbations in initial state and plant parameters is investigated. An upper bound on the maximal spread around the nominal trajectory at time t for a probability level p is established in the paper. If a sufficiently high degree of exponential stability is attained by additional feedback, the modified system has a lower upper bound compared to that for the system without additional feedback. Moreover, when a deterministic observer is employed, the upper bound is increased but it is still lower than that corresponding to the system without additional feedback and without an observer.

Surveillance systems are often required to simultaneously estimate the trajectory parameters of several targets. This problem is complicated significantly in high target density situations since the individual data sequences required by standard estimation algorithms are difficult to form. This paper discusses certain computational aspects of assigning closely spaced sensor returns to individual tracks. We refer to this as a "multiple choice" estimation problem since the real tracks are generally hidden in a large set F of feasible tracks. Forming the feasible track set F on the basis of a priori knowledge of the problem is the first step on the assignment process. A subset of the potential tracks contained in F is then selected on the basis accomplished by 0-1 integer programming, as we now illustrate for a simple discrete linear problem.

Using frequency domain techniques, this paper derives several boundedness (stability) conditions for pulse-modulated systems. These conditions extend the frequency approach to systems without strict sector non-linearities.

In this paper the estimation of unknown, time-invariant parameters that, if known, completely specify a discrete, linear dynamic model with Gaussian disturbances, is considered. Following the Bayesian approach the unknown parameters are modeled as random variables with known a priori probability density. Optimal, in the mean-square-error sense, estimates are desired. However, this requires recursive updating and storage of a non-Gaussian, and more importantly, a nonreproducing density. Therefore, exact realization of the nonlinear parameter estimators requires immense computational effort and storage capacity. To alleviate these difficulties, splines functions are used for the approximate realization of the Bayesian parameter estimation algorithm. Specifically, variation-diminishing splines are used, which are pieces of smoothly tied polynomials to approximate the a posteriori probability density (pdf). This approximation of the pdf is specified in terms of a finite number of parameters, yielding a readily implementable approximation of the exact but unimplementable parameter estimation algorithm. A convergence theorem is obtained for the convergence of the spline algorithm to the optimal algorithm, as well as two implementable error bounds. Extensive numerical simulation indicates that the spline algorithm performs well, yielding parameter estimates very close to the true values. In summary, the salient characteristics of the proposed spline-based estimator are as follows: 1. (a) it is readily implementable, its realization requiring essentially a bank of Kalman filters and integration of piece-wise polynomial functions; 2. (b) the spline algorithm is based essentially on an imbedded quantization algorithm, namely, the one corresponding to the bank of Karman filters used; 3. (c) as such, the spline estimator has greater computational requirements than the associated quantization algorithm; but 4. (d) the spline algorithm is more accurate than the quantization algorithm. In view of the above, the spline-based estimator should prove useful in practical applications of parameter estimation as well as of general nonlinear estimation.

The aim of this paper is to describe some of the important concepts and techniques which seem to me to help provide a solution of the stationary time series problem (prediction and model identification). Section 1 reviews models. Section 2 reviews prediction theory and develops criteria of closeness of a "fitted" model to a "true" model. The central role of the infinite autoregressive transfer function g? is developed, and the time series modeling problem is defined to be the estimation of g?. Section 3 describe auto-regressive estimators of g?. It introduces a criterion for selecting the order of an auto-regressive estimator which can be regarded as determining the order of an AR scheme when in fact the time series is generated by an AR scheme of finite order.