On least squares problems with certain Vandermonde-Khatri-Rao structure with applications to DMD

DOI10.1137/19M1288474zbMATH Open1452.65086arXiv1811.12562OpenAlexW3094624870MaRDI QIDQ5132014FDOQ5132014

Authors: Zlatko Drmač, Igor Mezić, Ryan Mohr 

Publication date: 9 November 2020

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

Abstract: This paper proposes a new computational method for solving structured least squares problems that arise in the process of identification of coherent structures in fluid flows. It is deployed in combination with dynamic mode decomposition (DMD) which provides a non-orthogonal set of modes --- corresponding to particular temporal frequencies --- a subset of which is used to represent time snapshots of the underlying dynamics. The coefficients of the representation are determined from a solution of a structured linear least squares problem with the matrix that involves the Khatri--Rao product of a triangular and a Vandermonde matrix. Such a structure allows a very efficient normal equation based least squares solution, which is used in state of the art CFD tools such as the sparsity promoting DMD (DMDSP). A new numerical analysis of the normal equations approach provides insights about its applicability and its limitations. Relevant condition numbers that determine numerical robustness are identified and discussed. Further, the paper offers a corrected semi-normal solution and QR factorization based algorithms. It is shown how to use the Vandermonde--Khatri--Rao structure to efficiently compute the QR factorization of the least squares coefficient matrix, thus providing a new computational tool for the ill-conditioned cases where the normal equations may fail to compute a sufficiently accurate solution. Altogether, the presented material provides a firm numerical linear algebra framework for a class of structured least squares problems arising in a variety of applications.

Full work available at URL: https://arxiv.org/abs/1811.12562

Recommendations

• Dynamic mode decomposition -- a numerical linear algebra perspective
• Complexity reduction of least squares problems involving special Vandermonde matrices
• Accurate solution of structured least squares problems via rank-revealing decompositions
• Tensor-based dynamic mode decomposition
• Randomized Dynamic Mode Decomposition

zbMATH Keywords

Vandermonde matrixKrylov subspace methodproper orthogonal decompositioncoherent structureRayleigh-Ritz approximationscattering coefficientsdynamic mode decomposition (DMD)antenna array processingstructured least squares

Mathematics Subject Classification ID

Factorization of matrices (15A23) Numerical solutions to overdetermined systems, pseudoinverses (65F20) Numerical linear algebra (65F99) Numerical computation of matrix norms, conditioning, scaling (65F35) Numerical problems in dynamical systems (65P99)

Cites Work

• LAPACK Users' Guide
• Dynamic mode decomposition of numerical and experimental data
• Spectral analysis of nonlinear flows
• Variable Projection Methods for an Optimized Dynamic Mode Decomposition
• Handbook series linear algebra. Linear least squares solutions by Householder transformations
• Numerical solution of saddle point problems
• Title not available (Why is that?)
• Numerical methods in matrix computations
• Condition numbers and equilibration of matrices
• Variants of dynamic mode decomposition: boundary condition, Koopman, and Fourier analyses
• On dynamic mode decomposition: theory and applications
• Dynamic mode decomposition with control
• Applications of the dynamic mode decomposition
• A data-driven approximation of the koopman operator: extending dynamic mode decomposition
• Three steps to chaos. II. A Chua's circuit primer
• Title not available (Why is that?)
• A Storage-Efficient $WY$ Representation for Products of Householder Transformations
• Three steps to chaos. I. Evolution
• Projected Krylov Methods for Saddle-Point Systems
• Stability analysis of the method of seminormal equations for linear least squares problems
• On convergence of extended dynamic mode decomposition to the Koopman operator
• Ergodic Theory, Dynamic Mode Decomposition, and Computation of Spectral Properties of the Koopman Operator
• On the Perturbation of the Cholesky Factorization
• Efficient solution of linear matrix equations with application to multistatic antenna array processing
• Data Driven Koopman Spectral Analysis in Vandermonde--Cauchy Form via the DFT: Numerical Method and Theoretical Insights
• An improved criterion to select dominant modes from dynamic mode decomposition
• Data Driven Modal Decompositions: Analysis and Enhancements
• Intermittent large deviation of chaotic trajectory in Ikeda map: Signature of extreme events
• Bifurcations in a quasi-two-dimensional Kolmogorov-like flow
• Efficiency of randomised dynamic mode decomposition for reduced order modelling

Cited In (2)

• Data Driven Koopman Spectral Analysis in Vandermonde--Cauchy Form via the DFT: Numerical Method and Theoretical Insights
• Modern Koopman Theory for Dynamical Systems

Uses Software

• LAPACK

This page was built for publication: On least squares problems with certain Vandermonde-Khatri-Rao structure with applications to DMD

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5132014)