Prev | Next |

@(@ \newcommand{\R}[1]{{\rm #1}} @)@@(@ \newcommand{\B}[1]{{\bf #1}} @)@

`[`

`] = l1_with_l2(`

`, `

`, `

`, `

`, `

`, `

`)`

`[`

`, `

`] = l1_with_l2(`

`, `

`, `

`, `

`, `

`, `

`)`

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.

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} @]@

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 @)@.

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) @]@

The integer scalar

The argument

The argument

The argument

The argument

The argument

*k*

-th iteration is defined by

`k`

`delta`

(see
First Order Condition
below).
The result

`(end, 1)`

described below.
If the return value

`(`

`+1, :)`

corresponds to iteration @(@
k
@)@ of the algorithm.
If `l1_linear`

has satisfied the convergence condition if
and only if

`(end, 1) <= `

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

`(`

`+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}
@]@
The value

`(`

`+1, 2)`

is the relaxation factor
used during iteration @(@
k
@)@.
As this factor decreases to zero, the solution should correspond to
the original problem.
The value

`(`

`+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

`(1, 3)`

is always zero).
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.
The routine l1_newton_l2 determines the Newton step used by

`l1_with_l2`

.
Input File: l1_with_l2.m