compsense.algorithms.TwIST¶

class compsense.algorithms.TwIST(P, tau, psi_function=None, phi_function=None, lam1=0.0001, alpha=0, beta=0, stop_criterion=1, tolA=0.01, debias=False, tolD=0.001, maxiter=1000, miniter=5, maxiter_debias=200, miniter_debias=5, enforce_monotone=True, sparse=True, verbose=True)¶

Two-step Iterative Shrinkage/Thresholding Algorithm for Linear Inverse Problems. Solves the regularization problem

$arg min_x = 0.5*|| y - A x ||_2^2 + \tau \phi( x ),$

where $A$ is a generic matrix and $phi()$ is a regularizarion function such that the solution of the denoising problem

$\Psi_{\tau}(y) = arg min_x = 0.5*|| y - x ||_2^2 + \tau \phi( x ),$

is known.

For further details about the TwIST algorithm, see the paper:

J. Bioucas-Dias and M. Figueiredo, "A New TwIST: Two-Step
Iterative Shrinkage/Thresholding Algorithms for Image 
Restoration",  IEEE Transactions on Image processing, 2007.

and

J. Bioucas-Dias and M. Figueiredo, "A Monotonic Two-Step 
Algorithm for Compressive Sensing and Other Ill-Posed 
Inverse Problems", submitted, 2007.

Parameters :

P : instance of a subclass of problemBase

The problem that the algorithm solves.

tau : float,

regularization parameter, usually a non-negative real parameter of the objective function (see above).

psi_function : function handle, optional

handle to denoising function (the default is soft threshold)

phi_function : function handle, optional

handle to regularizer needed to compute the objective function. (the default = $||x||_1$ )

lam1 : float, optional (default=0.04)

parameter of the TwIST algorithm: Optimal choice: lam1 = min eigenvalue of : $A^T*A$ . If min eigenvalue of $A^T*A$ equals 0, or unknwon, set lam1 to a value much smaller than 1. Rule of Thumb:

lam1=1e-4 for severyly ill-conditioned problems

lam1=1e-2 for mildly ill-conditioned problems

lam1=1 for A unitary direct operators

Note

If max eigenvalue of : $A^T*A$ > 1, the algorithm may diverge. This is to be avoided by taking one of the follwoing measures:

Set enforce_monotone=True (default)

Solve the equivalenve minimization problem

$min_x = 0.5*|| (y/c) - (A/c) x ||_2^2 + (tau/c^2) \phi( x ),$

where $c > 0$ ensures that max eigenvalue of : $(A^TA/c^2) \leq 1$ .

alpha : float, optional (default=calculated as function of lam1)

parameter alpha of TwIST (see ex. (22) of the paper)

beta : float, optional (default=calculated as function of lam1)

parameter beta of twist (see ex. (23) of the paper)

stop_criterion : {0, 1, 2, 3}, optional (default=0)

type of stopping criterion to use

stop_criterion=0 algorithm stops when the relative change in the number of non-zero components of the estimate falls below tolA

stop_criterion=1 stop when the relative change in the objective function falls below tolA

stop_criterion=2 stop when the relative norm of the difference between two consecutive estimates falls below tolA

stop_criterion=3 stop when the objective function becomes equal or less than tolA.

tolA : float, optional (default=0.01)

stopping threshold.

debias : bool, optional (default=False)

debiasing option

Note

Debiasing is an operation aimed at the computing the solution of the LS problem

$arg min_x = 0.5*|| y - A^T x ||_2^2$

where : $A^T$ is the submatrix of A obatained by deleting the columns of A corresponding of components of x set to zero by the TwIST algorithm

tolD : float, optional (default=0.0001)

stopping threshold for the debiasing phase. If no debiasing takes place, this parameter, is ignored.

maxiter : int, optional (default=1000)

maximum number of iterations allowed in the main phase of the algorithm.

miniter : int, optional (default=5)

minimum number of iterations performed in the main phase of the algorithm.

maxiter_debias : int, optional (default=5)

maximum number of iterations allowed in the debising phase of the algorithm.

miniter_debias : int, optional (default=5)

minimum number of iterations to perform in the debiasing phase of the algorithm.

enforce_monotone : bool, optional (default=True)

enforce monotonic decrease in f.

sparse : bool, optional (default=True)

Accelarates the convergence rate when the regularizer $\Phi(x)$ is sparse inducing, such as : $||x||_1$ .

Verbose : bool, optional (default=False)

work silently (False) or verbosely (True)

Attributes

`P`	The problem that the algorithm is set to solve
`mses`	The statistics of the MSE per iteration.
`name`	Name of the algorithm
`objectives`	The statistics of the objective value per iteration.
`times`	Time per iteration.

compsense.algorithms.TwIST¶

Previous topic

Next topic

This Page

Navigation

compsense.algorithms.TwIST¶

Previous topic

Next topic

This Page

Quick search

Navigation