fista.py 🚧

Source: LION/classical_algorithms/fista.py

Warning

This file has not yet received a complete narrative and docstring audit. Its public source-level API is listed automatically below.

FISTA algorithm for l1-regularized problems.

soft_threshold(v: torch.Tensor, tau: float) → torch.Tensor

Soft thresholding operator.

It is defined as:

\[\begin{split}S_{\tau}(v) = \mathrm{sign}(v) \cdot \\max(|v| - \tau, 0)\end{split}\]

Parameters ———- v : torch.Tensor Input tensor. tau : float Threshold parameter.

Returns ——- torch.Tensor Result after applying soft thresholding.

fista_l1(op: Operator, y: torch.Tensor, lam: float, max_iter: int = 200, tol: float = 0.0001, L: float | None = None, verbose: bool = False, progress_bar: bool = False) → torch.Tensor

Solve \(\min_w \tfrac12\lVert A w - y\rVert_2^2 + \lambda \lVert w\rVert_1\) by FISTA.

Implements the Fast Iterative Shrinkage-Thresholding Algorithm (FISTA) for \(\ell_1\)-regularised least squares [BeckTeboulle2009]. FISTA is an accelerated proximal-gradient method for composite objectives \(f(w) + \lambda \lVert w\rVert_1\) with smooth data-fidelity term \(f(w) = \tfrac12\lVert A w - y\rVert_2^2\); see [DaubechiesDefriseDeMol2004] for the original ISTA scheme and [ParikhBoyd2014] for a general overview of proximal-gradient methods.

Parameters ———- op : Operator Linear operator implementing the forward map and its adjoint. It is called as op(w) and op.adjoint(r). y : torch.Tensor Measurements, shape (M,). lam : float \(\ell_1\) regularisation parameter. max_iter : int Maximum number of iterations. tol : float Relative stopping threshold on \(w\). The iteration stops once norm(w_next - w) / (norm(w) + 1e-8) < tol. L : float or None Lipschitz constant of \(A^\top A\). If None, estimated by a power method on the normal operator \(A^\top A\), following the standard practice in FISTA-type schemes [BeckTeboulle2009]. verbose : bool If True, prints basic progress such as objective value and relative change. progress_bar : bool If True, wraps the iteration in a tqdm progress bar.

Returns ——- w : torch.Tensor Estimated coefficient vector, shape (Nw,).

References ———- .. [DaubechiesDefriseDeMol2004] I. Daubechies, M. Defrise, and C. De Mol, “An iterative thresholding algorithm for linear inverse problems with a sparsity constraint”, Communications on Pure and Applied Mathematics, 57(11):1413-1457, 2004. .. [BeckTeboulle2009] A. Beck and M. Teboulle, “A fast iterative shrinkage-thresholding algorithm for linear inverse problems”, SIAM Journal on Imaging Sciences, 2(1):183-202, 2009. .. [ParikhBoyd2014] N. Parikh and S. Boyd, “Proximal Algorithms”, Foundations and Trends in Optimization, 1(3):127-239, 2014.