L1 Minimization¶
Truncated Newton Interior Points Method (TNIPM)¶
This method can be used to solve problems of type:
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.
|
Solves \(\min \| A x - b \|_2^2 + \lambda \| x \|_1\) using the Truncated Newton Interior Point Method |
|
Solves \(\min \| A x - b \|_2^2 + \lambda \| x \|_1\) using the Truncated Newton Interior Point Method |
|
Solves \(\min \| A x - b \|_2^2 + \lambda \| x \|_1\) using the Truncated Newton Interior Point Method |
|
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¶
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.
|
Wrapper method to solve a variety of l1 minimization problems using ADMM |
|
Solves the problem \(\min \| x \|_1 \, \text{s.t.}\, A x = b\) using ADMM |
|
Solves the problem \(\min \| x \|_1 \, \text{s.t.}\, A x = b\) using ADMM |
|
Solves the problem \(\min \| x \|_1 + \frac{1}{2 \rho} \| A x - b \|_2^2\) using ADMM |
|
Solves the problem \(\min \| x \|_1 + \frac{1}{2 \rho} \| A x - b \|_2^2\) using ADMM |
|
Solves the problem \(\min \| x \|_1 \text{s.t.} \| A x - b \|_2 \leq \delta\) using ADMM |
|
Solves the problem \(\min \| x \|_1 \text{s.t.} \| A x - b \|_2 \leq \delta\) using ADMM |