Prev Next Index-> contents reference index search external Up-> l1_regular l1_linear l1_newton_line l1_regular-> l1_with_l2 l1_quadratic l1_linear whats_new l1_linear-> linear_ok.m l1_newton_line l1_newton_line-> newton_line_ok.m Headings-> Syntax Notation Purpose A b mu up, um, vp, vm w x dup, dum, dvp, dvm, dw dx Example

$\newcommand{\R}[1]{{\rm #1}}$$\newcommand{\B}[1]{{\bf #1}}$
L1 Objective with L1 Regularization Newton Step

Syntax
[ dup , dum , dvp , dvm , dw , dx ] = l1_newton_line( A, b, mu, up, um, vp, vm, w, x )

Notation
We use $I_m \in \B{R}^{m \times m}$ to denote the identity matrix and $1_m \in \B{R}^m$ to denote the vector will all elements equal to one. Given a vector $u \in \B{R}^m$ we use $D(u) \in \B{R}^{m \times m}$, to denote the corresponding diagonal matrix. If $v$ is also in $\B{R}^m$, $u / v \in \B{R}^m$ denotes element-wise division. The notation $u^{-1}$ is defined by $u^{-1} = 1_m / u$.

Purpose
We are given a matrix $A \in \B{R}^{m \times n}$, a vector $b \in \B{R}^n$ and the scalar $\mu \in \B{R}_+$. The function $F : \B{R}^{5m+n} \rightarrow \B{R}^{5m+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_+ - \mu 1_m \\ D ( u_- ) v_- - \mu 1_m \\ 1_m - u_+ - w \\ 1_m - u_- + w \\ A x - v_+ + v_- - b \\ A^\R{T} w \end{array} \right)$$ Given $( u_+ , u_- , v_+ , v_- , w , x ) \in \B{R}_+^{5m+n}$ this routine solves for $\Delta u_+$, $\Delta u_-$, $\Delta v_+$, $\Delta v_-$, $\Delta w$, $\Delta x$ such that $$F ( u_+ , u_- , v_+ , v_- , w , x ) + F^{(1)} ( u_+ , u_- , v_+ , v_- , w , x ) \left( \begin{array}{c} \Delta u_+ \\ \Delta u_- \\ \Delta v_+ \\ \Delta v_- \\ \Delta w \\ \Delta x \end{array} \right) = \left( \begin{array}{c} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{array} \right)$$

A
The argument A is an $m \times n$ of rank $n$ (hence $n \leq m$).

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

mu
The argument mu is a real scalar. It corresponds to $\mu$ in the discussion above.

up, um, vp, vm
The arguments up, um, vp, and vm are real column vectors of length $m$. They specify the value of $u_+$, $u_-$, $v_+$, and $v_-$ respectively. All the elements of these vectors must be greater than zero.

w
The argument w is a column vector of length $m$.

x
The argument x is a column vector of length $n$.

dup, dum, dvp, dvm, dw
The return values dup, dum, dvp, dvm, and dw are column vectors of length $m$. They correspond respectively to $\Delta u_+$, $\Delta u_-$, $\Delta v_+$, $\Delta v_-$, $\Delta w$, in the discussion above.

dx
The return value dx is a column vectors of length $n$. It corresponds to $\Delta x$, in the discussion above.

Example
The file newton_line_ok.m contains an example and test of l1_newton_line. It returns true if the test passes and false otherwise.
Input File: l1_newton_line.m