CHOPtrey: contextual online polynomial extrapolation for enhanced multi-core co-simulation of complex systems

XKCD. My hobby: extrapolating

CHOPtrey. A long, extrapolated and progressive scientific story. Ace, deuce, trey... ready?

It all started with Cyril Faure, then a PhD student  with Nicolas Pernet in real-time computing. He used to stop by my office. We had coffee, discussed books (from Descartes to Sci-Fi) and music (mostly Loudblast, Slayer, Pink Floyd, Manowar, Bolt Thrower). We exchanged ideas and concerns. One day, he told me about a worry in his thesis. Caveat: I am very bad at computer science, advanced programming, and had little hints about partitioned/slacked real-time co-simulation systems.

So this was not about programming, but simulation and co-simulation. Big physical systems (engines, aircrafts, boats) are complicated to simulate. Protocols and methods include FMI standard (Functional Mockup Interface) and FMU (Functional Mockup Unit). Partitioning them into subsystems may help the simulation, but split discrete subsystems should communicate. Fast enough to be precise, slow enough for speed-ups.

Hoher, 2011, A contribution to the real-time simulation...

So when simulated subsystems communicate at regular communication times, and one want interpolated data at a fractional time interval, one generally uses the last known value. This is called zeroth-order hold (ZOH). 

So I wondered: "this sound a little bit like aliasing, in a causal setting, let's interpolate, say, with a line or a parabola". No so easy. In this cosimulation domain, interpolation is "known" to be unstable. Even with FOH (first-order hold) or SOH (second-order hold).

A few implementations (Matlab prototypes, C++ and a final embedding in the XMOD software) and some tuning later, we produced a hierarchical scheme (with Abir, Cyril, Daniel and Mongi), based on morphological contexts, like in lossless image compression (PNG for instance). It proved very cheap, quite robust, and apparently stable. We called it CHOPtrey, from the old French words "ace, deuce, trey" (1, 2, 3 referring to sides of dice). In reference to a chop tray (or cutting board). Because it allows to chop (or cut) a big simulated system into several smaller ones. Because it is composed of three parts or chops:

• CHOPred: a Computationally Hasty Online Prediction system (improving the trade-off between integration speed-ups, needing large communication steps, and simulation precision)
• CHOPoly: Causal Hopping Oblivious Polynomials, with smoothed adaptive forward prediction improves co-simulation accuracy. They are similar to Savitzky-Golay filters or LOESS or LOWESS regression methods)
• CHOPatt: a Contextual & Hierarchical Ontology of Patterns, where data behavior is segmented  into different classes to handle the discontinuities of the exchanged signals

During this work, I learned a lot about co-simulation, parallel computing, multi-core, etc. But also a lot about least-squares parabolic regression, which I thought I knew for decades. I did not. Not the deepest theory ever, but one of my nicest experience of cross-domain collaboration (along with bioinformatics and our BRANE work on gene regulatory networks), some genuine computer engineering, with a final packaged product (implemented in xMod). Here it is:

CHOPtrey: contextual online polynomial extrapolation for enhanced multi-core co-simulation of complex systems 

Abstract : The growing complexity of Cyber-Physical Systems (CPS), together with increasingly available parallelism provided by multi-core chips, fosters the parallelization of simulation. Simulation speed-ups are expected from co-simulation and parallelization based on model splitting into weak-coupled sub-models, as for instance in the framework of Functional Mockup Interface (FMI). However, slackened synchronization between sub-models and their associated solvers running in parallel introduces integration errors, which must be kept inside acceptable bounds. CHOPtrey denotes a forecasting framework enhancing the performance of complex system co-simulation, with a trivalent articulation. First, we consider the framework of a Computationally Hasty Online Prediction system (CHOPred). It allows to improve the trade-off between integration speed-ups, needing large communication steps, and simulation precision, needing frequent updates for model inputs. Second, smoothed adaptive forward prediction improves co-simulation accuracy. It is obtained by past-weighted extrapolation based on Causal Hopping Oblivious Polynomials (CHOPoly). And third, signal behavior is segmented to handle the discontinuities of the exchanged signals: the segmentation is performed in a Contextual & Hierarchical Ontology of Patterns (CHOPatt). Implementation strategies and simulation results demonstrate the framework ability to adaptively relax data communication constraints beyond synchronization points which sensibly accelerate simulation. The CHOPtrey framework extends the range of applications of standard Lagrange-type methods, often deemed unstable. The embedding of predictions in lag-dependent smoothing and discontinuity handling demonstrates its practical efficiency.

Keywords: parallel simulation; Functional Mockup Interface (FMI); smoothed online prediction; causal polynomial extrapolation; context-based decision; internal combustion engine

Links:

• published: CHOPtrey (January 2017): SIMULATION: Transactions of The Society for Modeling and Simulation International
• arxiv: CHOPtrey: contextual online polynomial extrapolation for enhanced multi-core co-simulation of complex systems
• HAL: CHOPtrey: contextual online polynomial extrapolation for enhanced multi-core co-simulation of complex systems
• A novel CHOPtrey companion page
• Pêcheurs de perles, une parabole
• Ace, Deuce, Trey: The virtual linguist

The full set of numbers for the six sides of a die are ace, deuce, trey, cater, cinque, sice. They are from Old French (cf un, deux, trois, quatre, cinq, six of modern French). Ace is originally from the Latin for 'unit'.

Seismic Signal Processing (ICASSP 2014)

There was a special session on "Seismic Signal Processing" at International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2014, Florence. Our talk was on simplified optimization techniques to solve multiple reflections via adaptive filtering techniques in wavelet frame domains.

A constrained-based optimization approach for seismic data recovery problems

 Mai Quyen Pham, Caroline Chaux, Laurent Duval, Jean-Christophe Pesquet

Special session on "SS5 - Seismic Signal Processing", International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2014, Florence, Italy [journal paper+blog+arxiv+paper+slides] 

Random and structured noise both affect seismic data, hiding the reflections of interest (primaries) that carry meaningful geophysical interpretation. When the structured noise is composed of multiple reflections, its adaptive cancellation is obtained through time-varying filtering, compensating inaccuracies in given approximate templates. The under-determined problem can then be formulated as a convex optimization one, providing estimates of both filters and primaries. Within this framework, the criterion to be minimized mainly consists of two parts: a data fidelity term and hard constraints modelling a priori information. This formulation may avoid, or at least facilitate, some parameter determination tasks, usually difficult to perform in inverse problems. Not only classical constraints, such as sparsity, are considered here, but also constraints expressed through hyperplanes, onto which the projection is easy to compute. The latter constraints lead to improved performance by further constraining the space of geophysically sound solutions.

This paper  has focused on the constrained convex formulation of adaptive multiple removal. The proposed approach, based on proximal methods, is quite flexible and allows us to integrate a large panel of hard constraints corresponding to a priori knowledge on the data to be estimated (i.e. primary signal and time-varying filters). A key observation is that some of the related constraint sets can be expressed through hyperplanes, which are not only more convenient to design, but also easier to implement through straightforward projections. Since sparsifying transforms and  constraints strongly interact [Pham-2014-TSP], we now  study the class of hyperplane constraints of interest as well as their inner parameters, together with the extension to higher dimensions

Sparse template-based adaptive filtering

Significance index related to Student's t-test

The phenomenon arises in several real-life signal processing contexts: acoustic echo-cancellation (AEC) in sound and speech,  non-destructive testing where transmitted waves may rebound at material interfaces (e.g. ultrasounds), or pattern matching in images. Here in seismic reflection or seismology. Weak signals (of interest) are buried under both strong random and structured noise. Provided appropriate templates are obtained, we propose a structured-pattern filtering algorithm (called Ricochet) through constrained adaptive filtering in a  transformed domain. Its generic methodology impose sparsity: in different wavelet frames (Haar, Daubechies, Symmlets) coefficients, using the L-1 or Manhattan norm, as well as on adaptive filter coefficients using concentration measures (for sparser filters in the time domain): L-1, the Frobenius norm squared, and the mixed L-1,2 norms). Regularity properties are constrained as well, for instance slow variation on the adaptive filter coefficients (uniform, Chebychev or L-infinity norm). Quantitative results are given with a significance index, reminiscent of the Student t-test.

A Primal-Dual Proximal Algorithm for Sparse Template-Based Adaptive Filtering: Application to Seismic Multiple Removal [doi+hal+arxiv]

Abstract: Unveiling meaningful geophysical information from seismic data requires to deal with both random and structured ``noises''. As their amplitude may be greater than signals of interest

Lost in multiples: a creeping primary (flat, bootom-right)

(primaries), additional prior information is especially important in performing efficient signal separation. We address here the problem of multiple reflections, caused by  wave-field bouncing between layers. Since only approximate models of these phenomena are available, we propose a flexible framework for time-varying adaptive filtering of seismic signals, using sparse representations,  based on inaccurate templates. We recast the joint estimation of adaptive filters and primaries in a new convex variational formulation. This approach allows us to incorporate plausible knowledge about noise statistics, data sparsity and slow filter variation in parsimony-promoting wavelet frames.  The designed primal-dual algorithm solves a  constrained  minimization problem that alleviates standard regularization issues in finding hyper-parameters. The approach demonstrates  significantly good performance in low signal-to-noise ratio conditions, both for simulated and real field seismic data.

All the metrics here are convex. Wait a bit for something completely different with non-convex penalties, namely smoothed versions of the ratio of the L1 norm over the L2 norm: Euclid in a Taxicab: Sparse Blind Deconvolution with Smoothed $\ell_1/ell_2$ Regularization, covered in Nuit Blanche, and with arxiv page and pdf.

ICASSP 2014: Seismic processing special session

Galileo inclined Planes and Curves for motion study

First good news: our seismic data processing paper has been accepted to ICASSP 2014 (a just below 50% acceptance rate: 1745 out of 3492). Second good news: it is in Florence, a magnificent city, not only for arts (the conference is called "The Art of Signal Processing), but for Science too. The Galileo (1564-1642) History of Science Museum is a must-see. At our epoch, we can afford running time consuming dumb computations, changing only one hyper-parameter at the time to solve inverse restoration problems. We benefit from neat integro-differential settings to solve convex optimization problems. It is difficult to imagine a time when people endeavored the making of Science as we know it today, with very imprecise time measurements: imagine you want to compare the duration of free-fall for two objects (a 1 kg feather ball and a 1kg feather ball, for instance, with a water clock, or clepsydra. The calculus of variation blossomed between Leibniz and Newton between 1666 and 1674. Yet, people where able to "prove" important properties of motions, such as the tautochronism of the cycloid (the motion of a point on a rolling circle). Take a wooden gutter in shape of a cycloid, drop two balls from different heights along the wooden frame, they would arrive at the same time. The video is available here, at the Galileo virtual Museum. This "tautochrone" phenomenon  (meaning "same time" in Greek) was discovered by Christiaan Huyghens around the 1650's. It was instrumental in the development of "more perfect pendulum motions", at the core of modern pendulum clocks, that allowed increased precision in Science, as well as farther and less hazardous boat trips around the world. The clock making industry is related to the longitude problem.

The special session: Seismic Signal Processing is organized by Leonardo Duarte, Daniela Donno, Renato R Lopes and João Romano.

A fundamental problem in geophysics is to estimate the properties of the Earth’s subsurface based on measurements acquired by sensors located over the area to be analyzed. Among the different methods to accomplish this task, seismic reflection is the most widespread and has been intensively applied for hydrocarbon exploration. The characterization of the subsoil using seismic reflection techniques is conducted by recording the wave field that is originated from the interaction between the environment under analysis and a seismic wave generated by controlled active sources (e.g. a dynamite explosion in land acquisition). Signal processing (SP) plays a fundamental role in seismic reflection. Indeed, in order to extract relevant information from seismic data, one has to perform tasks such as filtering, deconvolution, and signal separation. Originally, there was a close interaction between the signal processing and geophysics communities – for instance, important achievements in deconvolution and the wavelet transform were obtained in the context of seismic data. Nowadays, however, this interaction has been partially lost – as a consequence, geophysicists are not aware of the most recent SP methods, and, on other hand, the SP community is drawing weak attention to this interesting application. Given this panorama, the main goals of this special session are to shed some light on the research in seismic signal processing, and to broaden and reinforce collaboration between the signal processing and the geophysics research communities. With this goal in mind, the session comprises works on important theoretical and practical topics that arise in seismic signal processing.

The accepted presentation is: A constrained-based optimization approach for seismic data recovery problems

Abstract: Random and structured noise both affect seismic data, hiding the reflections of interest (primaries) that carry meaningful geophysical interpretation. When the structured noise is composed of multiple reflections, its adaptive cancellation is obtained through time-varying filtering, compensating inaccuracies in given approximate templates. The under-determined problem can then be formulated as a convex optimization one, providing estimates of both filters and primaries.Within this framework, the criterion to be minimized mainly consists of two parts: a data fidelity term and hard constraints modeling a priori information. This formulation may avoid, or at least facilitate, some parameter determination tasks, usually difficult to perform in inverse problems. Not only classical constraints, such as sparsity, are considered here,  but also constraints  expressed through hyperplanes, onto which the projection is easy to compute. The latter constraints lead to improved performance by further constraining the space of geophysically sound solutions.

This conference presentation is strongly related to the journal paper: A Primal-Dual Proximal Algorithm for Sparse Template-Based Adaptive Filtering: Application to Seismic Multiple Removal [page|pdf|blog|arxiv], accepted in 2014 at IEEE Transactions on Signal Processing.