Minimizing the norm via fixpoint iteration

Question

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

Answer 1

$$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.

Answer 2

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.