Prev Next

@(@ \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( Abmuupumvpvmwx )

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