L1ノルムの最小化

質問

最適化問題で、　特異値分解法は最小２乗解を得ることができるので、L2ノルムの最小値に向かって推定が行われていると思うのですが、一般てきにポピュラーなL1ノルムを最小化するアルゴリズムにはどのような方法が使われているのでしょうか。
よろしく御願いします。

回答No.1

ur2c · ベストアンサー

何十年も前のロシア（当時はソ連）の本では、線形計画法でやってました。「距離は非負」という条件のもとで、距離の和を最小化ですから、すなおです。

下の URL のようなのもあります。はっきりおぼえてないし読みなおしてもいないのですけど、以下のような考え方だったかと思います。

絶対値の最小化は原点で微分が使えなくなるから、やりにくい。だから原点で角が丸くなるような関数の列を考える。その極限では角の丸みが取れて、L^1 の最小化になるようにする。そしてその関数列を使って、次々と最小化をする。関数の番号がじゅうぶん大きくなったら、それは L^1 の最小化と同じだと思うことにする。

参考URL：

http://www.scipress.org/journals/jjss/pdf/3101/31010039.pdf