Home > Program > Tutorials > AM-02

ICPR2012 Tutorials AM-02
Half-quadratic Optimization for Sparsity Estimation and Robust Learning in Pattern Recognition

Ran He*, Wei-Shi Zheng**, and Wang Liang*
*National Laboratory of Pattern Recognition, Institute of Automation, Chinese Academy of Sciences (CAISA), China,
**Sun Yat-sen University, China



In the past decade, half-quadratic (HQ) optimization has become increasingly popular for solving computational problems in sparsity estimation and robust learning, which is important for computer vision, image processing, and pattern recognition. In this half-day tutorial, we present basic theory and techniques of HQ optimization, as well as its applications in compressed sensing and pattern recognition. In addition, from the HQ perspective, we also give a general framework of the current developments in compressed sensing, including L1-minimization, robust sparse representation, low-rank matrix recovery and structured sparsity. Most of these developments can be simplified to the additive and multiplicative forms of HQ. Such a HQ perspective will help attendees to better understand the intrinsic relationship between several state-of-the-art methods in compressed sensing. It also motivates the development of HQ optimization to solve pattern recognition problems in the near future.

This tutorial only requires minimum knowledge of convex optimization and some basic knowledge in graduate-level pattern recognition. It includes four parts. First, we introduce the basic concept of HQ optimization (the additive form and the multiplicative form). Second, we introduce the applications of HQ in image denoising, subspace learning and feature extraction. Third, we focus on a general HQ view for L1 minimization and robust sparse representation. Lastly, we introduce recent advances in low rank matrix recovery and structured sparsity from the HQ viewpoint. This HQ analysis gives a general framework to unify the methods based on L21-norm, quasi-norm and other HQ norms, which have recently been used in low rank matrix recovery and structured sparsity.


Course description

  1. Introduction and Overview of the Tutorial (10 minutes)
  2. Basic Theory of Half-quadratic Optimization (35 minutes)
    1. Moreau Proximity Operators (MPO) and Soft-thresholding
    2. Half-quadratic Optimization
    3. Robust Statistics and Information Theoretic Learning
  3. HQ Optimization in Robust Learning (45 minutes)
    1. HQ Optimization in Image Denoising
    2. HQ Optimization in Subspace Learning
    3. HQ Optimization in Feature Extraction
  4. HQ Optimization in Sparsity Estimation (35 minutes)
    1. A Brief Review of HQ Optimization
    2. L1 Minimization and Robust Sparse Representation
    3. HQ framework for Robust Sparse Representation
  5. HQ Optimization in Recent Advances (45 minutes)
    1. Low-rank Matrix Recovery and Robust PCA
    2. HQ framework for Low-rank Matrix Recovery
    3. HQ framework for Structured Sparsity
  6. Open questions and discussion (10 minutes)


Relevant References:

Among the vast literature on convex optimization and half-quadratic optimization, the following are some selected publications. The list is preliminary and subject to modification:

  1. S. Boyd and L. Vandenberghe. Convex optimization. Cambridge University Press, 2004.
  2. Jose C. Principe. Information Theoretic Learning: Renyi's Entropy and Kernel Perspectives. Springer, New York, USA, 2010.
  3. M. Nikolova and M. K. NG. Analysis of half-quadratic minimization methods for signal and image recovery. SIAM Journal on Scientific computing, 27(3):937–966, 2005.
  4. Ran He, Tieniu Tan, Liang Wang and Wei-Shi Zheng. L21 Regularized Correntropy for Robust Feature Selection. In: IEEE CVPR, 2012.
  5. Wei-Shi Zheng, Shaogang Gong, and Tao Xiang. Transfer Re-identification: From Person to Set-based Verification. In: IEEE CVPR, 2012.
  6. Ran He, Wei-Shi Zheng, Bao-Gang Hu, Xiang-Wei Kong. Nonnegative sparse coding for discriminative semi-supervised learning. In: IEEE CVPR, 2011.
  7. Ran He, Zhenan Sun, Tieniu Tan, Wei-Shi Zheng. Recovery of corrupted low-rank matrices via half-quadratic based nonconvex minimization. In: IEEE CVPR, 2011:2889-2896.
  8. Wei-Shi Zheng, Shaogang Gong, and Tao Xiang. Person Re-identification by Probabilistic Relative Distance Comparison. In: IEEE CVPR, 2011.
  9. Ran He, Wei-Shi Zheng, and Bao-Gang Hu. Maximum Correntropy Criterion for Robust Face Recognition. IEEE Trans. on Pattern Analysis and Machine Intelligence, 33(8): 1561-1576, 2011.
  10. Wei-Shi Zheng, Shaogang Gong, and Tao Xiang. Quantifying and Transferring Contextual Information in Object Detection. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2011, accepted, (Published online: 18 August 2011; DOI: 10.1109/TPAMI.2011.164).
  11. Wei-Shi Zheng, JianHuang Lai, Shengcai Liao, and Ran He. Extracting Non-negative Basis Images Using Pixel Dispersion Penalty. Pattern Recognition, 45(8): 2912-2926, 2012.
  12. Ran He, Wei-Shi Zheng, Bao-Gang Hu, and Xiang-Wei Kong. A Regularized Correntropy Framework for Robust Pattern Recognition. Neural Computation (MIT), 23(8): 2074-2100, 2011.
  13. Ran He, Bao-Gang Hu, Wei-Shi Zheng, and X.-W. Kong. Robust Principal Component Analysis based on maximum Correntropy criterion. IEEE Trans. on Image Processing, 20(6): 1840-1494, 2011.
  14. Wei-Shi Zheng, Stan Z. Li, JianHuang Lai, and Shengcai Liao, “On Constrained Sparse Matrix Factorization,” In Proc. IEEE International Conference on Computer Vision (ICCV), Brazil, 2007.


About Lecturer:

Ran He received the B.E. degree and M.S. degree in Computer Science from Dalian University of Technology, and Ph.D. degree in Pattern Recognition and Intelligent Systems from Institute of Automation, Chinese Academy of Sciences in 2001, 2004 and 2009, respectively. Since September 2010, Dr. He has joined NLPR where he is currently Associate Professor. He is currently a member of IEEE (Institute of Electrical and Electronics Engineers), and serves as an associate editor of Neurocomputing (Elsevier), area Chair of ICPR 2012, the member of the council of the Beijing Society of Image and Graphics, and the program committee of several conferences.
His research interests focus on information theoretic learning, pattern recognition, and computer vision. He has published over 40 journal and conference papers in these fields, and has widely published at highly ranked international journals, such as IEEE Trans. on Pattern Analysis and Machine Intelligence (TPAMI), IEEE Trans. on Image Processing, IEEE Trans. on Knowledge and Data Engineering, IEEE Trans. on Neural Networks and Learning System, Neural Computation (MIT) and Pattern Recognition (Elsevier), and leading international conferences, such as Computer Vision and Pattern Recognition (CVPR) and the AAAI Conference on Artificial Intelligence (AAAI).

Wei-Shi Zheng has doctoral degree in Applied Mathematics and has joined Sun Yat-sen University as a faculty under the one-hundred-people program of Sun Yat-sen in 2011. His research area is in computer vision, pattern recognition and related machine learning. He is currently focusing on object/person association, face recognition, and transfer learning. He has published 47 papers widely in top/leading journals/conferences in computer vision and machine learning, including IEEE Trans. on Pattern Analysis and Machine Intelligence (PAMI), IEEE Trans. on Neural Networks, IEEE Trans. on Image Processing, Pattern Recognition, IEEE TSMC-B, Neural Computation, IEEE TKDE, ICCV, CVPR and AAAI. Among the publications, about 13 papers are in top/leading journals and 9 papers are in top conferences in computer vision. He has served as a regular reviewer for several top/leading journals (IEEE TPAMI, IEEE TNN, IEEE TCSVT, PR) and as a program committee member of several international conferences.


Liang Wang received the PhD degree in Pattern Recognition and Intelligent System from the National Laboratory of Pattern Recognition (NLPR), Institute of Automation, Chinese Academy of Sciences (CAS), China, in 2004. After graduation, he has worked as a Research Assistant at the Imperial College London, United Kingdom and Monash University, Australia, and a Research Fellow at the University of Melbourne, Australia, respectively. Before he returned back to China, he was a Lecturer with the Department of Computer Science, University of Bath, United Kingdom. Currently, he is a Professor of Hundred Talents Program of CAS at the Institute of Automation, Chinese Academy of Sciences, P. R. China.
His major research interests include machine learning, pattern recognition, computer vision, multimedia processing, and data mining. He has widely published at highly-ranked international journals such as IEEE TPAMI, IEEE TIP, IEEE TKDE, IEEE TCSVT, IEEE TSMC, CVIU, and PR, and leading international conferences such as CVPR, ICCV and ICDM. He has obtained several honors and awards such as the Special Prize of the Presidential Scholarship of CAS and the Research Commendation from University of Melbourne in recognition of Excellent Research. He is currently a Senior Member of IEEE (Institute of Electrical and Electronics Engineers), as well as a member of IEEE Computer Society, IEEE Communications Society and BMVA (British Machine Vision Association).
He is serving with more than 20 major international journals and more than 40 major international conferences and workshops. He is an associate editor of IEEE Transactions on Systems, Man and Cybernetics – Part B, International Journal of Image and Graphics (WorldSci), International Journal of Signal Processing (Elsevier), Neurocomputing (Elsevier), and International Journal of Cognitive Biometrics (Inderscience). He is a leading guest editor of 3 special issues appearing in PRL (Pattern Recognition Letters), IJPRAI (International Journal of Pattern Recognition and Artificial Intelligence) and IEEE TSMC-B, as well as a co-editor of 5 edited books. He has also co-chaired 8 international workshops.


> Back to List of Tutorials


Archive: Call for Tutorial Proposals



(C) 2010-2012 ICPR2012 Organizing Committee. All rights reserved.