L1 Minimization

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 Sparse Recovery via L1 minimization.

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