American Institute of Mathematical Sciences

Advanced
April  2016, 12(2): 543-563. doi: 10.3934/jimo.2016.12.543

Regularized multidimensional scaling with radial basis functions

Sohana Jahan 1, and  Hou-Duo Qi 1,

1. 

School of Mathematics, University of Southampton, United Kingdom, United Kingdom

Received  August 2014 Revised  January 2015 Published  June 2015

The classical Multi-Dimensional Scaling (MDS) is an important method for data dimension reduction. Nonlinear variants have been developed to improve its performance. One of them is the MDS with Radial Basis Functions (RBF). A key issue that has not been well addressed in MDS-RBF is the effective selection of its centers. This paper treats this selection problem as a multi-task learning problem, which leads us to employ the $(2,1)$-norm to regularize the original MDS-RBF objective function. We then study its two reformulations: Diagonal and spectral reformulations. Both can be effectively solved through an iterative block-majorization method. Numerical experiments show that the regularized models can improve the original model significantly.
Keywords: support vector machine., regularization, radial basis function, Multi-dimensional scaling, iterative majorization.
Mathematics Subject Classification: Primary: 62H30, 68T10; Secondary: 90C2.
Citation: Sohana Jahan, Hou-Duo Qi. Regularized multidimensional scaling with radial basis functions. Journal of Industrial & Management Optimization, 2016, 12 (2) : 543-563. doi: 10.3934/jimo.2016.12.543
References:
[1]

A. Argyriou, T. Evgeniou and M. Pontil, Multi-task Feature Learning,, in Advances in Neural Information Processing Systems (eds. B. Schoelkopf, (2007).   Google Scholar

[2]

A. Argyriou, T. Evgeniou and M. Pontil, Convex Multi-task Feature Learning,, Machine Learning, 73 (2008), 243.  doi: 10.2139/ssrn.1031158.  Google Scholar

[3]

J. Bénasséni, Partial additive constant,, J. Statist. Comput. Simul., 49 (1994), 179.   Google Scholar

[4]

I. Borg and P. J. F. Groenen, Modern Multidimensional Scaling. Theory and Applications,, $2^{nd}$ edition, (2005).   Google Scholar

[5]

F. Cailliez, The analytical solution of the additive constant problem,, Psychometrika, 48 (1983), 305.  doi: 10.1007/BF02294026.  Google Scholar

[6]

H. G. Chew and C. C. Lim, On regularisation parameter transformation of support vector machines,, Journal of Industrial and Management Optimization, 5 (2009), 403.  doi: 10.3934/jimo.2009.5.403.  Google Scholar

[7]

L. G. Cooper, A new solution to the additive constant problem in metric and multidimensional scaling,, Psychometrika, 37 (1972), 311.   Google Scholar

[8]

T. F. Cox and M. A. Cox, Multidimensional Scaling,, $2^{nd}$ edition, (2002).  doi: 10.1007/978-3-540-33037-0_14.  Google Scholar

[9]

J. de Leeuw, Applications of convex analysis to multidimensional scaling,, in Recent Developments in Statistics (eds. J. Barra, (): 133.   Google Scholar

[10]

J. de Leeuw, Block relaxation algorithms in statistics,, in Information Systems and Data Analysis (eds. Bock, (1994), 308.  doi: 10.1007/978-3-642-46808-7_28.  Google Scholar

[11]

W. Glunt, T. L. Hayden, S. Hong and J. Wells, An alternating projection algorithm for computing the nearest Euclidean distance matrix,, SIAM J. Matrix Anal. Appl., 11 (1990), 589.  doi: 10.1137/0611042.  Google Scholar

[12]

W. Glunt, T. L. Hayden and R. Raydan, Molecular conformations from distance matrices,, J. Computational Chemistry, 14 (1993), 114.  doi: 10.1002/jcc.540140115.  Google Scholar

[13]

J. C. Gower, Some distance properties of latent rootand vector methods in multivariate analysis,, Biometrika, 53 (1966), 315.  doi: 10.1093/biomet/53.3-4.325.  Google Scholar

[14]

Y. Hao and F. Meng, A new method on gene selection for tissue classification,, Journal of Industrial and Management Optimization, 3 (2007), 739.  doi: 10.3934/jimo.2007.3.739.  Google Scholar

[15]

J. Kruskal, Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis,, Psychometrika, 29 (1964), 1.  doi: 10.1007/BF02289565.  Google Scholar

[16]

K. V. Mardia, J. T. Kent and J. M. Bibby, Multivariate Analysis,, $10^{th}$ printing, (1995).   Google Scholar

[17]

S. J. Messick and R. P Abelson, The additive constant problem in multidimensional scaling,, Psychometrika, 21 (1956), 1.   Google Scholar

[18]

E. Pękalaska and R. P. W. Duin, The Dissimilarity Representation for Pattern Recognition: Foundations and Application,, Series in Machine Perception Artificial Intelligence 64, (2005).   Google Scholar

[19]

H.-D. Qi, A semismooth Newton method for the nearest Euclidean distance matrix problem,, SIAM Journal Matrix Analysis and Applications, 34 (2013), 67.  doi: 10.1137/110849523.  Google Scholar

[20]

H.-D. Qi and N. Xiu, A convex quadratic semidefinite programming approach to the partial additive constant problem in multidimensional scaling,, Journal of Statistical Computation and Simulation, 82 (2012), 1317.  doi: 10.1080/00949655.2011.579970.  Google Scholar

[21]

H.-D. Qi, N. H. Xiu and X. M. Yuan, A Lagrangian dual approach to the single source localization problem,, IEEE Transactions on Signal Processing, 61 (2013), 3815.  doi: 10.1109/TSP.2013.2264814.  Google Scholar

[22]

H.-D. Qi and X. M. Yuan, Computing the nearest Euclidean distance matrix with low embedding dimensions,, Mathematical Programming, (): 10107.  doi: 10.1007/s10107-013-0726-0.  Google Scholar

[23]

K. Schittkowski, Optimal parameter selection in support vector machines,, Journal of Industrial and Management Optimization, 1 (2005), 465.  doi: 10.3934/jimo.2005.1.465.  Google Scholar

[24]

I. J. Schoenberg, Remarks to Maurice Fréchet's article "Sur la définition axiomatque d'une classe d'espaces vectoriels distanciés applicbles vectoriellement sur l'espace de Hilbet'',, Ann. Math., 36 (1935), 724.  doi: 10.2307/1968654.  Google Scholar

[25]

S. Theodoridis and K. Koutroumbas, Pattern Recognition,, Elsevier Inc., (2009).  doi: 10.1016/B0-12-227240-4/00132-5.  Google Scholar

[26]

S. Theodoridis and K. Koutroumbas, An Introduction to Pattern Recognition, A MATLAB approach,, Elsevier Inc., (2010).   Google Scholar

[27]

W. S. Torgerson, Theory and Methods for Scaling,, Wiley, (1958).   Google Scholar

[28]

A. R. Webb, Multidimensional Scaling by iterative majorization using radial basis functions,, Pattern Recognition, 28 (1995), 753.  doi: 10.1016/0031-3203(94)00135-9.  Google Scholar

[29]

A. R. Webb, Nonlinear feature extraction with radial basis functions using a weighted multidimensional scaling stress measure,, Pattern Recognition, 4 (1996), 635.  doi: 10.1109/ICPR.1996.547642.  Google Scholar

[30]

A. R. Webb, An approach to nonlinear principal component analysis using radially-symmetric kernel functions,, Statistics and Computing, 6 (1996), 159.   Google Scholar

[31]

G. Young and A. S. Householder, Discussion of a set of points in terms of their mutual distances,, Psychometrika, 3 (1938), 19.  doi: 10.1007/BF02287916.  Google Scholar

[32]

Y. Yuan, W. Fan and D. Pu, Spline function smooth support vector machine for classification,, Journal of Industrial and Management Optimization, 3 (2007), 529.  doi: 10.3934/jimo.2007.3.529.  Google Scholar

show all references

References:
[1]

A. Argyriou, T. Evgeniou and M. Pontil, Multi-task Feature Learning,, in Advances in Neural Information Processing Systems (eds. B. Schoelkopf, (2007).   Google Scholar

[2]

A. Argyriou, T. Evgeniou and M. Pontil, Convex Multi-task Feature Learning,, Machine Learning, 73 (2008), 243.  doi: 10.2139/ssrn.1031158.  Google Scholar

[3]

J. Bénasséni, Partial additive constant,, J. Statist. Comput. Simul., 49 (1994), 179.   Google Scholar

[4]

I. Borg and P. J. F. Groenen, Modern Multidimensional Scaling. Theory and Applications,, $2^{nd}$ edition, (2005).   Google Scholar

[5]

F. Cailliez, The analytical solution of the additive constant problem,, Psychometrika, 48 (1983), 305.  doi: 10.1007/BF02294026.  Google Scholar

[6]

H. G. Chew and C. C. Lim, On regularisation parameter transformation of support vector machines,, Journal of Industrial and Management Optimization, 5 (2009), 403.  doi: 10.3934/jimo.2009.5.403.  Google Scholar

[7]

L. G. Cooper, A new solution to the additive constant problem in metric and multidimensional scaling,, Psychometrika, 37 (1972), 311.   Google Scholar

[8]

T. F. Cox and M. A. Cox, Multidimensional Scaling,, $2^{nd}$ edition, (2002).  doi: 10.1007/978-3-540-33037-0_14.  Google Scholar

[9]

J. de Leeuw, Applications of convex analysis to multidimensional scaling,, in Recent Developments in Statistics (eds. J. Barra, (): 133.   Google Scholar

[10]

J. de Leeuw, Block relaxation algorithms in statistics,, in Information Systems and Data Analysis (eds. Bock, (1994), 308.  doi: 10.1007/978-3-642-46808-7_28.  Google Scholar

[11]

W. Glunt, T. L. Hayden, S. Hong and J. Wells, An alternating projection algorithm for computing the nearest Euclidean distance matrix,, SIAM J. Matrix Anal. Appl., 11 (1990), 589.  doi: 10.1137/0611042.  Google Scholar

[12]

W. Glunt, T. L. Hayden and R. Raydan, Molecular conformations from distance matrices,, J. Computational Chemistry, 14 (1993), 114.  doi: 10.1002/jcc.540140115.  Google Scholar

[13]

J. C. Gower, Some distance properties of latent rootand vector methods in multivariate analysis,, Biometrika, 53 (1966), 315.  doi: 10.1093/biomet/53.3-4.325.  Google Scholar

[14]

Y. Hao and F. Meng, A new method on gene selection for tissue classification,, Journal of Industrial and Management Optimization, 3 (2007), 739.  doi: 10.3934/jimo.2007.3.739.  Google Scholar

[15]

J. Kruskal, Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis,, Psychometrika, 29 (1964), 1.  doi: 10.1007/BF02289565.  Google Scholar

[16]

K. V. Mardia, J. T. Kent and J. M. Bibby, Multivariate Analysis,, $10^{th}$ printing, (1995).   Google Scholar

[17]

S. J. Messick and R. P Abelson, The additive constant problem in multidimensional scaling,, Psychometrika, 21 (1956), 1.   Google Scholar

[18]

E. Pękalaska and R. P. W. Duin, The Dissimilarity Representation for Pattern Recognition: Foundations and Application,, Series in Machine Perception Artificial Intelligence 64, (2005).   Google Scholar

[19]

H.-D. Qi, A semismooth Newton method for the nearest Euclidean distance matrix problem,, SIAM Journal Matrix Analysis and Applications, 34 (2013), 67.  doi: 10.1137/110849523.  Google Scholar

[20]

H.-D. Qi and N. Xiu, A convex quadratic semidefinite programming approach to the partial additive constant problem in multidimensional scaling,, Journal of Statistical Computation and Simulation, 82 (2012), 1317.  doi: 10.1080/00949655.2011.579970.  Google Scholar

[21]

H.-D. Qi, N. H. Xiu and X. M. Yuan, A Lagrangian dual approach to the single source localization problem,, IEEE Transactions on Signal Processing, 61 (2013), 3815.  doi: 10.1109/TSP.2013.2264814.  Google Scholar

[22]

H.-D. Qi and X. M. Yuan, Computing the nearest Euclidean distance matrix with low embedding dimensions,, Mathematical Programming, (): 10107.  doi: 10.1007/s10107-013-0726-0.  Google Scholar

[23]

K. Schittkowski, Optimal parameter selection in support vector machines,, Journal of Industrial and Management Optimization, 1 (2005), 465.  doi: 10.3934/jimo.2005.1.465.  Google Scholar

[24]

I. J. Schoenberg, Remarks to Maurice Fréchet's article "Sur la définition axiomatque d'une classe d'espaces vectoriels distanciés applicbles vectoriellement sur l'espace de Hilbet'',, Ann. Math., 36 (1935), 724.  doi: 10.2307/1968654.  Google Scholar

[25]

S. Theodoridis and K. Koutroumbas, Pattern Recognition,, Elsevier Inc., (2009).  doi: 10.1016/B0-12-227240-4/00132-5.  Google Scholar

[26]

S. Theodoridis and K. Koutroumbas, An Introduction to Pattern Recognition, A MATLAB approach,, Elsevier Inc., (2010).   Google Scholar

[27]

W. S. Torgerson, Theory and Methods for Scaling,, Wiley, (1958).   Google Scholar

[28]

A. R. Webb, Multidimensional Scaling by iterative majorization using radial basis functions,, Pattern Recognition, 28 (1995), 753.  doi: 10.1016/0031-3203(94)00135-9.  Google Scholar

[29]

A. R. Webb, Nonlinear feature extraction with radial basis functions using a weighted multidimensional scaling stress measure,, Pattern Recognition, 4 (1996), 635.  doi: 10.1109/ICPR.1996.547642.  Google Scholar

[30]

A. R. Webb, An approach to nonlinear principal component analysis using radially-symmetric kernel functions,, Statistics and Computing, 6 (1996), 159.   Google Scholar

[31]

G. Young and A. S. Householder, Discussion of a set of points in terms of their mutual distances,, Psychometrika, 3 (1938), 19.  doi: 10.1007/BF02287916.  Google Scholar

[32]

Y. Yuan, W. Fan and D. Pu, Spline function smooth support vector machine for classification,, Journal of Industrial and Management Optimization, 3 (2007), 529.  doi: 10.3934/jimo.2007.3.529.  Google Scholar

[1]

Dmitry Treschev. A locally integrable multi-dimensional billiard system. Discrete & Continuous Dynamical Systems - A, 2017, 37 (10) : 5271-5284. doi: 10.3934/dcds.2017228
[2]

Yves Dumont, Frederic Chiroleu. Vector control for the Chikungunya disease. Mathematical Biosciences & Engineering, 2010, 7 (2) : 313-345. doi: 10.3934/mbe.2010.7.313
[3]

Haiyan Wang. Existence and nonexistence of positive radial solutions for quasilinear systems. Conference Publications, 2009, 2009 (Special) : 810-817. doi: 10.3934/proc.2009.2009.810
[4]

Fernando P. da Costa, João T. Pinto, Rafael Sasportes. On the convergence to critical scaling profiles in submonolayer deposition models. Kinetic & Related Models, 2018, 11 (6) : 1359-1376. doi: 10.3934/krm.2018053
[5]

Rafael G. L. D'Oliveira, Marcelo Firer. Minimum dimensional Hamming embeddings. Advances in Mathematics of Communications, 2017, 11 (2) : 359-366. doi: 10.3934/amc.2017029
[6]

Sara Munday. On the derivative of the $\alpha$-Farey-Minkowski function. Discrete & Continuous Dynamical Systems - A, 2014, 34 (2) : 709-732. doi: 10.3934/dcds.2014.34.709
[7]

A. K. Misra, Anupama Sharma, Jia Li. A mathematical model for control of vector borne diseases through media campaigns. Discrete & Continuous Dynamical Systems - B, 2013, 18 (7) : 1909-1927. doi: 10.3934/dcdsb.2013.18.1909
[8]

Jia Cai, Guanglong Xu, Zhensheng Hu. Sketch-based image retrieval via CAT loss with elastic net regularization. Mathematical Foundations of Computing, 2020, 3 (4) : 219-227. doi: 10.3934/mfc.2020013
[9]

Ralf Hielscher, Michael Quellmalz. Reconstructing a function on the sphere from its means along vertical slices. Inverse Problems & Imaging, 2016, 10 (3) : 711-739. doi: 10.3934/ipi.2016018
[10]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024
[11]

F.J. Herranz, J. de Lucas, C. Sardón. Jacobi--Lie systems: Fundamentals and low-dimensional classification. Conference Publications, 2015, 2015 (special) : 605-614. doi: 10.3934/proc.2015.0605
[12]

Madalina Petcu, Roger Temam. The one dimensional shallow water equations with Dirichlet boundary conditions on the velocity. Discrete & Continuous Dynamical Systems - S, 2011, 4 (1) : 209-222. doi: 10.3934/dcdss.2011.4.209
[13]

Charles Fulton, David Pearson, Steven Pruess. Characterization of the spectral density function for a one-sided tridiagonal Jacobi matrix operator. Conference Publications, 2013, 2013 (special) : 247-257. doi: 10.3934/proc.2013.2013.247
[14]

Irena PawŃow, Wojciech M. Zajączkowski. Global regular solutions to three-dimensional thermo-visco-elasticity with nonlinear temperature-dependent specific heat. Communications on Pure & Applied Analysis, 2017, 16 (4) : 1331-1372. doi: 10.3934/cpaa.2017065

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (82)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences