# 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

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 code can be obtained by visiting the GitHub page below, and clicking on the green “Clone or download” button.

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