0

I have to calculate this in Matlab:

$\operatorname{argmin}_{\lambda} \|a-\lambda b\|_1$,

where $a$ and $b$ vectors in $\mathbb{R}^n$. How can I minimize this in Matlab with a fixpoint iteration? I have to transform it to in equation like $f(\lambda)=\lambda$, but how can I do it with an argmin.

edit: I want to do it with an iteration because there will be another term for regularization. So I need to minimize this in the end:

$\operatorname{argmin}_{\lambda} \|a-\lambda b\|_1+ \beta|\lambda|$,

where $\beta\in [0,\infty)$.

brian
  • 43
  • 1
    Why do you want to used a fixed point iteration? This is a one dimensional convex minimisation that can be solved without iteration. – copper.hat Jun 12 '17 at 20:21
  • It's the first step. The second is with regularization. argmin norm(a-lambda b) + alpha*|lambda| – brian Jun 12 '17 at 20:52

2 Answers2

0

$$f(\lambda)=\left\|a-\lambda b\right\|_1 = \sum_{k=1}^{n} \left| a_k -\lambda b_k \right| \tag{1}$$ and for any $a_k,b_k\in\mathbb{R}$, $\,f_k(\lambda)=\left|a_k-\lambda b_k\right|$ is a non-negative and convex function.
In particular $f(\lambda)$ is a non-negative and convex function as well. We may assume $b_k\neq 0$ without loss of generality, and the minimum of $f$ over $\mathbb{R}$ is attained at a point of the form $\lambda=\frac{a_k}{b_k}$ for some $k\in[1,n]$. The problem can be solved in a single $\textbf{for}$ cycle.

Jack D'Aurizio
  • 353,855
  • Thanks Jack D'Aurizio and @Jean Marie Please look at my first post. It's the first step and I neet one more term. Is it still that easy? – brian Jun 13 '17 at 18:24
0

It means finding the minimum of the function defined by

$$f(\lambda):=|a_1-\lambda b_1|+|a_2-\lambda b_2|+\cdots+|a_n-\lambda b_n|$$

An important remark is that all the $b_i$ can be assumed positive and even >0 because a $b_i$ that would be $0$ does not change the value of $\lambda$ for which a minimum is obtained.

Then sort the quotients $c_i:=\dfrac{a_i}{b_i}$ in ascending order. Let us assume WLOG that it is this order that is taken hereafter.

  • On intervals [$c_i,c_{i+1}$], $f$ coincides with a function obtained by changing expressions |ax+b| into either $ax+b$ or $-ax-b$, thus an affine function which is minimum in $c_i$ or in $c_{i+1}$ (with an inclusive "or": it may happen that the totality of interval ($c_i,c_{i+1}$) is a solution).

  • On interval ($-\infty,c_1$], $f$ coincides with an affine function which tends to $\infty$. Thus its minimum is attained for $\lambda=c_1.$

  • On interval [$c_n,+\infty$), $f$ coincides with an affine function which tends to $\infty$. Thus its minimum is attained for $\lambda=c_n.$

Thus, all you have to do is to compute the values $f(c_i)$ argmin$_{\lambda}$ is the $c_{i_0}$ for which $f(c_i)$ is minimum.

Jean Marie
  • 81,803