Gradient flows and randomised thresholding: sparse inversion and classification
From MaRDI portal
Allen-Cahn equationclassificationpiecewise-deterministic Markov processessparsitystochastic processessubgradient flows
Ordinary differential inclusions (34A60) Inverse problems for PDEs (35R30) Applications of continuous-time Markov processes on discrete state spaces (60J28) Computational methods for problems pertaining to statistics (62-08) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Ridge regression; shrinkage estimators (Lasso) (62J07)
Abstract: Sparse inversion and classification problems are ubiquitous in modern data science and imaging. They are often formulated as non-smooth minimisation problems. In sparse inversion, we minimise, e.g., the sum of a data fidelity term and an L1/LASSO regulariser. In classification, we consider, e.g., the sum of a data fidelity term and a non-smooth Ginzburg--Landau energy. Standard (sub)gradient descent methods have shown to be inefficient when approaching such problems. Splitting techniques are much more useful: here, the target function is partitioned into a sum of two subtarget functions -- each of which can be efficiently optimised. Splitting proceeds by performing optimisation steps alternately with respect to each of the two subtarget functions. In this work, we study splitting from a stochastic continuous-time perspective. Indeed, we define a differential inclusion that follows one of the two subtarget function's negative subdifferential at each point in time. The choice of the subtarget function is controlled by a binary continuous-time Markov process. The resulting dynamical system is a stochastic approximation of the underlying subgradient flow. We investigate this stochastic approximation for an L1-regularised sparse inversion flow and for a discrete Allen-Cahn equation minimising a Ginzburg--Landau energy. In both cases, we study the longtime behaviour of the stochastic dynamical system and its ability to approximate the underlying subgradient flow at any accuracy. We illustrate our theoretical findings in a simple sparse estimation problem and also in low- and high-dimensional classification problems.
Recommendations
- The Split Bregman Method for L1-Regularized Problems
- Minimization of non-smooth, non-convex functionals by iterative thresholding
- A sparsity preserving stochastic gradient methods for sparse regression
- Analysis of stochastic gradient descent in continuous time
- A random block-coordinate Douglas-Rachford splitting method with low computational complexity for binary logistic regression
Cites work
- A Stochastic Approximation Method
- An MBO scheme for clustering and semi-supervised clustering of signed networks
- An unconditionally stable hybrid numerical method for solving the Allen-Cahn equation
- Analysis of stochastic gradient descent in continuous time
- Asymptotic convergence of nonlinear contraction semigroups in Hilbert space
- Classification and image processing with a semi‐discrete scheme for fidelity forced Allen–Cahn on graphs
- Compressed sensing with coherent and redundant dictionaries
- Diffuse Interface Models on Graphs for Classification of High Dimensional Data
- Effective dynamics of multi-vortices in an external potential for the Ginzburg–Landau gradient flow
- Elliptic optimal control problems with L^1-control cost and applications for the placement of control devices
- Exponential ergodicity for Markov processes with random switching
- Foundations of modern probability. In 2 volumes
- Geometrical image segmentation by the Allen-Cahn equation
- Ginzburg-Landau equation and motion by mean curvature. I: Convergence
- Graph Merriman-Bence-Osher as a semidiscrete implicit Euler scheme for graph Allen-Cahn flow
- scientific article; zbMATH DE number 3878095 (Why is no real title available?)
- scientific article; zbMATH DE number 3901778 (Why is no real title available?)
- scientific article; zbMATH DE number 6860839 (Why is no real title available?)
- scientific article; zbMATH DE number 3894826 (Why is no real title available?)
- scientific article; zbMATH DE number 5046597 (Why is no real title available?)
- scientific article; zbMATH DE number 3398324 (Why is no real title available?)
- scientific article; zbMATH DE number 3045283 (Why is no real title available?)
- Introduction to Piecewise Differentiable Equations
- Nineteen Dubious Ways to Compute the Exponential of a Matrix, Twenty-Five Years Later
- Numerical analysis of the Allen-Cahn equation and approximation for mean curvature flows
- On perturbed proximal gradient algorithms
- On the infinite swapping limit for parallel tempering
- Optimal Transport
- Proximal splitting methods in signal processing
- Quantitative ergodicity for some switched dynamical systems
- Random time step probabilistic methods for uncertainty quantification in chaotic and geometric numerical integration
- Solution paths of variational regularization methods for inverse problems
- Stochastic Allen-Cahn equation with logarithmic potential
- Stochastic forward-backward splitting for monotone inclusions
- The zig-zag process and super-efficient sampling for Bayesian analysis of big data
- Threshold dynamics for the piecewise constant Mumford-Shah functional
- Uncertainty quantification in graph-based classification of high dimensional data
- Weak convergence methods and singularly perturbed stochastic control and filtering problems
Cited in
(3)
This page was built for publication: Gradient flows and randomised thresholding: sparse inversion and classification
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5058108)
