Nuit Blanche: FASTA: A Field Guide to Forward-Backward Splitting with a FASTA Implementation

Thursday, January 15, 2015

FASTA: A Field Guide to Forward-Backward Splitting with a FASTA Implementation - implementation -

A Field Guide to Forward-Backward Splitting with a FASTA Implementation by Tom Goldstein, Christoph Studer, Richard Baraniuk

Non-differentiable and constrained optimization play a key role in machine learning, signal and image processing, communications, and beyond. For high-dimensional minimization problems involving large datasets or many unknowns, the forward-backward splitting method provides a simple, practical solver. Despite its apparently simplicity, the performance of the forward-backward splitting is highly sensitive to implementation details.
This article is an introductory review of forward-backward splitting with a special emphasis on practical implementation concerns. Issues like stepsize selection, acceleration, stopping conditions, and initialization are considered. Numerical experiments are used to compare the effectiveness of different approaches.
Many variations of forward-backward splitting are implemented in the solver FASTA (short for Fast Adaptive Shrinkage/Thresholding Algorithm). FASTA provides a simple interface for applying forward-backward splitting to a broad range of problems.

FASTA is on Tom's page. From that page:

What can FASTA solve?
FASTA targets problems of the form

where A is a linear operator, f is a differentiable function, and g is a “simple” (but possibly non-smooth) function. Problems of this form including sparse least-squares (basis-pursuit), lasso, total-variation denoising, matrix completion, and many more. The FASTA implementation is incredibly flexible; users can solve almost anything by providing their own f, g, and A. However, for users that want quick out-of-the-box solutions, simple customized solvers are provided for the following problems. See the FASTA user’s manual for details.