Abstract Network tomography aims at estimating source–destination traffic rates from link traffic measurements. This inverse problem was formulated by Vardi in 1996 for Poisson traffic over networks operating under deterministic as well as random routing regimes. In this article, we expand Vardi's second‐order moment matching rate estimation approach to higher‐order cumulant matching with the goal of increasing the column rank of the mapping and consequently improving the rate estimation accuracy. We develop a systematic set of linear cumulant matching equations and express them compactly in terms of the Khatri–Rao product. Both least squares estimation and iterative minimum I‐divergence estimation are considered. We develop an upper bound on the mean squared error (MSE) in least squares rate estimation from empirical cumulants. We demonstrate that supplementing Vardi's approach with the third‐order empirical cumulant reduces its minimum averaged normalized MSE in rate estimation by almost 20% when iterative minimum I‐divergence estimation was used.

In this article, we discuss the relationship between subcycle and instantaneous power metrics in polyphase ac systems. While both approaches have very low computational cost, which makes them suitable for real-time control of industrial processes, the two-sample subcycle scheme offers several distinct advantages over the purely-instantaneous approach. In particular, we show that: a) the level of steady-state fluctuation of subcycle power metrics that use only two time-domain samples is significantly lower than that of purely-instantaneous metrics, and b) the subcycle scheme generates several additional power metrics, which can be used to detect onset of faults, and accurately determine their duration. We illustrate our points using both synthetic and (real-life) industrial examples. In addition, we examine the connection between the two-sample subcycle scheme and other near-instantaneous approaches, based on derivatives of currents and voltages. We again observe a significantly lower numerical sensitivity for the two-sample subcycle quantities. Furthermore, two-sample quantities have a unique feature that they can naturally be extended to more samples, with concomitant reduction in fluctuations, better accuracy and with only moderate increase in computational cost. We posit that the subcycle approach has promise in detection, control, and classification applications.

We present an augmented continuous-discrete extended Kalman filter (EKF), capable of mitigating the effects of bad data and (random) measurement delay. We use an innovations-based Fisher-type scheme to identify and remove occurrences of corrupted sensor observations. We rely on time-stamp technology to accurately determine the duration of delay experience d by each received measurement packet. The length of delay is then used to construct a “delay-aware” optimum MMSE state estimate. A Flywheel Energy Storage System (FESS) example is used to demonstrate the high quality of dynamic state estimation achieved with the proposed method in the presence of bad sensor samples and delayed measurement packets.

An intuitive procedure for determining the location as well as reducing the effect of digital spurs in block-parallel digital filter realizations is proposed. The method is based on modeling voltage/current waveforms generated by the switching activity of digital clocks in each polyphase component of a blockparallel digital filter as electromagnetic waves travelling over a linear medium. Using superposition, frequency analysis as well as information regarding the area (size) and layout (placement) of the synthesized polyphase filter, the spurs generated at the output of the overall system are modeled as a weighted sum of voltage/current interference waveforms. Digital spur mitigation is achieved by calculating a strategic clock phasing scheme based on the contribution of these weighting coefficients. The technique and examples presented are intended to serve as a high-speed filter realization reference for Digital and DSP ASIC developers.

We describe a method for generating causal, stable, numerically robust, IIR, customizable (application specific), perfect reconstruction (PR) filter-banks with zero (or adjustable) reconstruction delay. The ideas presented in this paper extend the concept of Dynamic Phasors as well as the concept of the so-called Phasor Bank Transform, which constitute specific subclasses of filter-banks. We provide an explicit compact characterization of the optimally-robust reconstruction stage of this transform, which can be used with any (customized) choice of its analysis stage. Since the Phasor Bank transform allows causal (real-time) delay-free perfect reconstruction of any input waveform, it is perfectly suited for (closed-loop) control applications. Although the motivating application area of Phasor Banks is Power Systems, such as tracking of time-variant harmonic content under both steady-state (nearly-periodic) and transient operating conditions, the technique presented here can be used in a variety of closed loop applications.

We present a technique for determining the autocorrelation of an arbitrarily time-variant system response. Our approach relies on a key relation, introduced in [1], between the system response autocorrelation function and certain 2nd and 4th order moments of the system input and (noisy) output signals, with no other prior information about the dynamics of the system response required. We introduce a “Wiener problem” interpretation of this key relation, which enables us to benefit from the wealth of existing results about the dynamics and performance of standard adaptive filters. In particular, we propose time-recursive estimates for the system response autocorrelation, with significantly reduced computational cost, as compared to previously proposed (nonrecursive) estimates. Moreover, our procedure can also be customized to track (slow) variations in the system response autocorrelation when such variations are present. We use an example to demonstrate the advantage of applying standard adaptive algorithms such as LMS, NLMS or RLS to obtain an estimate of the desired system response autocorrelation.

The paper formulates and solves the problem of optimizing power flows in polyphase systems with significant source (line) impedance. The authors present two fundamental performance bounds, which give rise to explicit formulas for the apparent power and optimally compensated load current. Properties of the solution are illustrated on the example of an asymmetrical three-phase induction motor supplied with unbalanced non-sinusoidal voltages.

The signal subspace approach for speech enhancement is extended to colored-noise processes. Explicit forms for the linear time-domain- and spectral-domain-constrained estimators are presented. These estimators minimize the average signal distortion power for given constraints on the residual noise power in the time and spectral domains, respectively. Equivalent implementations of the two estimators using the whitening approach are described.

Efficient computation of extensions of banded, partially known covariance matrices is provided by the classical Levinson algorithm. One contribution of this paper is the introduction of a generalization of this algorithm that is applicable to a substantially broader class of extension problems. This generalized algorithm can compute unknown covariance elements in any order that satisfies certain graph-theoretic properties, which we describe. This flexibility, which is not provided by the classical Levinson algorithm, is then harnessed in a second contribution of this paper, the identification of a multiscale autoregressive (MAR) model for the maximum-entropy (ME) extension of a banded, partially known covariance matrix. The computational complexity of MAR model identification is an order of magnitude below that of explicitly computing a full covariance extension and is comparable to that required to build a standard autoregressive (AR) model using the classical Levinson algorithm.

We introduce a technique for identification of systems with arbitrarily time-variant responses from samples of their input and output signals, and without using any prior information about the dynamics of the unknown system response. Our technique uses only input-output data to determine the parameters that are required in the construction of an extended RLS estimator (as described in [3]) for the unknown system response. We demonstrate the utility of our approach via a numerical example.

This article reviews analytical results and practical experience with randomized modulation in power electronic converters. After providing a brief overview of power electronics and of relevant switching patterns, the authors present performance specifications for converters (in terms of electromagnetic interference, vibrations and acoustic noise), and classify various randomized switching schemes. They review the most directly related references next, and introduce the mathematical objects of primary interest-averaged autocorrelation and power spectrum. They then list some results for the (simpler) case of stationary modulation and consider in detail the more general case of randomized switching based on Markov chains. Their aim is twofold-to present results important for practice and to establish connections with several areas of applied probability. Finally, they consider the synthesis task for the two cases of randomized modulation, followed by brief conclusions.

Dynamic magnetic resonance imaging (MRI) refers to the acquisition of a sequence of MRI images to monitor temporal changes in tissue structure. We present a method for the estimation of dynamic MRI sequences based on two complimentary strategies: an adaptive framework for the estimation of the MRI images themselves, and an adaptive method to tailor the MRI system excitations for each data acquisition. We refer to this method as the doubly adaptive temporal update method (DATUM) for dynamic MRI. Analysis of the adaptive image estimate framework shows that calculating the optimal system excitations for each new image requires complete knowledge of the next image in the sequence. Since this is not realizable, we introduce a linear predictor to aid in determining appropriate excitations. Simulated examples using real MRI data are included to illustrate that the doubly adaptive strategy can provide estimates with lower steady state error than previously proposed methods and also the ability to recover from dramatic changes in the image sequence.

Motivated by work in the area of dynamic magnetic resonance imaging (MRI), we develop a new approach to the problem of reduced-order MRI acquisition. Efforts in this field have concentrated on the use of Fourier and singular value decomposition (SVD) methods to obtain low-order representations of an entire image plane. We augment this work to the case of imaging an arbitrarily-shaped region of interest (ROI) embedded within the full image. After developing a natural error metric for this problem, we show that determining the minimal order required to meet a prescribed error level is in general intractable, but can be solved under certain assumptions. We then develop an optimization approach to the related problem of minimizing the error for a given order. Finally, we demonstrate the utility of this approach and its advantages over existing Fourier and SVD methods on a number of MRI images.

We present a methodology for adaptive filtering and system identification under the cyclostationary regime. Our technique is based on a deterministic periodic least-squares criterion, and gives rise to adaptive periodic recursive-least-squares (P-RLS) algorithms. Furthermore, we show that every adaptive RLS algorithm has a P-RLS counterpart, which has exactly the same architecture and the same performance attributes, and differs only in the length of the delay used in its time-update recursions.

We introduce a technique for identification of systems with arbitrarily time-variant responses from samples of their input and output signals, and without using any prior information about the dynamics of the unknown system response. Our technique is based on the use of optimized averaging filters for the estimation of time-variant second order moments. We demonstrate the utility of our approach and the quality of the resulting estimates via a numerical example.

In this work we develop an adaptive nonlinear estimation technique, polynomial model-based, that has guaranteed stability and makes parsimonious use of coefficients. Our approach to the development of reduced-complexity adaptive nonlinear filters is based on a combination of: (a) The Wiener model of nonlinear systems (both FIR and IIR) and its application to nonlinear estimation from white Gaussian signals; (b) Wiener's notion of fixed (Laguerre) pre-orthogonalization, which we have extended to include adaptive pre-orthogonalization with respect to arbitrary (non-white and non-Gaussian) input signals; (c) Efficient implementation of memoryless nonlinear maps for uncorrelated inputs based on (Hermite) orthogonal polynomials; (d) Application of suitably modified RLS and LMS adaptation techniques to determine the coefficients of such nonlinear maps.

An analytical framework for the implementation of optimal filters in the multiresolution (i.e., subband) domain is presented. In particular, we concentrate on filter bank based on the notions of wavelets and wave-packets. We show how the notion of sparse estimation can lead to significant reduction in computational cost, with only a minor degradation in performance. The combination of a wavelet-based filter bank with a sparse estimation scheme results in a configuration with five design parameters: (i) resolution level, (ii) degree of subband channel overlap, (iii) subband utilization ratio, (iv) estimation sparsity, and (v) filter order. We demonstrate the effect of each one of these design parameters on the over-all cost-performance trade-off.

In this paper, we developed a systematic frequency domain approach to analyze adaptive tracking algorithms for fast time-varying channels. The analysis is performed with the help of two new concepts, a tracking filter and a tracking error filter, which are used to calculate the mean square identification error (MSIE). First, we analyze existing algorithms, the least mean squares (LMS) algorithm, the exponential windowed recursive least squares (EW-RLS) algorithm and the rectangular windowed recursive least squares (RW-RLS) algorithm. The equivalence of the three algorithms is demonstrated by employing the frequency domain method. A unified expression for the MSIE of all three algorithms is derived. Secondly, we use the frequency domain analysis method to develop an optimal windowed recursive least squares (OW-RLS) algorithm. We derive the expression for the MSIE of an arbitrary windowed RLS algorithm and optimize the window shape to minimize the MSIE. Compared with an exponential window having an optimized forgetting factor, an optimal window results in a significant improvement in the h MSIE. Thirdly, we propose two types of robust windows, the average robust window and the minimax robust window. The RLS algorithms designed with these windows have near-optimal performance, but do not require detailed statistics of the channel.>

The authors use the classical Schur reduction procedure to give a lattice filter implementation of the Chandrasekhar recursions. The derivation is based on the observation that the covariance matrix of a process with a time-invariant state-space model is structured. This allows one to easily derive the connection between the Schur algorithm and spectral factorization and to extend the Chandrasekhar recursions to the case of nonsymmetric Riccati equations. The Chandrasekhar recursions can be implemented in scalar steps using a sequence of well-defined elementary (hyperbolic and Givens) rotations.>

General order-recursive least-squares estimation employing a sliding window is described. It is shown that time and order updates of any order-recursive sliding window least-squares algorithm can be obtained solely by 3*3 hyperbolic Householder transformations. Applying this general observation to the sliding window least-squares estimation of time-series signals results in a new algorithm: the hyperbolic Householder lattice (HHL) algorithm. This work broadens the range of applications of QR-decomposition (QRD)-based adaptive least-squares algorithms by allowing a sliding window formulation in addition to the known exponentially windowed form.>

This paper is concerned with the analysis of synchronous, special purpose, multiple-processor systems (including, e.g., systolic arrays). The analysis problem is that of determining the algorithm executed by the system. There has been some prior work in this area, especially by Melhem and Rheinboldt [SIAM J. Comput.,13 (1984), pp. 541–565], who were the first to obtain a general solution. The approach used here is different and apparently simpler. By combining ideas well known in system theory with certain graph-theoretical concepts, a simple procedure for recovering, within a natural equivalence, the iterative algorithm executed by a given special purpose synchronous computing array is obtained. The solution is based on reversing (modulo equivalence) the process by which an iterative algorithm is translated into a logical circuit.

The authors present scalar implementations of multichannel fast recursive least squares algorithms in transversal filter form (so-called FTF). By processing the different channels sequentially, i.e one at a time, the processing of any channel reduces to that of the single-channel algorithm. This sequential processing decomposes the multichannel algorithm into a set of intertwined single-channel algorithms. Geometrically, this corresponds to a modified Gram-Schmidt orthogonalization of multichannel error vectors. Algebraically, this technique corresponds to matrix triangularization of multichannel error covariance matrices and converts matrix operations into a regular set of scalar operations. Algorithm structures that are amenable to VLSI implementation on arrays of parallel processors follow naturally from this approach. Numerically, the resulting algorithm benefits from the advantages of triangularization techniques in block processing. Stabilization techniques for control of numerical error propagation in the update recursions are incorporated.>

Several computationally efficient versions of the Levinson algorithm for solving linear equations with Toeplitz and quasi-Toeplitz matrices are presented, motivated by a new stability test. The new versions require half the number of multiplications and the same number of additions as the conventional form of the Levinson algorithm. The saving is achieved by using three-term (rather than two-term) recursions and propagating them in an impedance/admittance (or immittance) domain rather than the conventional scattering domain. One of the recursions coincides with recent results of P. Delsarte and Y. Genin (IEEE Trans., Acoust. Speech, Signal Proc., vol.ASSP-34, p.470-8, June 1986) on split Levinson algorithms for symmetric Toeplitz matrices, where the efficiency is gained by using the symmetric and skew-symmetric versions of the usual polynomials. This special structure is lost in the quasi-Toeplitz case, but one still can obtain similar computational reductions by suitably using three-term recursions in the immittance domain.>

A universal characterization of maximum-entropy covariances for multidimensional signals is presented. It is shown that the maximum-entropy extension of an arbitrary partial covariance of a nonstationary multidimensional signal always has a banded inverse, i.e the inverse is sparse and has the same support as the given partial covariance. A dual formulation of the problem that makes it possible to approximate maximum-entropy extensions with models selected from suitably constrained model sets is introduced. It is proved that the best approximation in terms of multidimensional recursible autoregressive models can be determined by solving a set of linear equations. A simple graph-theoretic criterion is introduced to characterize those partial covariances whose maximum-entropy extension coincides with its autoregressive approximation, as in the conventional (one-dimensional stationary) maximum-entropy problem.>

A simple general method for overcoming singularities in the Levinson (and Schur) recursions for Toeplitz systems is presented. It is based on a generalization of the conventional three-term recursion for polynomials orthogonal on the unit circle: the scalar coefficients of the conventional three-term recursion are replaced by polynomial coefficients whose degree is determined by the depth of singularity. The depth of the singularity is related to the number of additional zero elements that occur in the Schur recursion. The authors' method also makes it possible to recursively determine the inertia of a Hermitian Toeplitz matrix.>

An explicit expression is derived for the minimum discrimination information (MDI) measure with respect to Gaussian priors for sources characterized by their mean and by any principal leading block of their covariance matrix. An explicit expression is provided for the MDI extension of the given partial covariance of the source with respect to a Gaussian prior. For zero-mean sources and zero-mean Gaussian priors that are asymptotically weakly stationary (AWS) processes, it is shown that the asymptotic MDI measure equals half the Itakura-Saito distortion measure between the asymptotic power spectral densities of the source and prior. Asymptotic MDI modelling of a given AWS source by autoregressive and autoregressive moving average models, which are AWS models, is considered, and conditions are given for convergence of the sample covariance estimator of the source to the stationary covariance used in the modelling.>

Several lattice forms and algorithms which constitute the immittance domain alternatives to the PARCOR lattice algorithm are presented. The immittance variables were shown to offer more efficient Levinson algorithms than the conventional scattering algorithms for both symmetric and Hermitian Toeplitz matrices. This paper presents the lattices associated with the new recursions and provides algorithms to determine their coefficients directly from the signal segments. The new lattices are of interest for speech processing as they offer a different parametrization and process real signal segments with only one multiplier and two adders per section. Complex signal segments require two multipliers and adders per section. Stability conditions for the new parametrizations are also presented.

A new approach to stability of adaptive filters is presented. The notion of constrained-input/constrained-output (CICO) stability is introduced as a generalization of the standard notion of bounded-input/bounded-output (BIBO) stability. This new notion involves a set of constraints on the filter data (i.e., signals and parameters) that, unlike boundedness, are specific to the filter in consideration. The set of all data that satisfy the constraints is the feasibility domain of the adaptive filter. Three particular adaptive lattice filters are analyzed: (i)Burg's lattice, (ii)the unnormalized RLS lattice, and (iii)the normalized RLS lattice. We derive the feasibility domains of these adaptive filters and prove that they are CICO stable.

A recursive-least-squares (RLS) adaptive fast transversal filter (FTF) for processing of continuous-time signals is presented. It has the same structure as the discrete-time least-squares FTF, namely, a tapped-delay-line with time-varying gains, which are updated by propagating a set of coupled recursions. However, while the discrete-time scheme involves a fundamental unit of time (i.e., the sampling period of the signal), which determines both the duration of the delay and the rate of gain updating, our continuous-time scheme involves a delay of arbitrary duration and continuously-varying gains. Also, the conceptual and computational complexity of the continuous-time FTF is reduced in comparison to the to that of the discrete-time FTF. The rate of parameter updating in the continuous-time FTF configuration is essentially independent of the bandwidth and center frequency of the processed signal. Consequently, the gain-update module of the proposed algorithm can be implemented with slow devices (or with digital hardware), whereas the signal-path filter must match the frequency characteristics of the processed signal.

Several computationally extra-efficient versions of the Levinson algorithm are presented. The new versions require half the number of multiplications and the same number of additions as the conventional form of the Levinson algorithm. The saving is achieved by using three- (rather than two) term recursions and propagating them in an Impedance/Admittance domain rather than the conventional scattering domain. Our result apply both to Toeplitz and to close to Toeplitz systems. Moreover they provide a general method for reducing computational requirements in various recursive algorithm, e.g. adaptive least-square lattice algorithms.

A recursive-least-squares (RLS) adaptive lattice algorithm for processing of continuous-time signals is presented. It has the same structure as the discrete-time RLS lattice, namely a cascade of two-input/two-output sections with a single delay-element per section. However, while the discrete-time scheme involves a fundamental unit of time (i.e., the sampling period of the signal), which determines both the duration of the delay and the rate of gain updating, our scheme involves a delay of arbitrary duration and continuously-varying gains. The rate of parameter updating in the continuous-time lattice configuration is essentially independent of the bandwidth and center frequency of the processed signal. Consequently, the gain-update module of the proposed algorithm can be implemented with slow devices (or with digital hardware), whereas the signal-path filter must match the frequency characteristics of the processed signal.

A universal characterization of multi-dimensional maximum-entropy covariances is presented. We show that the maximum-entropy extension of an arbitrary covariance band of a (nonstationary) multi-dimensional signal must have a banded inverse. Furthermore, we show that for one-dimensional signals such banded-inverse covariances are characterized by finite-order autoregressive models. The same kind of model is inadequate for multi-dimensional signals, but it can be used to approximate maximum-entropy covariances.

A recursive biorthogonalization procedure, which forms the basis for the derivation of lattice recursions for the instrumental variable algorithm is presented. We show that the basis for this procedure is an orthogonal decomposition of non-orthogonal (oblique) projections. Furthermore, we show that the orthogonality principle, which underlies the well-known Gram-Schmidt procedure also extends to the above-mentioned recusive biorthogonalization procedure. Applications to the construction of instrumental variable lattice recursions are briefly described.

Autoregressive lattice-filter modeling of two-dimensional fields is developed as an extension of one-dimensional lattice-filter theory. Several distinct methods of extension are presented, including a transfer function approach and a stochastic approach. The resulting lattice configurations span a wide range of structural complexity. They all exhibit the cascade structure of the conventional (one-dimensional) lattice-filter but differ widely in the structure of their elementary sections. It appears that orthogonality of prediction errors, which is essential for robust numerical behavior, requires high structural complexity. A configuration that offers a trade-off between perfect orthogonality and structural complexity is described.

A general theory of constant-parameter modular lattice models for discrete-time nonstationary second-order processes is presented. A complete parametrization of such processes in terms of Schur and congruence coefficients is derived by developing a natural connection between the displacement structure of a covariance matrix and Schur's test for positive-definiteness of matrices. Schur coeffieients provide a simple solution to problems of covariance extension and rational spectral approximation for nonstationary covariances, and they coincide with the well-known reflection (or PARCOR) coefficients when the covariance is stationary. The congruence coefficients provide the time-varying gains of a tapped-delay-line realization of the whitening filter for the process. A constant-parameter realization of the same filter is derived by combining a lattice filter structure with a tapped delay line, both with time-invariant gains. This configuration also provides a recursive relation for the congruence coefficients (namely, a generalized Levinson-Szego recursion). The tapped-delay-line part of the realization can be eliminated by introducing the concept of admissibility. Admissibility also reduces the parametrization of a nonstationary process to Schur coefficients alone, in analogy to stationary processes, which are completely characterized by their PARCOR coefficients.

A unified theory is presented to characterize least-squares adaptive filters, in either lattice or transversal-filter form, for nonstationary processes. The derivations are based upon a geometric formulation of least-squares estimation and on the concept of displacement rank. A few basic geometric relations are shown to underlie the various algorithms. Insights into the fundamental concepts that unify lattice- and transversal-filter approaches to least-squares adaptive filters are also given. The general results are illustrated by applications to the so-called "pre-windowed" and "growing-memory covariance" formulations of the deterministic least-squares problem.

A modular architecture for adaptive multi-channel lattice algorithms is presented. This architecture requires no matrix computations and has a regular structure which significantly simplifies its implementation in comparison with the multichannel (matrix) version of the same algorithms. Because the suggested architecture exhibits a high degree of parallelism and local communication, it is well suited for parallel hardware (VLSI) implementation. The derivation of this modular architecture demonstrates a powerful principle which may become a basic tool for analysis and design of structured processing architectures such as systolic arrays and wavefront array processors.

It is known that a covariance matrix of a stationary discrete-time process can be uniquely characterized by a set of partial correlation coefficients (or matrices, for a vector process) which can be efficiently computed by the Levinson, or better by the Schur algorithm, each requiring O(N2) operations for an N×N covariance matrix. In this paper we point out that the same is true for any covariance matrix, stationary or not, but the corresponding nonstationary Levinson- and Schur-type algorithms require O(N3) operations which is the same amount as required by any direct method of matrix inversion. However, by introducing a classification of processes in terms of their closeness to stationarity we can obtain natural extensions of the stationary algorithms that now require only O(αN2) operations, where α is our measure of closeness to stationarity. As in the stationary case, both algorithms can be implemented by a cascade of time-invariant ladder (or lattice) sections. Some implications for the definition of a power spectral density of α-stationary processes are also noted.