Academy of Mathematics and Systems Science, CAS
Colloquia & Seminars

Speaker:	Prof. Houduo Qi, University of Southampton
Inviter:
Title:	Classical Multidimensional Scaling: A Subspace Perspective, Over Denoi sing and Outlier Detection
Time & Venue:	2019.7.4 9:00-10:00 N602
Abstract:	The classical Multi-Dimensional Scaling (cMDS) has become a cornerstone for analyzing metric dissimilarity data due to its simplicity in derivation, low computational complexity and its nice interpretation via the principle component analysis. This paper focuses on its capability of denoising and outlier detection. Our new interpretation shows that cMDS always overly denoises a sparsely perturbed data by subtracting a fully dense denoising matrix in a subspace from the given data matrix. This leads us to consider two types of sparsity-driven models: Subspace sparse MDS and Full-space sparse MDS, which respectively uses the $\ell_1$ and $\ell_{1-2}$ regularization to induce sparsity. We then develop fast majorization algorithms for both models and establish their convergence. In particular, we are able to control the sparsity level at every iterate provided that the sparsity control parameter is above a computable threshold. This is a desirable property that has not been enjoyed by any of existing sparse MDS methods. Our numerical experiments on both artificial and real data demonstrates that cMDS with appropriate regularization can perform the tasks of denoising and outlier detection, and inherits the efficiency of cMDS in comparison with several state-of-the-art sparsity-driven MDS methods. Short Bio： Houduo Qi received the BSc in Statistics from Peking University in 1990, MSc and PhD in Operational Research respectively from Qufu Normal University (1993) and Institute of Applied Mathematics, Chinese Academy of Sciences (CAS) (1996). He had done postdoctoral research at the Institute of Computational Mathematics, CAS, Hong Kong Polytechnic University and University of New South Wales. In 2004, he was awarded the prestigious Queen Elizabeth II Fellowship by the Australian Research Council. On the same year, he joined the University of Southampton as a lecturer in Operational Research, rising to Professor and Chair of Optimization. He is mainly interested in Mathematical Optimization, especially in matrix optimization with applications to finance, statistics and signal processing. He currently serves as the area editor (optimization) of Asia-Pacific Journal of Operational Research, and associate editor for Mathematical Programming Computation and Journal of Operations Research Society of China. From 2010, he has been a college member of Engineering and Physical Sciences Research Council, UK. In 2019, he was appointed Turing Fellow at The Alan Turing Institute, UK’s national research institute of data sciences.