本論文應用交替方向乘子法（Alternating Direction of Multiplier Method）於辭典學習（Dictionary Learning）問題上。相較於預先設定的轉換方法，辭典學習為一種從訓練訊號中學習並產生一稀疏（sparse）之辭典的程序。現存解決辭典學習的方法為：（Method of Optimal Direction）及（K-SVD），然而這兩種方法都是計算複雜度即高的方法。而我們使用的交替方向乘子法將原本複雜的問題轉換成簡單的迭代步驟，使得計算複雜度降低，並能降低解決問題的計算時間。模擬結果證明了相較於現存的方法，我們提出的方法能夠成功地在沒有雜訊的環境下更快速且效率地訓練辭典並解決問題。

This thesis investigates the application of the alternating direction method of multipliers (ADMM) to dictionary learning for noise removal problem.
Dictionary learning (DL) is the process of acquiring dictionary that can yield sparse representation of desired signal by learning from training sig-nal, instead of using prespeci ed transformation basis. The prior arts of the dictionary learning algorithms include the method of optimal direction (MOD) and K-SVD. These methods have main drawback in computational complexity.By contrast, the ADMM, which we use to transform the complex problem, into simple update steps, yields lower computational complexity.
We further proposed on inexact ADMM that can reduce the computational time, for scenarios with large dictionary size. Simulation results show that the proposed methods can successfully train the dictionary and yields promising performance for the image noise removal problem. In particular, the pro-posed ADMM method can be around 30 times faster than K-SVD, while inexact ADMM method can further reduce the computational time around 40 %.

[1] M. Elad and M. Aharon, \Image denoising via sparse and redundant representa-
tions over learned dictionaries," IEEE TRANSACTIONS ON IMAGE PROCESS-
ING, VOL. 15, NO. 12, DECEMBER 2006, vol. 15, no. 12, december 2006.
[2] R. Coifman and D. L. Donoho, \Translation invariant de-noising, in in wavelets and
statistics, lecture notes in statistics," In Wavelets and Statistics, Lecture Notes in
Statistics.., pp. 125{150, 1995.
[3] M. Aharaon, \Overcomplete dictionaries for sparse representation of signals," PH.D
Thesis, November 2006.
[4] M. Elad, Sparse and Redundant Representations: From Theory to Applications in
Signal and Image Processing. Springer, 2009.
[5] S. Foucart and H. Rauhut, A Mathematical Introduiction to Compressed Sensing.
Birkhauser, 2013.
[6] S. G. Mallat and Z. Zhang, \Matching pursuits with time-frequency dictionaries,"
IEEE Trans on Signal Processing, vol. 41, no. 12, pp. 3397 { 3415, December 1993.
[7] E. J. Candes and T. Tao, \Decoding by linear programming," IEEE Trans on Infor-
mation Theory, vol. 51, no. 12, pp. 4203 { 4215, Nov. 2005.
[8] M. Aharon, M. Elad, and A. Bruckstein, \K-svd: An algorithm for designing overcom-
plete dictionaries for sparse representation," IEEE TRANSACTIONS ON SIGNAL
PROCESSING, vol. 54, no. 11, pp. 4311 { 4322, November 2006.
[9] S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Echstein, Distributed Optimization and
Statistical Learning via Alternating Direction Method of Multipliers. Foundations
and Trends in Machine Learning, 2011.
[10] T.-H. Chang, M. Hong, and X. Wang, \Multi-agent distributed optimization via
inexact consensus admm," 2014.
[11] Y. C. PATI, R. R. D, and P. s. KRISHNAPRASAD, \Orthogonal matching pur-
suit: Recursive function approximat ion with applications to wavelet decomposition,"
Confrence on Signals, Systems and Computers, 1993. 1993 Conference Record of The
Twenty-Seventh Asilomar, vol. 1, pp. 40{44, November 1993.
[12] H. Mohimani, M. Babaie-Zadeh, and C. Jutten, \Fast sparse representation based
on smoothed l0 norm," Proceedings of 7th International Conference on Independent
Component Analysis and Signal Separation, pp. 389{396, September 2007.
[13] K. Kreutz-Delgado, J. F. Murray, B. D. Rao, K. Engan, T.-W. Lee, and T. J. Se-
jnowski, \Dictionary learning for sparse representation, neural computing," Neural
Computing,2003, vol. 15, no. 2, pp. 394 {396, 2003.
[14] S. Engan, K.and Aase and J. Hakon Husoy, \Method of optimal directions for frame
design," IEEE International Conference on Acoustics, Speech, and Signal Processing,,
1999.
[15] R. Glowinski and A. Marroco, \Sur l'approximation, par elements nis d'ordre un,
et la resolution, par penalisation-dualite d'une classe de problemes de dirichlet non
lineaires," ESAIM: Mathematical Modelling and Numerical Analysis - Modelisation
Mathematique et Analyse Numerique, vol. 9, no. R2, pp. 41{76, 1975.
[16] R. Nishihara, L. Lessard, B. Recht, A. Packard, and M. I. Jordan, \A general analysis
of the convergence of admm," International Conference on Machine Learning, 2015.
[17] R. Chatrand, \A nonconvex admm algorithm for group sparsity with sparse groups,"
IEEE International Confrence on Acoustics, Speech and Signal Processing, pp. 6009
{ 6013, May 28-31 2013.
[18] D. L. S. . and C. Fevotte, \Alternating direction method of multipliers for non-
negative matrix factorization with the beta-divergence," IEEE International Con-
frence on Acoustics, Speech and Signal Processing, pp. 6201 { 6205.
[19] R. Nishihara, L. Lessard, B. Recht, A. Packard, and M. I. Jordan, \A general analysis
of the convergence of admm," arXiv:1502.02009v3, 2015.
[20] A. Rakotomamonjy, \Applying alternating direction method of multipliers for con-
strained dictionary learning," Neurocomputing, vol. 106, pp. 126{136, 2013.
[21] J. M. Duarte-Carvajalino and G. Sapiro, \Learning to sense sparse signals: Simul-
taneous sensing matrix and sparsifying dictionary optimization," IEEE TRANSAC-
TIONS ON SIGNAL PROCESSING, vol. 14, no. 07, pp. 1{5, JULY 2009.
[22] S. P. Kasiviswanathan, H. Wang, A. Banerjee, and P. Melville, \Online l1-dictionary
learning with application to novel document detection," Advances in Neural Infor-
mation Processing Systems, no. 25, 2012.
33