FASTA

fast adaptive
shrinkage/thresholding
algorithm

FASTA (Fast Adaptive Shrinkage/Thresholding Algorithm) is an efficient, easy-to-use implementation of the Forward-Backward Splitting (FBS) method (also known as the proximal gradient method) for regularized optimization problems. Many variations on FBS are available in FASTA, including the popular accelerated variant FISTA (Beck and Teboulle ’09), the adaptive stepsize rule SpaRSA (Wright, Nowak, Figueiredo ’09), and other variants described in the review A Field Guide to Forward-Backward Splitting with a FASTA Implementation. Whether the problem you are solving is simple or complex, FASTA makes things easy by handling issues like stepsize selection, acceleration, and stopping conditions for you.

Downloads

The following files are available for download:

The paper: A Field Guide to Forward-Backward Splitting with a FASTA Implementation
The FASTA user’s guide
The FASTA code

What can FASTA solve?

FASTA targets problems of the form

$$\large \text{minimize} \quad f(Ax)+g(x)$$

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.

\begin{align} \large \text{lasso regression} & \large \qquad \min_x\,\, \frac{1}{2}||Ax-b|| \,\,\text{ subject to }\,\, ||x||_1\le\lambda \\ \large \text{sparse least squares} & \large \qquad \min_x\,\, \mu||x||_1 + \frac{1}{2}||Ax-b||^2 \\ \large \text{non-negative least squares} & \large \qquad \min_x\,\, ||Ax-b||^2 \,\,\text{ subject to }\,\, x\ge 0 \\ \large \text{sparse logistic regression} & \large \qquad \min_x\,\, \mu||x||_1 + \text{logit}(Ax,b) \\ \large \text{1-bit matrix completion} & \large \qquad \min_X\,\, \mu||X||_* + \text{logit}(X,Y) \\ \large \text{phase retrieval} & \large \large \qquad \min_X\,\, \mu||X||_* \,\,\text{ subject to }\,\, \mathcal{A}(X) = b, X\succeq 0 \\ \large \text{democratic representations} & \large \qquad \min_x\,\, \mu||x||_\infty + \frac{1}{2} ||Ax-b||^2 \\ \large \text{total-variation denoising} & \large \qquad \min_x\,\, \mu||\nabla x||_1 + \frac{1}{2} ||x-f||^2 \\ \large \text{non-negative matrix factorization} & \large \qquad \min \,\, ||A-XY||^2 \,\,\text{ subject to }\,\, X,Y \ge 0 \end{align}

About the Authors

Fasta was developed by:

Tom Goldstein - University of Maryland
Christoph Studer - Cornell University
Richard Baraniuk - Rice University

How to cite FASTA

If you find that FASTA has contributed to your published work, please include the following citations:

@article{GoldsteinStuderBaraniuk:2014,
  Author = {Goldstein, Tom and Studer, Christoph and Baraniuk, Richard},
  Title = {A Field Guide to Forward-Backward Splitting with a {FASTA} Implementation},
  year = {2014},
  journal = {arXiv eprint},
  volume = {abs/1411.3406},
  url = {http://arxiv.org/abs/1411.3406},
  ee = {http://arxiv.org/abs/1411.3406}
}

@misc{FASTA:2014,
  Author = {Goldstein, Tom and Studer, Christoph and Baraniuk, Richard},
  title = {{FASTA}:  A Generalized Implementation of Forward-Backward Splitting},
  note = {http://arxiv.org/abs/1501.04979},
  month = {January},
  year = {2015}
}