Articles

• ---

  The Handbook of Cluster Analysis

  February 14, 2016
  

  最近在看 The Handbook of Cluster Analysis（聚类分析手册）这本书。这本书不愧为手册，各种聚类方法都很全，作者也都是业内人士。

• ---

  K-means, K-SVD, LC-KSVD and DPL

  August 4, 2015
  

  从 K-means 到 K-SVD¹¹ M. Aharon, M. Elad, and A.M. Bruckstein, “The K-SVD: An Algorithm for Designing of Overcomplete Dictionaries for Sparse Representation”, the IEEE Trans. On Signal Processing, Vol. 54, no. 11, pp. 4311-4322, November 2006. http://www.cs.technion.ac.il/~elad/publications/journals/2004/32_KSVD_IEEE_TSP.pdf²² O. Bryt and M. Elad, Compression of Facial Images Using the K-SVD Algorithm, Journal of Visual Communication and Image Representation, Vol. 19, No. 4, Pages 270-283, May 2008. http://www.cs.technion.ac.il/~elad/publications/journals/2007/FaceCompress_KSVD_JVCIR.pdf³³ R. Rubinstein, T. Peleg and M. Elad, Analysis K-SVD: A Dictionary-Learning Algorithm for the Analysis Sparse Model, IEEE Trans. on Signal Processing, Vol. 61, No. 3, Pages 661-677, March 2013. http://www.cs.technion.ac.il/~elad/publications/journals/2011/Analysis-KSVD-IEEE-TSP.pdf，到 LC-KSVD⁴⁴ Zhuolin Jiang, Zhe Lin, Larry S. Davis. “Label Consistent K-SVD: Learning A Discriminative Dictionary for Recognition”. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(11): 2651-2664. http://www.umiacs.umd.edu/~zhuolin/projectlcksvd.html，到 DPL⁵⁵ Gu, S., Zhang, L., Zuo, W., & Feng, X. (2014). Projective dictionary pair learning for pattern classification. In Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, & K. Q. Weinberger (Eds.), Advances in Neural Information Processing Systems 27 (pp. 793–801). Curran Associates, Inc. http://papers.nips.cc/paper/5600-spectral-clustering-of-graphs-with-the-bethe-hessian。

  ---

  K-means 算法

  任务：通过最近邻寻找能够表达数据样本 ​$\{\mathbf{y}_i\}^N_{i=1}$ 的最优编码本（codebook，既字典参数），既求解如下问题

  ​ $$\min_{\mathbf{C, X}} \left\{ \|\mathbf{Y} - \mathbf{CX}\|^2_F \right\} \text{ subject to } \forall i \text{, } \mathbf{x}_i = \mathbf{e}_k \text{ for some } k$$

• ---

  《非线性最优化基础》学习笔记

  August 2, 2015
  

  《非线性最优化基础》 作者 福嶋雅夫 ¹¹ 《非线性最优化基础》（豆瓣链接：http://book.douban.com/subject/6510671/）。福嶋雅夫（Masao Fukushima），教授，日本南山大学理工学院系统与数学科学系，日本京都大学名誉教授，加拿大滑铁卢大学/比利时那慕尔大学/澳大利亚新南威尔士大学客座教授。主页：http://www.seto.nanzan-u.ac.jp/~fuku/index.html。

  该文为冯象初教授²² 冯象初，教授，西安电子科技大学数学系。主页：http://web.xidian.edu.cn/xcfeng/有关非线性最优化的讲座的笔记。

  主要内容

  理论基础

  1. 凸函数、闭函数
  2. 共轭函数
  3. 鞍点问题
  4. Lagrange 对偶问题
  5. Lagrange 对偶性的推广
  6. Fenchel 对偶性

  算法

  1. Proximal gradient methods
  2. Dual proximal gradient methods
  3. Fast proximal gradient methods
  4. Fast dual proximal gradient methods

• ---

  The Expectation Maximization Algorithm and Finite Mixture Models

  July 24, 2015
  

  期望最大化算法和有限混合模型

  概念主要来自于一次跟师弟的讨论。师弟提到 Expectation Maximization Algorithm (EM 算法) 方面的专家 Prof. Geoffrey John McLachlan 的一篇早期的论文就完全涵盖了多个最新顶级期刊论文的思想。就跟着追到该教授的主页，找到这两本书：Finite Mixture Models (有限混合模型) 和 The EM Algorithm and Extensions (期望最大化算法及其拓展)。

• ---

  Kernel and Kernel: Reproducing Kernel Hilbert Space and Kernel Method

  July 19, 2015
  

  Kernel

  再生核的定义

  Definition. ​$k: \mathcal{X} \times \mathcal{X} \rightarrow \Re$ is a kernel if

  1. 核函数 ​$k$ 对称 isymmetric: ​$k(x,y)=k(y,x)$.

  2. 核函数 ​$k$ 半正定 positive semi-definite

  i.e., ​$\forall x_1, x_2, \ldots , x_n \in \mathcal{X}$, the “Gram Matrix” ​$K$ defined by ​$K_{ij} = k(x_i,x_j)$ is positive semi-definite. (A matrix ​$M \in \Re^{n \times n}$ is positive semi-definite if ​$\forall a \in \Re^n$, ​$a' M a \ge 0$.)

• ---

  Alternating Direction Method of Multipliers (ADMM)

  July 18, 2015
  

  Consider minimizing ​$f({\bf x}) + g({\bf y})$ subject to affine constraints ​${\bf Ax} + {\bf By} = {\bf c}$

  The augmented Lagrangian

  ​ $$\mathcal{L}_\rho({\bf x}, {\bf y}, {\bf \lambda}) = f({\bf x}) + g({\bf y}) + \langle {\bf \lambda}, {\bf Ax} + {\bf By} - {\bf c} \rangle + \frac{\rho}{2} \| {\bf Ax} + {\bf By} - {\bf c} \|^2_2$$

• ---

  Augmented Lagrangian Method

  July 17, 2015
  

  Consider minimizing:

  ​$f({\bf x})$ subject to equality constraints ​$g_i({\bf x}) = 0$ for ​$i=1, \ldots ,q$

  Inequality constraints are ignored for simplicity

  Assume ​$f$ and ​$g_i$ are smooth for simplicity

  At a constrained minimum, the Lagrange multiplier condition

  ​ $${\bf 0}=\nabla f({\bf x})+\sum^q_{i=1}\lambda_i\nabla g_i({\bf x})$$

  holds provided ​$\nabla g_i({\bf x})$ are linearly independent

• ---

  Introduction to Nonlinear Optimization

  July 16, 2015
  

  昨天晚上到今天，看完了一本之前一直看不完的书 《Introduction to Nonlinear Optimization》¹¹ 《Introduction to Nonlinear Optimization》 at 豆瓣: http://book.douban.com/subject/26551626/ and at Amazon: http://www.amazon.com/Introduction-Nonlinear-Optimization-Algorithms-Applications/dp/1611973643/ by Amir Beck ²² Amir Beck is an associate professor at The Technion—Israel Institute of Technology： http://iew3.technion.ac.il/Home/Users/becka.html。澄清了一些过去曾经误解的概念。MOS-SIAM Series on Optimization³³ MOS-SIAM Series on Optimization: http://bookstore.siam.org/mos-siam-series-on-optimization/ 一系列优化的书都不错。连着借了三本，希望以后都能好好读完。现在这本非线性优化暂时只是翻完了，习题都没做，感觉习题也都挺有用的。

• ---

  稀疏编码的优化问题

  May 21, 2015
  

  稀疏编码问题： ​$\arg\min_x f(x)\left\|y-Ax\right\|^2+ \lambda\|x\|_1$

  • 用 alternating minimization (ADM)
  • Primal-dual 算法
  • Soft threshold

• ---

  几个基本优化问题

  May 21, 2015
  

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

  Question 1

  least entropy & error correction