A fast algorithm for general Volterra filtering

Volterra filters are a classical instrument for nonlinear channels and systems modeling, noise and echo cancellation, signal estimation and detection, and various other applications. As is well known, the computational weight of Volterra filters exponentially grows with the nonlinearity degree. This work presents a contribution to the efficient computation of Volterra filters with generic order nonlinearity found in many telecommunication applications. Our technique rests on the interpretation of the Mth-order one-dimensional Volterra filters in terms of M-dimensional linear convolution, and it adopts a multidimensional fast convolution scheme. This makes the method applicable to any M. Interestingly enough, fast convolution based on the standard multidimensional fast Fourier transform (MD FFT) in the case of Volterra filters is outperformed by direct computation. Our method is efficient due to the use of a special MD FFT which can exploit the symmetries of the signals entering the computation of Volterra filters and which makes it superior to direct computation. The points of interests of the results presented are both the generality and the fact that they show that the well-known nonlinearity/multidimensionality tradeoff of Volterra filters can have computational implications.     

Tensor product basis approximations for Volterra filters

The paper studies approximations for a class of nonlinear filters known as Volterra filters. Although the Volterra filter provides a relatively simple and general representation for nonlinear filtering, it is often highly overparameterized. Due to the large number of parameters, the utility of the Volterra filter is limited. The overparameterization problem is addressed in the paper using a tensor product basis approximation (TPBA). In many cases, a Volterra filter may be well approximated using the TPBA with far fewer parameters. Hence, the TPBA offers considerable advantages over the original Volterra filter in terms of both implementation and estimation complexity. Furthermore, the TPBA provides useful insight into the filter response. The paper studies the crucial issue of choosing the approximation basis. Several methods for designing an appropriate approximation basis and error bounds on the resulting mean-square output approximation error are derived. Certain methods are known to be nearly optimal     

Baseband Volterra filters for implementing carrier basednonlinearities

A diagonal coordinate representation for Volterra filters is developed and exploited to derive efficient Volterra filter implementations for processing carrier based input signals. In the diagonal coordinate representation, the output is expressed as a sum of linear filters applied to modified input signals. Hence, linear filtering methods are employed to implement the nonlinear filter on a baseband version of the input. Downsampling is then used to reduce computational complexity. The same approach is employed to develop efficient implementations for processing continuous-time carrier-based signals, pulse amplitude-modulated signals, and frequency division multiplexed input signals     

Adaptive parallel-cascade truncated Volterra filters

This paper studies adaptive truncated Volterra filters employing parallel-cascade structures. Parallel-cascade realizations implement higher order Volterra systems as a parallel connection of multiplicative combinations of lower order truncated Volterra systems. A normalized LMS adaptive filter is developed, and its performance capabilities are evaluated using a series of simulation experiments. The experimental results indicate that the normalized LMS adaptive parallel-cascade Volterra filter has superior convergence properties over several competing structures. This paper also includes an experiment that demonstrates the capability of the parallel-cascade adaptive system to reduce its implementation complexity by using fewer than the maximum number of branches required for the most general realization of the system     

A new family of concurrent algorithms for adaptive Volterra andlinear filters

A novel idea for introducing concurrency in least squares (LS) adaptive algorithms by sacrificing optimality has been proposed. The resultant class of algorithms provides schemes to fill the wide gap in the convergence rates of LS and stochastic gradient (SG) algorithms. It will be particularly useful in the real time implementations of large-order linear and Volterra filters for which both the LS and SG algorithms are unsuited     

Geometrical properties of optimal Volterra filters for signaldetection

Linear-quadratic filters are a special example of Volterra filters that are limited to the second order. It is shown that all the results recently published which are valid in the linear-quadratic case can be extended with the appropriate notations to Volterra filters of arbitrary order. Particularly, the optimum Volterra filter giving the maximum of the deflection for detecting a signal in noise is wholly calculated. In addition, several geometrical properties of optimal Volterra filters are investigated by introducing appropriate scalar products. In particular, the concept of space orthogonal to the signal and the noise alone reference (NAR) property are introduced, allowing a decomposition of the optimal filter that exhibits a relation between detection and estimation. Extensions to the infinite case and relations with the likelihood ratio are also investigated     

Adaptive Volterra filters for active control of nonlinear noiseprocesses

This paper presents a Volterra filtered-X least mean square (LMS) algorithm for feedforward active noise control. The research has demonstrated that linear active noise control (ANC) systems can be successfully applied to reduce the broadband noise and narrowband noise, specifically, such linear ANC systems are very efficient in reduction of low-frequency noise. However, in some situations, the noise that comes from a dynamic system may he a nonlinear and deterministic noise process rather than a stochastic, white, or tonal noise process, and the primary noise at the canceling point may exhibit nonlinear distortion. Furthermore, the secondary path estimate in the ANC system, which denotes the transfer function between the secondary source (secondary speaker) and the error microphone, may have nonminimum phase, and hence, the causality constraint is violated. If such situations exist, the linear ANC system will suffer performance degradation. An implementation of a Volterra filtered-X LMS (VFXLMS) algorithm based on a multichannel structure is described for feedforward active noise control. Numerical simulation results show that the developed algorithm achieves performance improvement over the standard filtered-X LMS algorithm for the following two situations: (1) the reference noise is a nonlinear noise process, and at the same time, the secondary path estimate is of nonminimum phase; (2) the primary path exhibits the nonlinear behavior. In addition, the developed VFXLMS algorithm can also be employed as an alternative in the case where the standard filtered-X LMS algorithm does not perform well     

A general framework for low level vision

We introduce a new geometrical framework based on which natural flows for image scale space and enhancement are presented. We consider intensity images as surfaces in the (x,I) space. The image is, thereby, a two-dimensional (2-D) surface in three-dimensional (3-D) space for gray-level images, and 2-D surfaces in five dimensions for color images. The new formulation unifies many classical schemes and algorithms via a simple scaling of the intensity contrast, and results in new and efficient schemes. Extensions to multidimensional signals become natural and lead to powerful denoising and scale space algorithms.     

A general framework for nonlinear multigrid inversion.

A variety of new imaging modalities, such as optical diffusion tomography, require the inversion of a forward problem that is modeled by the solution to a three-dimensional partial differential equation. For these applications, image reconstruction is particularly difficult because the forward problem is both nonlinear and computationally expensive to evaluate. In this paper, we propose a general framework for nonlinear multigrid inversion that is applicable to a wide variety of inverse problems. The multigrid inversion algorithm results from the application of recursive multigrid techniques to the solution of optimization problems arising from inverse problems. The method works by dynamically adjusting the cost functionals at different scales so that they are consistent with, and ultimately reduce, the finest scale cost functional. In this way, the multigrid inversion algorithm efficiently computes the solution to the desired fine-scale inversion problem. Importantly, the new algorithm can greatly reduce computation because both the forward and inverse problems are more coarsely discretized at lower resolutions. An application of our method to Bayesian optical diffusion tomography with a generalized Gaussian Markov random-field image prior model shows the potential for very large computational savings. Numerical data also indicates robust convergence with a range of initialization conditions for this nonconvex optimization problem.     

A general framework for frequency domain multi-channel signalprocessing

The authors provide a general framework for performing processing of stationary multichannel (MC) signals that is linear shift-invariant within channel and shift varying across channels. Emphasis is given to the restoration of degraded signals. It is shown that, by utilizing the special structure of semiblock circulant and block diagonal matrices, MC signal processing can be easily carried out in the frequency domain. The generalization of many frequency-domain single-channel (SC) signal processing techniques to the MC case is presented. It is shown that in MC signal processing each frequency component of a signal and system is presented, respectively, by a small vector and a matrix (of size equal to the number of channels), while in SC signal processing each frequency component in both cases is a scalar.     

A general framework for developing adaptive fault-tolerant routingalgorithms

It is shown that Cartesian product (CP) graph-based network methods provide a useful framework for the design of reliable parallel computer systems. Given component networks with prespecified connectivity, more complex networks with known connectivity and terminal reliability can be developed. CP networks provide systematic techniques for developing reliable fault-tolerant routing schemes, even for very complex topological structures. The authors establish the theoretical foundations that relate the connectivity of a CP network, the connectivity of the component networks, and the number of faulty components: present an adaptive generic algorithm that can perform successful point-to-point routing in the presence of faults: synthesize, using the theoretical results, this adaptive fault-tolerant algorithm from algorithms written for the component networks: prove the correctness of the algorithm: and show that the algorithm ensures following an optimal path, in the presence of many faults, with high probability     

Partially decoupled Volterra filters: formulation and LMSadaptation

The adaptation of Volterra filters by one particular method-the method of least mean squares (LMS)-while easily implemented, is complicated by the fact that upper hounds for the values of step sizes employed by a parallel update LMS scheme are difficult to obtain. In this paper, we propose a modification of the Volterra filter in which the filter weights of a given order are optimized independently of those weights of higher order. Using this approach, we then solve the minimum mean square error (MMSE) filtering problem as a series of constrained optimization problems, which produce a partially decoupled normal equation for the Volterra filter. From this normal equation, we are able to develop an adaptation routine that uses the principles of partial decoupling that is similar in form to the Volterra LMS algorithm but with important structural differences that allow a straightforward derivation of bounds on the algorithm's step sizes; these bounds can be shown to depend on the respective diagonal blocks of the Volterra autocorrelation matrix. This produces a reliable set of design guidelines that allow more rapid convergence of the lower order weight sets     

Efficient VLSI array processing structures for adaptive quadratic digital filters

In this paper we introduce a class of efficient architectures for adaptive quadratic digital filters. These architectures are based on the LMS algorithm and use the rank compressed lower-upper (LU) triangular deomposition method. These architectures exhibit high parallelism as well as great modularity and regularity. We also consider affiliated VLSI array processing structures and compare these in terms of hardware cost and data throughput delay. For comparison purposes, the distributed arithmetic structures of adaptive quadratic filters are also included in the paper. Finally, the convergence performance of the adaptive quadratic filters is tested via benchmark simulation examples.This work was supported by National Science Foundation Grant ECS-8601307.     

Semisystolic implementation of second-order Volterra digital filters based on recurrence algorithm of Volterra filtering

The letter presents a quasitriangular semisystolic array for the implementation of nonlinear second-order volterra digital filters. The performance of the proposed systolic array is based on the recurrence algorithm of Volterra filtering, which is also derived here.<>     

Bi-impulse response design of isotropic quadratic filters

The bi-impulse response of a 1-D or 2-D quadratic Volterra filter is introduced as a mathematical tool able to completely describe the nonlinear operator. The conditions that must be satisfied in order to obtain isotropic input/output relations are studied. The result is a formal framework that allows simple but effective operators (particularly for image enhancement and preprocessing) to be designed and a deeper insight into the properties of Volterra filters to be acquired. Examples of design and of the performance obtained by processing natural and synthetic images are presented     

A multichannel hierarchical approach to adaptive Volterra filters employing filtered-X affine projection algorithms

It is shown in this paper how the use of a recently introduced algebra, called V-vector algebra, can directly lead to the implementation of Volterra filters of any order P in the form of a multichannel filterbank. Each channel in this approach is modeled as a finite impulse response (FIR) filter, and the channels are hierarchically arranged according to the number of the filter coefficients. In such a way, it is also possible to devise models of reduced complexity by cutting the less relevant channels. This model is then used to derive efficient adaptation algorithms in the context of nonlinear active noise control. In particular, it is shown how the affine projection (AP) algorithms used in the linear case can be extended to a Volterra filter of any order P. The derivation of the so-called Filtered-X AP algorithms for nonlinear active noise controllers is easily obtained using the elements of the V-vector algebra. These algorithms can efficiently replace the standard LMS and NLMS algorithms usually applied in this field, especially when, in practical applications, a reduced-complexity multichannel structure can be exploited.     

A general framework for vertex orderings with applications tocircuit clustering

Vertex orderings have been successfully applied to problems in netlist clustering and for system partitioning and layout. We present a vertex ordering construction that encompasses most reasonable graph traversals. Two parameters-an attraction function and a window-provide the means for achieving various graph traversals and addressing particular clustering requirements. We then use dynamic programming to optimality split the vertex ordering into a multiway clustering. Our approach outperforms several clustering methods in the literature in terms of three distinct clustering objectives. The ordering construction, by itself, also outperforms existing graph ordering constructions for this application. Tuning our approach to “meta-objectives”, particularly clustering for two-phase Fiduccia-Mattheyses bipartitioning, remains an open area of research     

A general framework for developing and evaluating band-limitedfunction extrapolation methods

It is shown that the bandlimited function extrapolation can be considered as an approximation problem in operator space. Within this framework, the Papoulis-Gerchberg method and two other methods for extrapolation are analyzed. Particular attention is given to approximation using Taylor and Chebyschev series, and to approximation using the Lagrange interpolation method     

Penalized least squares estimation of Volterra filters and higherorder statistics

Volterra filters (VFs) and higher order statistics (HOS) are important tools for nonlinear analysis, processing, and modeling. Despite their highly desirable properties, the transfer of VFs and HOS to real-world signal processing problems has been hindered by the requirement of very large data records needed to obtain reliable estimates. The identification of VFs and the estimation of HOS both fall into the category of ill-posed estimation problems. We develop penalized least squares (PLS) estimation methods for VFs and HOS. It is shown that PLS is a very effective way to incorporate prior information of the problem at hand without directly constraining the estimation procedure. Hence, PLS produces much more reliable estimates. The main contributions of this paper are the development of appropriate penalizing functionals and cross-validation procedures for PLS based VF identification and HOS estimation