# 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