Prev Next Index-> contents reference index search external Up-> l1_regular l1_with_l2 l1_regular-> l1_with_l2 l1_quadratic l1_linear whats_new l1_with_l2-> with_l2_ok.m l1_newton_l2 Headings-> Syntax Notation Purpose Restriction First Order Conditions max_itr A a B b delta x_out info ---..First Order Condition ---..Relaxation Factor ---..Step Size Example Newton Step

$\newcommand{\R}[1]{{\rm #1}}$$\newcommand{\B}[1]{{\bf #1}}$
Combined L1 and L2 Fitting and or Regularization

Syntax
[x_out] = l1_with_l2(max_itr, A, a, B, b, delta) [x_out, info] = l1_with_l2(max_itr, A, a, B, b, delta)

Notation
We use $1_\ell \in \B{R}^\ell$ to denote the vector will all elements equal to one. Given a vector $w \in \B{R}^\ell$ we use $D(w) \in \B{R}^{\ell \times \ell}$, to denote the corresponding diagonal matrix.

Purpose
We are given a matrix $A \in \B{R}^{\ell \times n}$, a vector $a \in \B{R}^\ell$, a matrix $B \in \B{R}^{m \times n}$, and a vector $b \in \B{R}^m$. The problem we wish to solve is $$\begin{array}{lll} \R{minimize} & \| A x - a^\R{T} \|_1 + \frac{1}{2} \| B x - b \|_2^2 & \R{w.r.t} \; x \in \B{R}^n \end{array}$$

Restriction
For any vector $p \in \B{R}^\ell$ with $p_i > 0$ for all $i$, the matrix $A^\R{T} D(p) A + B^\R{T} B$ must have rank $n$.

First Order Conditions
We reformulate this as the following equivalent linear programming problem $$\begin{array}{lll} \R{minimize} & \frac{1}{2} \| B x - b \|_2^2 + 1_\ell^\R{T} v_+ + 1_\ell^\R{T} v_- & \R{w.r.t.} ( v_+ , v_- , x ) \in \B{R}_+^{2 \ell} \times \B{R}_n \\ \R{subject \; to} & A x - b = v_+ - v_- \end{array}$$ The first order conditions for a minimum of this problem are equivalent to $F = 0$ where $F : \B{R}^{5 \ell +n} \rightarrow \B{R}^{5 \ell +n}$ is defined by $$F \left( \begin{array}{c} u_+ , u_- , v_+ , v_- , w , x \end{array} \right) = \left( \begin{array}{c} D ( u_+ ) v_+ \\ D ( u_- ) v_- \\ 1_\ell - u_+ - w \\ 1_\ell - u_- + w \\ A x - v_+ + v_- - a \\ A^\R{T} w + B^\R{T} B x - B^\R{T} b \end{array} \right)$$

max_itr
The integer scalar max_itr specifies the maximum number of iterations of the algorithm to execute. It must be greater than or equal to zero. Note that if it is zero, the first row of the info return value will still be computed. This can be useful for deciding what is a good value for the argument delta .

A
The argument A is an $\ell \times n$ matrix where $\ell$ can not be zero.

a
The argument a is real column vector of length $\ell$.

B
The argument B is an $m \times n$ matrix where $m$ can not be zero (see l1_linear for the case where $m$ is zero).

b
The argument b is real column vector of length $m$.

delta
The argument delta is a real scalar greater than zero. Convergence after the step at the k-th iteration is defined by info(k+1, 1) <=delta (see First Order Condition below).

x_out
The result x_out contains the approximate solution of the optimization problem at the last iteration; i.e., it corresponds to the value in info(end, 1) described below.

info
If the return value info is not present, the corresponding information is printed on the screen. The result info is a matrix with each row corresponding to an iteration of the algorithm. The row info(k+1, :) corresponds to iteration $k$ of the algorithm. If l1_linear has satisfied the convergence condition if and only if        info(end, 1) <= delta 
First Order Condition
We use $u_+^k$ $u_-^k$ $v_+^k$ $v_-^k$ $w^k$ $x^k$ to denote the corresponding values at iteration $k$ of the algorithm. The value info(k+1, 1) is defined by $$info(k+1, 1) = \left. \left| F \left( \begin{array}{c} u_+ , u_- , v_+ , v_- , w , x \end{array} \right) \right| \right/ \sqrt{5 \ell + n}$$

Relaxation Factor
The value info(k+1, 2) is the relaxation factor used during iteration $k$. As this factor decreases to zero, the solution should correspond to the original problem.

Step Size
The value info(k+1, 3) is the line search step size used during iteration $k$. Values near one indicate good convergence. Small values indicate that the relaxation factor is decreasing to quickly (with the exception that info(1, 3) is always zero).

Example
The file with_l2_ok.m contains an example and test of l1_with_l2. It returns true if the test passes and false otherwise.

Newton Step
The routine l1_newton_l2 determines the Newton step used by l1_with_l2.
Input File: l1_with_l2.m