Total-Variation — Fast Gradient Flow and Relations to Koopman Theory

Ido Cohen et al.

The space-discrete Total Variation (TV) flow is analyzed using several mode decomposition techniques. In the one-dimensional case, we provide analytic formulations to Dynamic Mode Decomposition (DMD) and to Koopman Mode Decomposition (KMD) of the TV-flow and compare the obtained modes to TV spectral decomposition. We propose a computationally efficient algorithm to evolve the one-dimensional TV-flow. A significant speedup by three orders of magnitude is obtained, compared to iterative minimizations. A common theme, for both mode analysis and fast algorithm, is the significance of phase transitions during the flow, in which the subgradient changes. We explain why applying DMD directly on TV-flow measurements cannot model the flow or extract modes well. We formulate a more general method for mode decomposition that coincides with the modes of KMD. This method is based on the linear decay profile, typical to TV-flow. These concepts are demonstrated through experiments, where additional extensions to the two-dimensional case are given.

Examining the Limitations of Dynamic Mode Decomposition through Koopman Theory Analysis

Ido Cohen and Guy Gilboa

This work binds the existence of Koopman Eigenfunction (KEF), the geometric of the dynamics, and the validity of DMD to one coherent theory. Viewing the dynamic as a curve in the state-space allows us to formulate an existence condition of KEFs and their multiplicities. These conditions lay the foundations for system reconstruction, global controllability, and observability for nonlinear dynamics.  DMD can be interpreted as a finite dimension approximation of KMD. However, this method is limited to the case when KEFs are linear combinations of the observations. We examine the limitations of DMD through the analysis of Koopman theory. We propose a new mode decomposition technique based on the typical time profile of the dynamics. An overcomplete dictionary of decay profiles is used to sparsely represent the dynamic. This analysis is also valid in the full continuous setting of Koopman theory, which is based on variational calculus.
We demonstrate applications of this analysis, such as finding KEFs and their multiplicities, calculating KMD, dynamics reconstruction, global linearization, and controllability.

Total-Variation Mode Decomposition

Ido Cohen et al. code

In this work we analyze theTotal Variation(TV) flow ap-plied to one dimensional signals. We formulate a relation between Dynamic Mode Decomposition(DMD), a dimensionality reduction method basedon the Koopman operator, and the spectral TV decomposition. DMD isadapted by time rescaling to fit linearly decaying processes, such as theTV flow. For the flow with finite subgradient transitions, a closed formsolution of the rescaled DMD is formulated. In addition, a solution to theTV-flow is presented, which relies only on the initial condition and itscorresponding subgradient. A very fast numerical algorithm is obtainedwhich solves the entire flow by elementary subgradient updates.