FISTA: attaining a rate of convergence proportional to k^-3 for medium values of k in a robust fashion
Abstract
The minimization of a cost functional composed by the sum of two convex functions, i.e. F = f + r; such that f() is smooth (L-Lipschitz continuous) and r() is a possibly nonsmooth function that usually promotes a sparse solution, is a mathematical problem which has several applications in signal/image processing and deep learning. There exists several alternatives for optimizing (1); APG (accelerated proximal gradient) is a very popular choice due to its simplicity and its rate of convergence (RoC), i.e. O(kÀÀ2), where k represents the number of iterations. When the so-called regularization function r() is the `1 norm, APG is called FISTA. The key objective of this document is to provide the mathematical foundation to modify FISTA such it achieves a RoC proportional to kÀÀ3, in a robust fashion, for small/medium values of k (with the default O(kÀÀ2) behavior for large k), with the overall effect of, at least, doubling FISTAÕs practical performance. Furthermore, such results will also be extended to APG, where other sparsity promoting regularizers such the elastic net norm (r() = 1k k1 +2k k22 ), SCAD, the `0 norm (or approximations such the CEL0 envelope), etc., will also be considered. Moreover, given that APG, as well as other acceleration methods, can be understood as multi-step integration schemes, we will also explore the applicability of the proposed method to the integration of the gradient flow equation. The original FISTA has several applications for inverse problems with a linear function f, e.g. denoising, convolutional sparse representations, background modeling, dictionary learning, etc. Moreover, since FISTA has also been recently adapted for the case of nonlinear or nonconvex f, (i.e. f = f1 +f2, where f1 is non-convex and f2 is convex) it can also be used for model-based deep learning approaches, lowrank regularization, matrix completion, etc. Boosting FISTAÕs practical performance has a direct impact on all the applications which use it as their primary optimization method.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Apr 19, 2023
- Source ID
- W911NF2210296
Entities
People
- Paúl Rodríguez
Organizations
- Army Contracting Command
- Pontifical Catholic University of Peru
- United States Army