Prev Next

@(@ \newcommand{\R}[1]{{\rm #1}} @)@@(@ \newcommand{\B}[1]{{\bf #1}} @)@
Newton Step for Combined L1-L2 Fitting

Syntax
dup , dum , dvp , dvm , dw , dx ] = l1_newton_l2( AaBbmuupumvpvmwx )

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

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} @)@, a vector @(@ b \in \B{R}^m @)@, and scalar @(@ \mu \in \B{R}_+ @)@. The function @(@ 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_+ - \mu 1_\ell \\ D ( u_- ) v_- - \mu 1_\ell \\ 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) @]@ 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) @]@

Restriction
The matrix @(@ A^\R{T} D( v_+ / u_+ + v_- / u_- ) A + B^\R{T} B @)@ must have rank @(@ n @)@

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

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 @(@ \ell @)@. 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_l2_ok.m contains an example and test of l1_newton_l2. It returns true if the test passes and false otherwise.
Input File: l1_newton_l2.m