Patrick Héas

Patrick Héas, Cédric Herzet

This work studies the linear approximation of high-dimensional dynamical systems using low-rank dynamic mode decomposition (DMD). Searching this approximation in a data-driven approach is formalised as attempting to solve a low-rank constrained optimisation problem. This problem is non-convex and state-of-the-art algorithms are all sub-optimal. This paper shows that there exists a closed-form solution, which is computed in polynomial time, and characterises the l2-norm of the optimal approximation error. The paper also proposes low-complexity algorithms building reduced models from this optimal solution, based on singular value decomposition or eigen value decomposition. The algorithms are evaluated by numerical simulations using synthetic and physical data benchmarks.

Patrick Héas, Frédéric Cérou, Mathias Rousset

Atmospheric motion vectors (AMVs) extracted from satellite imagery are the only wind observations with good global coverage. They are important features for feeding numerical weather prediction (NWP) models. Several Bayesian models have been proposed to estimate AMVs. Although critical for correct assimilation into NWP models, very few methods provide a thorough characterization of the estimation errors. The difficulty of estimating errors stems from the specificity of the posterior distribution, which is both very high dimensional, and highly ill-conditioned due to a singular likelihood. Motivated by this difficult inverse problem, this work studies the evaluation of the (expected) estimation errors using gradient-based Markov Chain Monte Carlo (MCMC) algorithms. The main contribution is to propose a general strategy, called here chilling, which amounts to sampling a local approximation of the posterior distribution in the neighborhood of a point estimate. From a theoretical point of view, we show that under regularity assumptions, the family of chilled posterior distributions converges in distribution as temperature decreases to an optimal Gaussian approximation at a point estimate given by the Maximum A Posteriori, also known as the Laplace approximation. Chilled sampling therefore provides access to this approximation generally out of reach in such high-dimensional nonlinear contexts. From an empirical perspective, we evaluate the proposed approach based on some quantitative Bayesian criteria. Our numerical simulations are performed on synthetic and real meteorological data. They reveal that not only the proposed chilling exhibits a significant gain in terms of accuracy of the point estimates and of their associated expected errors, but also a substantial acceleration in the convergence speed of the MCMC algorithms.

P. Héas, O. Hautecoeur, R. Borde

In this work, we present an efficient optic flow algorithm for the extraction of vertically resolved 3D atmospheric motion vector (AMV) fields from incomplete hyperspectral image data measures by infrared sounders. The model at the heart of the energy to be minimized is consistent with atmospheric dynamics, incorporating ingredients of thermodynamics, hydrostatic equilibrium and statistical turbulence. Modern optimization techniques are deployed to design a low-complexity solver for the energy minimization problem, which is non-convex, non-differentiable, high-dimensional and subject to physical constraints. In particular, taking advantage of the alternate direction of multipliers methods (ADMM), we show how to split the original high-dimensional problem into a recursion involving a set of standard and tractable optic-flow sub-problems. By comparing with the ground truth provided by the operational numerical simulation of the European Centre for Medium-Range Weather Forecasts (ECMWF), we show that the performance of the proposed method is superior to state-of-the-art optical flow algorithms in the context of real infrared atmospheric sounding interferometer (IASI) observations.

C. Herzet, M. Diallo, P. Héas

We consider an enhanced version of the well-kwown "Petrov-Galerkin" projection in Hilbert spaces. The proposed procedure, dubbed "multi-slice" projector, exploits the fact that the sought solution belongs to the intersection of several high-dimensional slices. This setup is for example of interest in model-order reduction where this type of prior may be computed off-line. In this note, we provide a mathematical characterization of the performance achievable by the multi-slice projector and compare the latter with the results holding in the Petrov-Galerkin setup. In particular, we illustrate the superiority of the multi-slice approach in certain situations.

Patrick Heas, Cedric Herzet

This technical note reviews sate-of-the-art algorithms for linear approximation of high-dimensional dynamical systems using low-rank dynamic mode decomposition (DMD). While repeating several parts of our article "low-rank dynamic mode decomposition: an exact and tractable solution", this work provides additional details useful for building a comprehensive picture of state-of-the-art methods.

Patrick Heas, Cedric Herzet, Benoit Combes

Reduced modeling in high-dimensional reproducing kernel Hilbert spaces offers the opportunity to approximate efficiently non-linear dynamics. In this work, we devise an algorithm based on low rank constraint optimization and kernel-based computation that generalizes a recent approach called "kernel-based dynamic mode decomposition". This new algorithm is characterized by a gain in approximation accuracy, as evidenced by numerical simulations, and in computational complexity.

Patrick Heas, Cedric Herzet

This work provides closed-form solutions and minimum achievable errors for a large class of low-rank approximation problems in Hilbert spaces. The proposed theorem generalizes to the case of bounded linear operators the previous results obtained in the finite dimensional case for the Frobenius norm. The theorem provides the basis for the design of tractable algorithms for kernel or continuous DMD.

Patrick Héas, Cédric Herzet, Benoit Combès

Reduced modeling of a computationally demanding dynamical system aims at approximating its trajectories, while optimizing the trade-off between accuracy and computational complexity. In this work, we propose to achieve such an approximation by first embedding the trajectories in a reproducing kernel Hilbert space (RKHS), which exhibits appealing approximation and computational capabilities, and then solving the associated reduced model problem. More specifically, we propose a new efficient algorithm for data-driven reduced modeling of non-linear dynamics based on linear approximations in a RKHS. This algorithm takes advantage of the closed-form solution of a low-rank constraint optimization problem while exploiting advantageously kernel-based computations. Reduced modeling with this algorithm reveals a gain in approximation accuracy, as shown by numerical simulations, and in complexity with respect to existing approaches.

C. Herzet, P. Héas, A. Drémeau

This paper deals with model-order reduction of parametric partial differential equations (PPDE). More specifically, we consider the problem of finding a good approximation subspace of the solution manifold of the PPDE when only partial information on the latter is available. We assume that two sources of information are available: i) a "rough" prior knowledge, taking the form of a manifold containing the target solution manifold, ii) partial linear measurements of the solutions of the PPDE (the term partial refers to the fact that observation operator cannot be inverted). We provide and study several tools to derive good approximation subspaces from these two sources of information. We first identify the best worst-case performance achievable in this setup and propose simple procedures to approximate the corresponding optimal approximation subspace. We then provide, in a simplified setup, a theoretical analysis relating the achievable reduction performance to the choice of the observation operator and the prior knowledge available on the solution manifold.

Patrick Héas, Cédric Herzet

This work studies the linear approximation of high-dimensional dynamical systems using low-rank dynamic mode decomposition (DMD). Searching this approximation in a data-driven approach is formalised as attempting to solve a low-rank constrained optimisation problem. This problem is non-convex and state-of-the-art algorithms are all sub-optimal. This paper shows that there exists a closed-form solution, which is computed in polynomial time, and characterises the l2-norm of the optimal approximation error. The paper also proposes low-complexity algorithms building reduced models from this optimal solution, based on singular value decomposition or eigen value decomposition. The algorithms are evaluated by numerical simulations using synthetic and physical data benchmarks.

Patrick Héas, Angélique Drémeau, Cédric Herzet

In this work, we propose a novel procedure for video super-resolution, that is the recovery of a sequence of high-resolution images from its low-resolution counterpart. Our approach is based on a "sequential" model (i.e., each high-resolution frame is supposed to be a displaced version of the preceding one) and considers the use of sparsity-enforcing priors. Both the recovery of the high-resolution images and the motion fields relating them is tackled. This leads to a large-dimensional, non-convex and non-smooth problem. We propose an algorithmic framework to address the latter. Our approach relies on fast gradient evaluation methods and modern optimization techniques for non-differentiable/non-convex problems. Unlike some other previous works, we show that there exists a provably-convergent method with a complexity linear in the problem dimensions. We assess the proposed optimization method on {several video benchmarks and emphasize its good performance with respect to the state of the art.}