A Three-Operator Splitting Algorithm for Nonconvex Sparsity Regularization
From MaRDI portal
Publication:5005209
DOI10.1137/20M1326775zbMATH Open1473.90126arXiv2006.08951OpenAlexW3192362104MaRDI QIDQ5005209FDOQ5005209
Publication date: 9 August 2021
Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)
Abstract: Sparsity regularization has been largely applied in many fields, such as signal and image processing and machine learning. In this paper, we mainly consider nonconvex minimization problems involving three terms, for the applications such as: sparse signal recovery and low rank matrix recovery. We employ a three-operator splitting proposed by Davis and Yin (called DYS) to solve the resulting possibly nonconvex problems and develop the convergence theory for this three-operator splitting algorithm in the nonconvex case. We show that if the step size is chosen less than a computable threshold, then the whole sequence converges to a stationary point. By defining a new decreasing energy function associated with the DYS method, we establish the global convergence of the whole sequence and a local convergence rate under an additional assumption that this energy function is a Kurdyka-ojasiewicz function. We also provide sufficient conditions for the boundedness of the generated sequence. Finally, some numerical experiments are conducted to compare the DYS algorithm with some classical efficient algorithms for sparse signal recovery and low rank matrix completion. The numerical results indicate that DYS method outperforms the exsiting methods for these specific applications.
Full work available at URL: https://arxiv.org/abs/2006.08951
nonconvex optimizationsparsity regularizationsparse signal recoverylow rank matrix completionthree-operator splitting method
Numerical mathematical programming methods (65K05) Applications of mathematical programming (90C90) Matrix completion problems (15A83) Nonconvex programming, global optimization (90C26) Nonlinear programming (90C30)
Cites Work
- Title not available (Why is that?)
- Coherence pattern-guided compressive sensing with unresolved grids
- A Fast Algorithm for Sparse Reconstruction Based on Shrinkage, Subspace Optimization, and Continuation
- Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers
- Regularization and Variable Selection Via the Elastic Net
- Convex analysis approach to d. c. programming: Theory, algorithms and applications
- A Singular Value Thresholding Algorithm for Matrix Completion
- Exact matrix completion via convex optimization
- The Split Bregman Method for L1-Regularized Problems
- Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
- Proximal alternating linearized minimization for nonconvex and nonsmooth problems
- Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm
- Alternating Direction Algorithms for $\ell_1$-Problems in Compressive Sensing
- Clarke Subgradients of Stratifiable Functions
- Bregman Iterative Algorithms for $\ell_1$-Minimization with Applications to Compressed Sensing
- Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
- The Łojasiewicz Inequality for Nonsmooth Subanalytic Functions with Applications to Subgradient Dynamical Systems
- Image restoration by minimizing zero norm of wavelet frame coefficients
- Superresolution via Sparsity Constraints
- A parameterized Douglas-Rachford splitting algorithm for nonconvex optimization
- Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems
- A D.C. Optimization Algorithm for Solving the Trust-Region Subproblem
- A three-operator splitting scheme and its optimization applications
- A Weighted Difference of Anisotropic and Isotropic Total Variation Model for Image Processing
- Computing sparse representation in a highly coherent dictionary based on difference of \(L_1\) and \(L_2\)
- Minimization of $\ell_{1-2}$ for Compressed Sensing
- Fixed-rank matrix factorizations and Riemannian low-rank optimization
- A Proximal Minimization Algorithm for Structured Nonconvex and Nonsmooth Problems
- A method for finding structured sparse solutions to nonnegative least squares problems with applications
- Alternating Direction Method of Multipliers for a Class of Nonconvex and Nonsmooth Problems with Applications to Background/Foreground Extraction
- Global convergence of ADMM in nonconvex nonsmooth optimization
- Global Convergence of Splitting Methods for Nonconvex Composite Optimization
- Peaceman-Rachford splitting for a class of nonconvex optimization problems
- Guarantees of Riemannian optimization for low rank matrix recovery
- DC formulations and algorithms for sparse optimization problems
- Convergence Analysis of Douglas--Rachford Splitting Method for “Strongly + Weakly” Convex Programming
- PhaseLiftOff: an accurate and stable phase retrieval method based on difference of trace and Frobenius norms
- Douglas--Rachford Splitting and ADMM for Nonconvex Optimization: Tight Convergence Results
- A proximal difference-of-convex algorithm with extrapolation
- Guarantees of Riemannian optimization for low rank matrix completion
- An envelope for Davis-Yin splitting and strict saddle-point avoidance
Cited In (5)
- A parameterized three-operator splitting algorithm for non-convex minimization problems with applications
- A three-operator splitting algorithm with deviations for generalized DC programming
- Extrapolated plug-and-play three-operator splitting methods for nonconvex optimization with applications to image restoration
- A preconditioned Riemannian gradient descent algorithm for low-rank matrix recovery
- Proximal variable smoothing method for three-composite nonconvex nonsmooth minimization with a linear operator
Uses Software
This page was built for publication: A Three-Operator Splitting Algorithm for Nonconvex Sparsity Regularization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5005209)
