Efficient Computation of Bilinear Approximations and Volterra Models of Nonlinear Systems

P.m.s. Burt, José Henrique de Morais Goulart

Abstract

International audience. This paper introduces a suite of highly efficient algorithms for converting physical models of nonlinear systems into bilinear and Volterra models. By exploiting sparsity, non-redundant Taylor expansions, and low-rank decompositions, the authors achieve speedups of over 300x compared to previous methods, making these complex mathematical tools practical for real-time signal processing design.

Introduction

In signal processing, modeling nonlinear behavior—such as the distortion in smartphone speakers or echo in communication systems—is a persistent challenge. Engineers typically rely on two modeling paradigms: Physical Models (PM), which are accurate but difficult to implement in real-time, and Volterra Filters, which are stable and easy to adapt but suffer from the "curse of dimensionality."

The bridge between these two is Carleman Bilinearization (CB). While mathematically elegant, CB has traditionally been a computational nightmare due to the massive matrix operations involved. This paper presents optimized algorithms to make these transformations efficient enough for practical engineering use.

Methodology

The authors propose four main stages of optimization to overcome the computational bottlenecks of traditional Carleman Bilinearization:

  1. Sparsity-Aware Taylor Expansion: Most physical systems involve only a few interacting variables. By using symbolic-to-string conversion and C-coded MEX functions, the algorithms skip the calculation of zero-valued coefficients, preventing the explosion of terms during the initial approximation.
  2. Non-Redundant Carleman Bilinearization: Redundant terms in the state vector (e.g., $x_1x_2$ and $x_2x_1$) are eliminated. A recursive row-wise calculation method is then used to build the bilinear system matrices efficiently.
  3. Recursive Time-Domain Kernel Computation: Contrary to the common frequency-domain approach, the authors compute Volterra kernels directly in the time domain. The recursive structure of bilinear systems makes this approach significantly faster.
  4. Rank-Retaining Decomposition (RRD): By applying Singular Value Decomposition (SVD) to identify the low-rank structure of system matrices, the number of multiplications required to generate kernels is drastically reduced.

Experimental Evaluation

The algorithms were evaluated using two simulated physical setups based on real-world loudspeaker models. Setup A consists of a 4th-order state-space model, while Setup B is a more complex 11-dimensional system involving reconstruction and anti-aliasing filters.

Block diagram of the nonlinear system modeling framework, including D/A and A/D conversion stages.

Key Results

The performance gains are substantial across both bilinear modeling and kernel computation. The proposed routines are more than 30 times faster than previous state-of-the-art implementations for bilinear modeling. For high-order models, the kernel computation methods are more than 300 times faster.

Computational performance comparison for different system orders (P) and setups (A, B).

In the complex "Setup B," a computation that was previously considered impractical was completed in just 27 seconds. Furthermore, the use of non-redundant forms reduced the memory footprint by a factor of 41 for a 5th-order model.

Discussion and Future Work

While these algorithms significantly lower the barrier to using Volterra models, they still require an initial physical model (differential equations) of the system. They do not currently support pure black-box system identification. Additionally, while the computation of kernels is now efficient, the resulting high-order Volterra filters still require many coefficients for real-time execution.

Future research will focus on using these efficient kernels to "prune" models or find optimal initial conditions for simpler block-oriented structures. The authors also suggest extending this work to sensitivity analysis scenarios where thousands of different parameter sets must be evaluated.

Summary updated

Abstract

International audience
BibTeX
@article{burt2017efficient,
  author = {P.M.S. Burt and José Henrique de Morais Goulart},
  title = {{Efficient Computation of Bilinear Approximations and Volterra Models of Nonlinear Systems}},
  journal = {IEEE Transactions on Signal Processing},
  year = {2017},
  doi = {10.1109/tsp.2017.2777391},
}
Figure