Convex Relaxation

Truncated Newton Interior Points Method (TNIPM)

This method can be used to solve problems of type:

(1)\[\min \| A x - b \|_2^2 + \lambda \| x \|_1\]

The method works as follows:

  • The \(\ell_1\) regularized LSP (Least Squares Program) above is transformed into a convex quadratic program with linear inequality constraints.

  • The logarithmic barrier for the quadratic program is constructed.

  • The central path for this logarithmic barrier minimizer is identified.

  • Truncated newton method is used to solve for points on the central path.

    • Compute the search direction as an approximate solution to the Newton system

    • Compute the step size by backtracking line search

    • Update the iterate

    • Construct a dual feasible point

    • Evaluate the duality gap

    • Repeat till the relative duality gap is within a specified threshold

  • The Newton system is solved approximately using preconditioned conjugate gradients.

The solve_from versions below are useful if the solution is known partially. The solve versions are more directly applicable when solution is not known. Both solve_from and solve are available as regular and JIT-compiled versions.

l1ls.solve_from(A, y, lambda_, x0, u0[, …])

Solves \(\min \| A x - b \|_2^2 + \\lambda \| x \|_1\) using the Truncated Newton Interior Point Method

l1ls.solve_from_jit(A, y, lambda_, x0, u0[, …])

Solves \(\min \| A x - b \|_2^2 + \\lambda \| x \|_1\) using the Truncated Newton Interior Point Method

l1ls.solve(A, y, lambda_[, x0, u0, tol, xi, …])

Solves \(\min \| A x - b \|_2^2 + \\lambda \| x \|_1\) using the Truncated Newton Interior Point Method

l1ls.solve_jit(A, y, lambda_[, x0, u0, tol, …])

Solves \(\min \| A x - b \|_2^2 + \\lambda \| x \|_1\) using the Truncated Newton Interior Point Method

An example is provided in Convex Relaxation Techniques.

Alternating Directions Methods

This is based on [YZ11].

A tutorial has been provided to explore these methods in action. The yall1.solve method is an overall wrapper method for solving different types of \(\ell_1\) minimization problems. It in turn calls the lower level methods for solving specific types of problems.

yall1.solve(A, b[, x0, z0, W, weights, …])

Wrapper method to solve a variety of l1 minimization problems using ADMM

yall1.solve_bp(A, b, x0, z0, w, nonneg, …)

Solves the problem \(\min \| x \|_1 \, \\text{s.t.}\, A x = b\) using ADMM

yall1.solve_bp_jit(A, b, x0, z0, w, nonneg, …)

Solves the problem \(\min \| x \|_1 \, \\text{s.t.}\, A x = b\) using ADMM

yall1.solve_l1_l2(A, b, x0, z0, w, nonneg, …)

Solves the problem \(\min \| x \|_1 + \\frac{1}{2 \\rho} \| A x - b \|_2^2\) using ADMM

yall1.solve_l1_l2_jit(A, b, x0, z0, w, …)

Solves the problem \(\min \| x \|_1 + \\frac{1}{2 \\rho} \| A x - b \|_2^2\) using ADMM

yall1.solve_l1_l2con(A, b, x0, z0, w, …)

Solves the problem \(\min \| x \|_1 \\text{s.t.} \| A x - b \|_2 \\leq \\delta\) using ADMM

yall1.solve_l1_l2con_jit(A, b, x0, z0, w, …)

Solves the problem \(\min \| x \|_1 \\text{s.t.} \| A x - b \|_2 \\leq \\delta\) using ADMM

FOcal Underdetermined System Solver (FOCUSS)

This is based on [Ela10] (section 3.2.1).

focuss.matrix_solve_noiseless(Phi, y[, p, …])

Solves the sparse recovery problem using FOCUSS.

focuss.step_noiseless(Phi, y, x[, p])

A step in the FOCUSS algorithm

Example:

Spectral Projected Gradient L1 (SPGL1)

Berg and Friedlander proposed the spectral projected gradient l1 (SPGL1) algorithm in [vdBF08]. They provide a MATLAB package implementing the algorithm in [vdBF19]. A NumPy based Python port is also available here. We have implemented the algorithm with JAX.

spgl1.solve_lasso_from(A, b, tau, x0[, …])

Solves the LASSO problem using SPGL1 algorithm with an initial solution

spgl1.solve_lasso(A, b, tau[, options, tracker])

Solves the LASSO problem using SPGL1 algorithm

spgl1.solve_lasso_jit(A, b, tau[, options, …])

Solves the LASSO problem using SPGL1 algorithm

spgl1.solve_bpic_from(A, b, sigma, x0[, …])

Solves the BPIC problem using SPGL1 algorithm with an initial solution

spgl1.solve_bpic_from_jit(A, b, sigma, x0[, …])

Solves the BPIC problem using SPGL1 algorithm with an initial solution

spgl1.solve_bpic(A, b, sigma[, options, tracker])

Solves the BPIC problem using SPGL1 algorithm

spgl1.solve_bpic_jit(A, b, sigma[, options, …])

Solves the BPIC problem using SPGL1 algorithm

spgl1.solve_bp(A, b[, options, tracker])

Solves the Basis Pursuit problem using SPGL1 algorithm

spgl1.solve_bp_jit(A, b[, options, tracker])

Solves the Basis Pursuit problem using SPGL1 algorithm

Associated data types

spgl1.SPGL1Options(bp_tol, ls_tol, opt_tol, …)

Options for the SPGL1 algorithm

spgl1.SPGL1LassoState(x, g, r, f_past, …)

Solution state of the SPGL1 algorithm for LASSO problem

spgl1.SPGL1BPState(x, g, r, f_past, tau, …)

Solution state of the SPGL1 algorithm for BPIC problem

Examples

Theory