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.

FASTA is currently available in Matlab and R with Python coming soon.

Downloads

Before using FASTA, we recommend that you have a look at the following documents:

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

The FASTA Matlab code can be obtained by visiting the GitHub page below, and clicking on the green “Clone or download” button.

The FASTA download page on GitHub

The R implementation of FASTA was provided by Eric Chi, and is available via CRAN.

The FASTA R package

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 originally developed by:

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

The R implementation was developed by Eric Chi.

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}
}

Search

Categories