向量 L1 範數最小化問題？

01-04

Weighted median is the solution to the following cost function:
( $Cost(eta )=sum_{i=1}^{N-1}{W_{i}*|x_{i}-eta|}$ )
其中x是一個N維向量。求一個 $eta$ ，使得Cost( $eta$ )最小。

想問一下，為啥 $eta$ 就是x向量的中值加權濾波呢？

要求 $min_eta J(eta)=sum_{i=1}^n w_i|x_i-eta|quad(w_i ge 0, sum_{i=1}^nw_i=1)$ ，不妨假設 $x_1<cdots<x_n$ 。取subdifferential，則最優點滿足 $0insum_{i=1}^nw_icdotpartial|x_i-eta|$ ，其中（不區分單點集和其中的點，下同）

$partial|x_i-eta|=egin{cases} 1 x_i>eta\<br /> [-1,1] x_i=eta\<br /> -1 x_i <eta end{cases}$ ，

故

$sum_{i=1}^nw_icdotpartial|x_i-eta|=egin{cases} 1 eta>x_n\<br /> sum_{i=k+1}^nw_i-sum_{i=1}^kw_i x_k <eta < x_{k+1}\ left(sum_{i=k+1}^nw_i-sum_{i=1}^{k-1}w_i ight)+[-w_k, w_k] eta=x_k\ -1 eta < x_1 end{cases}$

因此要令 $0insum_{i=1}^nw_icdotpartial|x_i-eta|$ ，需找到 $k$ 使得 $sum_{i=k+1}^nw_i=sum_{i=1}^kw_i=1/2$ （情形2），此時 $x_k <eta < x_{k+1}$ ，可取 $eta = (x_k + x_{k+1})/2$ ；或使得 $sum_{i=1}^{k-1}w_ile 1/2$ 且 $sum_{i=k+1}^{n}w_ile 1/2$ （情形3），此時 $eta=x_k$ 。兩種情況均表明 $eta$ 是 ${x_1,cdots,x_n}$ 的以 ${w_1,cdots,w_n}$ 為權的加權中位數。若 $w_iequiv 1/n$ ，則 $eta$ 退化為 ${x_1,cdots,x_n}$ 的中位數。