|
|
Prev | Next |
\newcommand{\R}[1]{{\rm #1}}
\newcommand{\B}[1]{{\bf #1}}
[x_out] = l1_linear(max_itr, A, b, delta)
[x_out, info] = l1_linear(max_itr, A, b, delta)
1_m \in \B{R}^m
to denote the vector will all elements
equal to one.
Given a vector
w \in \B{R}^m
we use
D(w) \in \B{R}^{m \times m}
,
to denote the corresponding diagonal matrix.
A \in \B{R}^{m \times n}
with rank
n
and
a vector
b \in \B{R}^m
.
The problem we wish to solve is
\[
\begin{array}{lll}
\R{minimize}
& \| A x - b^\R{T} \|_1
& \R{w.r.t} \; x \in \B{R}^n
\end{array}
\]
\[
\begin{array}{lll}
\R{minimize}
& 1_m^\R{T} v_+ + 1_m^\R{T} v_-
& \R{w.r.t.} ( v_+ , v_- , x ) \in \B{R}_+^{2 m} \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}^{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_+
\\
D ( u_- ) v_-
\\
1_m - u_+ - w
\\
1_m - u_- + w
\\
A x - v_+ + v_- - b
\\
A^\R{T} w
\end{array} \right)
\]
m \times n
matrix with rank
n
(hence
n \leq m
).
m
.
k+1, 1) <=delta (see
First Order Condition
below).
(end, 1) described below.
(k+1, :)
corresponds to iteration
k
of the algorithm.
If l1_linear has satisfied the convergence condition if
and only if
(end, 1) <= delta
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 (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 m + n}
\]
(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.
(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 (1, 3) is always zero).
l1_linear.
It returns true if the test passes and false otherwise.
l1_linear.