Class FISTA

source code

            object --+        
                     |        
   bases.BaseAlgorithm --+    
                         |    
   bases.ExplicitAlgorithm --+
                             |
                object --+   |
                         |   |
  bases.IterativeAlgorithm --+
                             |
                object --+   |
                         |   |
bases.InformationAlgorithm --+
                             |
                            FISTA

The fast iterative shrinkage-thresholding algorithm.

Parameters
----------
eps : Positive float. Tolerance for the stopping criterion.

use_gap : Boolean. If true, FISTA will use a dual gap, from the interface
        DualFunction, in the stopping criterion as

                if function.gap(beta) < eps:
                    break

        Default is False, since the gap may be very expensive to compute.

info : List or tuple of utils.consts.Info. What, if any, extra run
        information should be stored. Default is an empty list, which means
        that no run information is computed nor returned.

max_iter : Non-negative integer. Maximum allowed number of iterations.

min_iter : Non-negative integer less than or equal to max_iter. Minimum
        number of iterations that must be performed. Default is 1.

Example
-------
>>> from parsimony.algorithms.proximal import FISTA
>>> from parsimony.functions import LinearRegressionL1L2TV
>>> import scipy.sparse as sparse
>>> import numpy as np
>>>
>>> np.random.seed(42)
>>> X = np.random.rand(100, 50)
>>> y = np.random.rand(100, 1)
>>> A = sparse.csr_matrix((50, 50))  # Unused here
>>> function = LinearRegressionL1L2TV(X, y, 0.0, 0.0, 0.0,
...                                   A=A, mu=0.0)
>>> fista = FISTA(max_iter=10000)
>>> beta1 = fista.run(function, np.random.rand(50, 1))
>>> beta2 = np.dot(np.linalg.pinv(X), y)
>>> round(np.linalg.norm(beta1 - beta2), 13)
4.6182817e-06
>>>
>>> np.random.seed(42)
>>> X = np.random.rand(100, 50)
>>> y = np.random.rand(100, 1)
>>> A = sparse.csr_matrix((50, 50))  # Unused here
>>> function = LinearRegressionL1L2TV(X, y, 0.1, 0.0, 0.0,
...                                   A=A, mu=0.0)
>>> fista = FISTA(max_iter=10000)
>>> beta1 = fista.run(function, np.random.rand(50, 1))
>>> beta2 = np.dot(np.linalg.pinv(X), y)
>>> round(np.linalg.norm(beta1 - beta2), 14)
0.82723292510703
>>> np.linalg.norm(beta2.ravel(), 0)
50
>>> np.linalg.norm(beta1.ravel(), 0)
7

Find the minimiser of the given function, starting at beta.

Parameters
----------
function : Function. The function to minimise.

beta : Numpy array. The start vector.