几个基本优化问题

May 21, 2015

可以用 ALM¹¹ Augmented Lagrange Multiplier 增广拉格朗日乘子法, LP²² Linear Programming 线性规划 和 IRLS ³³ Iteratively Reweighted Least Squares 求解的四种基本优化问题

Question 1

least entropy & error correction

• ​$\arg \min \|x\|_1 + \|e\|_1$ subj. to ​$y=Ax+e$
• 标准 linear programming
• 鲁棒的 SRC⁴⁴ 参见 http://research.microsoft.com/pubs/132810/PAMI-Face.pdf and Face Recognition via Sparse Representation。使用单位矩阵作为遮挡字典，用标准形式求解。

Question 2

least energy & error correction

• ​$\arg\min \|x\|_2 + \|e\|_1$ subj. to ​$y=Ax+e$
• 鲁棒的 CRC

Question 3

sparse regression with noise - lasso

• ​$\arg\min \|x\|_1 + \|e\|_2$ subj. to ​$y=Ax+e$
• 标准 lasso 问题
• 标准的 SRC

Question 4

least energy with noise

• ​$\arg\min \|x\|_2 + \|e\|_2$ subj. to ​$y=Ax+e$
• 极小最小二乘解，可求广义逆。
• CRC，用二范数约束表示系数，有解析解。

弗罗贝尼乌斯范数 Frobenius norm

​ $$\| \mathbf{A} \|_F = \sqrt{\sum^m_{i=1} \sum^n_{j=1} \mid a_{ij} \mid^2} = \sqrt{trace(\mathbf{A}^* \mathbf{A})} = \sqrt{\sum^{\min\{m,n\}}_{i=1}\sigma^2_i}$$