Signal and Image Processing
Latent Modes of Nonlinear Flows: A Koopman Theory Analysis
I Cohen, G Gilboa
Elements in Non-local Data Interactions: Foundations and Applications, Mathematics, Computational Science, Cambridge University Press
Extracting the latent underlying structures of complex nonlinear local and nonlocal flows is essential for their analysis and modeling. In this Element the authors attempt to provide a consistent framework through Koopman theory and its related popular discrete approximation-dynamic mode decomposition (DMD). They investigate the conditions to perform appropriate linearization, dimensionality reduction and representation of flows in a highly general setting. The essential elements of this framework are Koopman eigenfunctions (KEFs) for which existence conditions are formulated. This is done by viewing the dynamic as a curve in state-space. These conditions lay the foundations for system reconstruction, global controllability, and observability for nonlinear dynamics. They examine the limitations of DMD through the analysis of Koopman theory and propose a new mode…
presentation | video | arXiv | code
Total-Variation Mode Decomposition
I Cohen, T Berkov, G Gilboa
Scale Space and Variational Methods in Computer Vision
In this work we analyze the Total Variation (TV) flow applied to one dimensional signals. We formulate a relation between Dynamic Mode Decomposition (DMD), a dimensionality reduction method based on the Koopman operator, and the spectral TV decomposition. DMD is adapted by time rescaling to fit linearly decaying processes, such as the TV flow. For the flow with finite subgradient transitions, a closed form solution of the rescaled DMD is formulated. In addition, a solution to the TV-flow is presented, which relies only on the initial condition and its corresponding subgradient. A very fast numerical algorithm is obtained which solves the entire flow by elementary subgradient updates.
presentation | video | arXiv | code
Modes of Homogeneous Gradient Flows
I Cohen, O Azencot, P Lifshits, G Gilboa
SIAM Journal on Imaging Sciences
Finding latent structures in data is drawing increasing attention in diverse fields such as image and signal processing, fluid dynamics, and machine learning. In this work we examine the problem of finding the main modes of gradient flows. Gradient descent is a fundamental process in optimization where its stochastic version is prominent in training of neural networks. Here our aim is to establish a consistent theory for gradient flows ψ_t=P(ψ), where P is a nonlinear homogeneous operator. Our proposed framework stems from analytic solutions of homogeneous flows, previously formalized by Cohen and Gilboa, where the initial condition ψ_0 admits the nonlinear eigenvalue problem P(ψ_0)=λψ_0. We first present an analytic solution for dynamic mode decomposition (DMD) in such cases. We show an inherent flaw of DMD, which is unable to recover the essential dynamics of the flow. It is evident that DMD is best suited for homogeneous flows of degree one. We propose an adaptive time sampling scheme and show its dynamics are analogue to homogeneous flows of degree one with a fixed step size. Moreover, we adapt DMD to yield a real spectrum, using symmetric matrices. Our analytic solution of the proposed scheme recovers the dynamics perfectly and yields zero error. We then proceed to show the relation between the orthogonal modes {φ_i} and their decay profiles under the gradient flow. We formulate orthogonal nonlinear spectral decomposition (OrthoNS), which recovers the essential latent structures of the gradient descent process. Definitions for spectrum and filtering are given, and a Parseval-type identity is shown. Experimental results on images show the resemblance to direct computations of nonlinear spectral decomposition. A significant speedup (by about two orders of magnitude) is achieved for this application using the proposed method.
presentation | video | arXiv | code
Introducing the p-Laplacian Spectra
I Cohen, G Gilboa
Scale Space and Variational Methods in Computer Vision
In this work we develop a nonlinear decomposition, associated with nonlinear eigenfunctions of the p-Laplacian for p ∈ (1, 2). With this decomposition we can process signals of different degrees of smoothness. We first analyze solutions of scale spaces, generated by γ-homogeneous operators, γ ∈ R. An analytic solution is formulated when the scale space is initialized with a nonlinear eigenfunction of the respective operator. We show that the flow is extinct in finite time for γ ∈ [0, 1). A main innovation in this study is concerned with operators of fractional homogeneity, which require the mathematical framework of fractional calculus. The proposed transform rigorously defines the notions of decomposition, reconstruction, filtering and spectrum. The theory is applied to the p-Laplacian operator, where the tools developed in this framework are demonstrated.
presentation | video | arXiv | code
Stable Explicit p-Laplacian Flows Based on Nonlinear Eigenvalue Analysis
I Cohen, A Falik, G Gilboa
Scale Space and Variational Methods in Computer Vision
Implementation of nonlinear flows by explicit schemes can be very convenient, due to their simplicity and low-computational cost per time step. A well known drawback is the small time step bound, referred to as the CFL condition, which ensures a stable flow. For p-Laplacian flows, with 1<p<2, explicit schemes without gradient regularization require, in principle, a time step approaching zero. However, numerical implementations show explicit flows with small time-steps are well behaved. We can now explain and quantify this phenomenon.
In this paper we examine explicit p-Laplacian flows by analyzing the evolution of nonlinear eigenfunctions, with respect to the p-Laplacian operator. For these cases analytic solutions can be formulated, allowing for a comprehensive analysis. A generalized CFL condition is presented, relating the time step to the inverse of the nonlinear eigenvalue. Moreover, we show that the flow converges and formulate a bound on the error of the discrete scheme. Finally, we examine general initial conditions and propose a dynamic time-step bound, which is based on a nonlinear Rayleigh quotient.
presentation | video | arXiv | code
Energy dissipating flows for solving nonlinear eigenpair problems
I Cohen, G Gilboa
Journal of Computational Physics
This work is concerned with computing nonlinear eigenpairs, which model solitary waves and various other physical phenomena. We aim at solving nonlinear eigenvalue problems of the general form T(u)=λQ(u). In our setting T is a variational derivative of a convex functional (such as the Laplacian operator with respect to the Dirichlet energy), Q is an arbitrary bounded nonlinear operator and λ is an unknown (real) eigenvalue. We introduce a flow that numerically generates an eigenpair solution by its steady state.
Analysis for the general case is performed, showing a monotone decrease in the convex functional throughout the flow. When T is the Laplacian operator, a complete discretized version is presented and anlalyzed. We implement our algorithm on Korteweg and de Vries (KdV) and nonlinear Schrödinger (NLS) equations in one and two dimensions. The proposed approach is very general and can be applied to a large variety of models. Moreover, it is highly robust to noise and to perturbations in the initial conditions, compared to classical Petiashvili-based methods.
presentation | video | arXiv | code
