CVX|凸优化（ADMM(Alternating Direction Method of Multipliers)交替方向乘子算法系列之六： L1-Norm Problems）
最近开始对凸优化(convex optimization)中的ADMM(Alternating Direction Method of Multipliers)交替方向乘子算法开始感兴趣，接下来我会写一系列关于ADMM(Alternating Direction Method of Multipliers)交替方向乘子算法的内容。
凸优化：ADMM(Alternating Direction Method of Multipliers)交替方向乘子算法系列之六： L1-Norm Problems
本文地址：http://blog.csdn.net/shanglianlm/article/details/46805675
6- L1范式问题（L1-Norm Problems） ADMM 自然地将飞光滑的 L1 项 与光滑的损失项分离开来，使得计算更有效。这一部分我们主要考虑非并行的 L1-Norm 问题。关于最近的 L1 算法的综述可以参考 [173]
[173] A. Y. Yang, A. Ganesh, Z. Zhou, S. S. Sastry, and Y. Ma, “A Review of Fast l1-Minimization Algorithms for Robust Face Recognition,” arXiv:1007.3753, 2010.
6-1 最小绝对偏差（Least Absolute Deviations ） 最小化 ||Ax?b||1替代||Ax?b||22
当数据包含较大的离群点时，Least Absolute Deviations（LAD） 通常比 least squares fitting（LSF） 提供一个更鲁棒的拟合 （Least absolute deviations provides a more robust fit than least squares when the data contains large outliers）。写成 ADMM 形式，
文章图片
其中f=0和g=||?||1 , 假设ATA可逆， 有
文章图片
6-1-1 Huber 拟合（Huber Fitting）
Huber Fitting 位于 least squares 和 least absolute deviations 之间，
文章图片
其中 Huber penalty functionghub：
文章图片
因此有，
文章图片
x-update 和 u-update 和 Least absolute deviations 的一样。
6-2 基追踪（Basis Pursuit） Basis Pursuit 是一个 等式约束的 L1 最小化问题
文章图片
[24] 是关于 Basis Pursuit 的一个综述。
写成 ADMM 形式
文章图片
其中 f 是
文章图片
的指示函数。
因此有
文章图片
其中 Π 是
文章图片
上的映射。
x-update 展开为
文章图片
最近提出的 Bregman iterative methods 解决类似 Basis Pursuit 的问题很有效。
For basis pursuit and related problems, Bregman iterative regularization [176] is equivalent to the method of multipliers, and the split Bregman method [88] is equivalent to ADMM [68].[24] A. M. Bruckstein, D. L. Donoho, and M. Elad, “From sparse solutions of systems of equations to sparse modeling of signals and images,” SIAM Review, vol. 51, no. 1, pp. 34–81, 2009.
[176] W. Yin, S. Osher, D. Goldfarb, and J. Darbon, “Bregman iterative algorithms for l1-minimization with applications to compressed sensing,” SIAM Journal on Imaging Sciences, vol. 1, no. 1, pp. 143–168, 2008.
[88] T. Goldstein and S. Osher, “The split Bregman method for l1 regularized problems,” SIAM Journal on Imaging Sciences, vol. 2, no. 2, pp. 323–343, 2009.
[68] E. Esser, “Applications of Lagrangian-based alternating direction methods and connections to split Bregman,” CAM report, vol. 9, p. 31, 2009.
6-3 广义 L1正则化损失最小化（General L1 Regularized Loss Minimization） 考虑广义的问题
文章图片
其中 l 是任意的凸代价函数。
写成 ADMM 形式
文章图片
其中
文章图片
有
文章图片
In general, we can interpret ADMM for L1 regularized loss minimization as reducing it to solving a sequence of L2 (squared) regularized loss minimization problems.6-4 Lasso（Lasso) lasso [156] 是 （6.1）的一个特例，也叫 L1 regularized linear regression。
文章图片
写成 ADMM 形式
文章图片
其中
文章图片
有
文章图片
The x-update is essentially a ridge regression (i.e., quadratically regularized least squares) computation, so ADMM can be interpreted as a method for solving the lasso problem by iteratively carrying out ridge regression.6-4-1 广义Lasso（Generalized Lasso）
进一步一般化
文章图片
其中 F 是一个任意的线性变换。
一个特殊的例子是当F∈R(n?1)×n是差异矩阵
文章图片
和 A =I 时，
文章图片
写成 ADMM 形式
文章图片
有
文章图片
6-4-2 组 Lasso（Group Lasso）
文章图片
文章图片
文章图片
文章图片
6-5 稀疏逆协方差选择（Sparse Inverse Covariance Selection） 【CVX|凸优化（ADMM(Alternating Direction Method of Multipliers)交替方向乘子算法系列之六： L1-Norm Problems）】参考或延伸材料：
[1] Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers
[2] 凸优化讲义
[3] A Note on the Alternating Direction Method of Multipliers
