{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T18:08:49Z","timestamp":1781374129625,"version":"3.54.1"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2024,6,19]],"date-time":"2024-06-19T00:00:00Z","timestamp":1718755200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,6,19]],"date-time":"2024-06-19T00:00:00Z","timestamp":1718755200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004377","name":"Hong Kong Polytechnic University","doi-asserted-by":"publisher","award":["Departmental Project P0044200"],"award-info":[{"award-number":["Departmental Project P0044200"]}],"id":[{"id":"10.13039\/501100004377","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2024,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Maximum Variance Unfolding (MVU) is among the first methods in nonlinear dimensionality reduction for data visualization and classification. It aims to preserve local data structure and in the meantime push the variance among data as big as possible. However, MVU in general remains a computationally challenging problem and this may explain why it is less popular than other leading methods such as Isomap and t-SNE. In this paper, based on a key observation that the structure-preserving term in MVU is actually the squared stress in Multi-Dimensional Scaling (MDS), we replace the term with the stress function from MDS, resulting in a model that is usable. The property of the usability guarantees the \u201ccrowding phenomenon\u201d will not happen in the dimension reduced results. The new model also allows us to combine label information and hence we call it the supervised MVU (SMVU). We then develop a fast algorithm that is based on Euclidean distance matrix optimization. By making use of the majorization-mininmization technique, the algorithm at each iteration solves a number of one-dimensional optimization problems, each having a closed-form solution. This strategy significantly speeds up the computation. We demonstrate the advantage of SMVU on some standard data sets against a few leading algorithms including Isomap and t-SNE.<\/jats:p>","DOI":"10.1007\/s10994-024-06553-8","type":"journal-article","created":{"date-parts":[[2024,6,19]],"date-time":"2024-06-19T17:01:47Z","timestamp":1718816507000},"page":"6197-6226","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Supervised maximum variance unfolding"],"prefix":"10.1007","volume":"113","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8250-8072","authenticated-orcid":false,"given":"Deliang","family":"Yang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hou-Duo","family":"Qi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2024,6,19]]},"reference":[{"key":"6553_CR1","unstructured":"Arias-Castro, E., & Pelletier, B. (2013). On the convergence of maximum variance unfolding. Journal of Machine Learning Research 14(7)"},{"key":"6553_CR2","volume-title":"UCI machine learning repository","author":"A Asuncion","year":"2007","unstructured":"Asuncion, A., & Newman, D. (2007). UCI machine learning repository. CA, USA: Irvine."},{"key":"6553_CR3","volume-title":"Modern multidimensional scaling: Theory and applications","author":"I Borg","year":"2005","unstructured":"Borg, I., & Groenen, P. J. (2005). Modern multidimensional scaling: Theory and applications. Berlin: Springer."},{"key":"6553_CR4","doi-asserted-by":"crossref","unstructured":"Clarke, F.H. (1990). Optimization and Nonsmooth Analysis. In SIAM pp. 51\u201352.","DOI":"10.1137\/1.9781611971309"},{"key":"6553_CR5","doi-asserted-by":"crossref","unstructured":"Cohen, G., Afshar, S., Tapson, J., & Van\u00a0Schaik, A. (2017). Emnist: Extending mnist to handwritten letters. In: 2017 International Joint Conference on Neural Networks (IJCNN), pp. 2921\u20132926. IEEE","DOI":"10.1109\/IJCNN.2017.7966217"},{"issue":"9","key":"6553_CR6","doi-asserted-by":"publisher","first-page":"2943","DOI":"10.1080\/03610929108830679","volume":"20","author":"TF Cox","year":"1991","unstructured":"Cox, T. F., & Cox, M. A. (1991). Multidimensional scaling on a sphere. Communications in Statistics-Theory and Methods, 20(9), 2943\u20132953.","journal-title":"Communications in Statistics-Theory and Methods"},{"issue":"1","key":"6553_CR7","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/0031-3203(93)90096-F","volume":"26","author":"TF Cox","year":"1993","unstructured":"Cox, T. F., & Ferry, G. (1993). Discriminant analysis using non-metric multidimensional scaling. Pattern Recognition, 26(1), 145\u2013153.","journal-title":"Pattern Recognition"},{"issue":"1","key":"6553_CR8","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/BF02294209","volume":"49","author":"J De Leeuw","year":"1984","unstructured":"De Leeuw, J. (1984). Differentiability of Kruskal\u2019s stress at a local minimum. Psychometrika, 49(1), 111\u2013113.","journal-title":"Psychometrika"},{"issue":"2","key":"6553_CR9","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/BF01897162","volume":"5","author":"J De Leeuw","year":"1988","unstructured":"De Leeuw, J. (1988). Convergence of the majorization method for multidimensional scaling. Journal of Classification, 5(2), 163\u2013180.","journal-title":"Journal of Classification"},{"issue":"1","key":"6553_CR10","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/s10107-016-1090-7","volume":"164","author":"C Ding","year":"2017","unstructured":"Ding, C., & Qi, H.-D. (2017). Convex optimization learning of faithful Euclidean distance representations in nonlinear dimensionality reduction. Mathematical Programming, 164(1), 341\u2013381.","journal-title":"Mathematical Programming"},{"issue":"3","key":"6553_CR11","doi-asserted-by":"publisher","first-page":"2153","DOI":"10.1109\/TVCG.2019.2944182","volume":"27","author":"M Espadoto","year":"2019","unstructured":"Espadoto, M., Martins, R. M., Kerren, A., Hirata, N. S., & Telea, A. C. (2019). Toward a quantitative survey of dimension reduction techniques. IEEE Transactions on Visualization and Computer Graphics, 27(3), 2153\u20132173.","journal-title":"IEEE Transactions on Visualization and Computer Graphics"},{"key":"6553_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ins.2014.02.068","volume":"270","author":"A Gracia","year":"2014","unstructured":"Gracia, A., Gonz\u00e1lez, S., Robles, V., & Menasalvas, E. (2014). A methodology to compare dimensionality reduction algorithms in terms of loss of quality. Information Sciences, 270, 1\u201327.","journal-title":"Information Sciences"},{"issue":"5","key":"6553_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00894-019-4007-6","volume":"25","author":"F Grisoni","year":"2019","unstructured":"Grisoni, F., Neuhaus, C. S., Hishinuma, M., Gabernet, G., Hiss, J. A., Kotera, M., & Schneider, G. (2019). De novo design of anticancer peptides by ensemble artificial neural networks. Journal of Molecular Modeling, 25(5), 1\u201310.","journal-title":"Journal of Molecular Modeling"},{"issue":"8","key":"6553_CR14","doi-asserted-by":"publisher","first-page":"995","DOI":"10.1109\/TPAMI.2004.46","volume":"26","author":"P Howland","year":"2004","unstructured":"Howland, P., & Park, H. (2004). Generalizing discriminant analysis using the generalized singular value decomposition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(8), 995\u20131006.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"6553_CR15","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/B978-1-4832-3211-9.50009-7","volume":"3","author":"TH Jukes","year":"1969","unstructured":"Jukes, T. H., & Cantor, C. R. (1969). Evolution of protein molecules. Mammalian Protein Metabolism, 3, 21\u2013132.","journal-title":"Mammalian Protein Metabolism"},{"issue":"3","key":"6553_CR16","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1023\/B:MACH.0000015882.38031.85","volume":"54","author":"A Kalousis","year":"2004","unstructured":"Kalousis, A., Gama, J., & Hilario, M. (2004). On data and algorithms: Understanding inductive performance. Machine Learning, 54(3), 275\u2013312.","journal-title":"Machine Learning"},{"issue":"1","key":"6553_CR17","first-page":"2384","volume":"20","author":"KL Keys","year":"2019","unstructured":"Keys, K. L., Zhou, H., & Lange, K. (2019). Proximal distance algorithms: Theory and practice. The Journal of Machine Learning Research, 20(1), 2384\u20132421.","journal-title":"The Journal of Machine Learning Research"},{"issue":"2","key":"6553_CR18","doi-asserted-by":"publisher","first-page":"758","DOI":"10.1016\/j.patcog.2013.07.022","volume":"47","author":"K Kim","year":"2014","unstructured":"Kim, K., & Lee, J. (2014). Sentiment visualization and classification via semi-supervised nonlinear dimensionality reduction. Pattern Recognition, 47(2), 758\u2013768.","journal-title":"Pattern Recognition"},{"key":"6553_CR19","unstructured":"Krizhevsky, A., & Hinton, G., et al. (2009). Learning multiple layers of features from tiny images"},{"issue":"1","key":"6553_CR20","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/s10994-014-5455-y","volume":"101","author":"HA Le Thi","year":"2015","unstructured":"Le Thi, H. A., Le, H. M., & Pham Dinh, T. (2015). Feature selection in machine learning: an exact penalty approach using a difference of convex function algorithm. Machine Learning, 101(1), 163\u2013186.","journal-title":"Machine Learning"},{"issue":"12","key":"6553_CR21","doi-asserted-by":"publisher","first-page":"6073","DOI":"10.1109\/TNNLS.2018.2817538","volume":"29","author":"Z Li","year":"2018","unstructured":"Li, Z., Nie, F., Chang, X., Nie, L., Zhang, H., & Yang, Y. (2018). Rank-constrained spectral clustering with flexible embedding. IEEE Transactions on Neural Networks and Learning Systems, 29(12), 6073\u20136082.","journal-title":"IEEE Transactions on Neural Networks and Learning Systems"},{"issue":"6","key":"6553_CR22","doi-asserted-by":"publisher","first-page":"1147","DOI":"10.1109\/TPAMI.2010.183","volume":"33","author":"Y-Y Lin","year":"2010","unstructured":"Lin, Y.-Y., Liu, T.-L., & Fuh, C.-S. (2010). Multiple kernel learning for dimensionality reduction. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(6), 1147\u20131160.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"issue":"4","key":"6553_CR23","doi-asserted-by":"publisher","first-page":"1641","DOI":"10.1137\/090771181","volume":"21","author":"Q Li","year":"2011","unstructured":"Li, Q., & Qi, H.-D. (2011). A sequential semismooth newton method for the nearest low-rank correlation matrix problem. SIAM Journal on Optimization, 21(4), 1641\u20131666.","journal-title":"SIAM Journal on Optimization"},{"issue":"1","key":"6553_CR24","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/s10107-015-0961-7","volume":"159","author":"W Miao","year":"2016","unstructured":"Miao, W., Pan, S., & Sun, D. (2016). A rank-corrected procedure for matrix completion with fixed basis coefficients. Mathematical Programming, 159(1), 289\u2013338.","journal-title":"Mathematical Programming"},{"key":"6553_CR25","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1016\/j.patrec.2017.09.032","volume":"100","author":"R Paul","year":"2017","unstructured":"Paul, R., & Chalup, S. K. (2017). A study on validating non-linear dimensionality reduction using persistent homology. Pattern Recognition Letters, 100, 160\u2013166.","journal-title":"Pattern Recognition Letters"},{"issue":"12","key":"6553_CR26","doi-asserted-by":"publisher","first-page":"2159","DOI":"10.1007\/s10994-019-05818-x","volume":"108","author":"Q Peng","year":"2019","unstructured":"Peng, Q., Rao, N., & Zhao, R. (2019). Covariance-based dissimilarity measures applied to clustering wide-sense stationary ergodic processes. Machine Learning, 108(12), 2159\u20132195.","journal-title":"Machine Learning"},{"issue":"1","key":"6553_CR27","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/s10107-013-0726-0","volume":"147","author":"H-D Qi","year":"2014","unstructured":"Qi, H.-D., & Yuan, X. (2014). Computing the nearest Euclidean distance matrix with low embedding dimensions. Mathematical Programming, 147(1), 351\u2013389.","journal-title":"Mathematical Programming"},{"issue":"2","key":"6553_CR28","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/s10589-021-00276-5","volume":"79","author":"A Sagan","year":"2021","unstructured":"Sagan, A., & Mitchell, J. E. (2021). Low-rank factorization for rank minimization with nonconvex regularizers. Computational Optimization and Applications, 79(2), 273\u2013300.","journal-title":"Computational Optimization and Applications"},{"issue":"3","key":"6553_CR29","doi-asserted-by":"publisher","first-page":"522","DOI":"10.1090\/S0002-9947-1938-1501980-0","volume":"44","author":"IJ Schoenberg","year":"1938","unstructured":"Schoenberg, I. J. (1938). Metric spaces and positive definite functions. Transactions of the American Mathematical Society, 44(3), 522\u2013536.","journal-title":"Transactions of the American Mathematical Society"},{"key":"6553_CR30","unstructured":"Song, L., Smola, A. J., Borgwardt, K. M., & Gretton, A. (2007). Colored maximum variance unfolding. In Nips, pp. 1385\u20131392. Citeseer"},{"key":"6553_CR31","unstructured":"Song, L., Smola, A., Gretton, A., Bedo, J., & Borgwardt, K. (2012). Feature selection via dependence maximization. Journal of Machine Learning Research 13(5)"},{"issue":"3","key":"6553_CR32","doi-asserted-by":"publisher","first-page":"794","DOI":"10.1109\/TSP.2016.2601299","volume":"65","author":"Y Sun","year":"2016","unstructured":"Sun, Y., Babu, P., & Palomar, D. P. (2016). Majorization-minimization algorithms in signal processing, communications, and machine learning. IEEE Transactions on Signal Processing, 65(3), 794\u2013816.","journal-title":"IEEE Transactions on Signal Processing"},{"issue":"4","key":"6553_CR33","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1137\/S0036144504443821","volume":"48","author":"J Sun","year":"2006","unstructured":"Sun, J., Boyd, S., Xiao, L., & Diaconis, P. (2006). The fastest mixing Markov process on a graph and a connection to a maximum variance unfolding problem. SIAM Review, 48(4), 681\u2013699.","journal-title":"SIAM Review"},{"issue":"5500","key":"6553_CR34","doi-asserted-by":"publisher","first-page":"2319","DOI":"10.1126\/science.290.5500.2319","volume":"290","author":"JB Tenenbaum","year":"2000","unstructured":"Tenenbaum, J. B., De Silva, V., & Langford, J. C. (2000). A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500), 2319\u20132323.","journal-title":"Science"},{"issue":"2","key":"6553_CR35","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/s10994-018-5737-x","volume":"108","author":"KM Ting","year":"2019","unstructured":"Ting, K. M., Zhu, Y., Carman, M., Zhu, Y., Washio, T., & Zhou, Z.-H. (2019). Lowest probability mass neighbor algorithms: Relaxing the metric constraint in distance-based neighborhood algorithms. Machine Learning, 108(2), 331\u2013376.","journal-title":"Machine Learning"},{"issue":"11","key":"6553_CR36","first-page":"2579","volume":"9","author":"L Van der Maaten","year":"2008","unstructured":"Van der Maaten, L., & Hinton, G. (2008). Visualizing data using t-SNE. Journal of Machine Learning Research, 9(11), 2579\u20132605.","journal-title":"Journal of Machine Learning Research"},{"key":"6553_CR37","volume-title":"Matlab toolbox for dimensionality reduction","author":"L Van der Maaten","year":"2007","unstructured":"Van der Maaten, L., Postma, E. O., & van den Herik, H. J. (2007). Matlab toolbox for dimensionality reduction. Maastricht: Maastricht University, MICC."},{"key":"6553_CR38","doi-asserted-by":"crossref","unstructured":"Vlachos, M., Domeniconi, C., Gunopulos, D., Kollios, G., & Koudas, N. (2002). Non-linear dimensionality reduction techniques for classification and visualization. In: Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 645\u2013651","DOI":"10.1145\/775047.775143"},{"issue":"8","key":"6553_CR39","doi-asserted-by":"publisher","first-page":"1334","DOI":"10.1109\/TPAMI.2005.165","volume":"27","author":"L Wang","year":"2005","unstructured":"Wang, L., Zhang, Y., & Feng, J. (2005). On the Euclidean distance of images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 27(8), 1334\u20131339.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"6553_CR40","doi-asserted-by":"crossref","unstructured":"Weinberger, K. Q., Sha, F., Zhu, Q., & Saul, L. K. (2007). Graph Laplacian regularization for large-scale semidefinite programming. In Advances in Neural Information Processing Systems, pp. 1489\u20131496","DOI":"10.7551\/mitpress\/7503.003.0191"},{"key":"6553_CR41","first-page":"1683","volume":"6","author":"KQ Weinberger","year":"2006","unstructured":"Weinberger, K. Q., & Saul, L. K. (2006). An introduction to nonlinear dimensionality reduction by maximum variance unfolding. AAI, 6, 1683\u20131686.","journal-title":"AAI"},{"key":"6553_CR42","unstructured":"Yang, J., Shi, R., Wei, D., Liu, Z., Zhao, L., Ke, B., Pfister, H., & Ni, B. (2021). Medmnist v2: A large-scale lightweight benchmark for 2d and 3d biomedical image classification. arXiv preprint arXiv:2110.14795"},{"issue":"1","key":"6553_CR43","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1109\/TPAMI.2007.250598","volume":"29","author":"S Yan","year":"2006","unstructured":"Yan, S., Xu, D., Zhang, B., Zhang, H.-J., Yang, Q., & Lin, S. (2006). Graph embedding and extensions: A general framework for dimensionality reduction. IEEE Transactions on Pattern Analysis and Machine Intelligence, 29(1), 40\u201351.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"issue":"3","key":"6553_CR44","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1109\/TPAMI.2007.70714","volume":"30","author":"J Yu","year":"2008","unstructured":"Yu, J., Amores, J., Sebe, N., Radeva, P., & Tian, Q. (2008). Distance learning for similarity estimation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 30(3), 451\u2013462.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"issue":"16","key":"6553_CR45","doi-asserted-by":"publisher","first-page":"4331","DOI":"10.1109\/TSP.2018.2849734","volume":"66","author":"S Zhou","year":"2018","unstructured":"Zhou, S., Xiu, N., & Qi, H.-D. (2018). A fast matrix majorization\u2013projection method for penalized stress minimization with box constraints. IEEE Transactions on Signal Processing, 66(16), 4331\u20134346.","journal-title":"IEEE Transactions on Signal Processing"},{"issue":"3","key":"6553_CR46","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/s12532-019-00168-0","volume":"12","author":"S Zhou","year":"2020","unstructured":"Zhou, S., Xiu, N., & Qi, H.-D. (2020). Robust Euclidean embedding via EDM optimization. Mathematical Programming Computation, 12(3), 337\u2013387.","journal-title":"Mathematical Programming Computation"}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-024-06553-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10994-024-06553-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-024-06553-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T17:23:43Z","timestamp":1723051423000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10994-024-06553-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,19]]},"references-count":46,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2024,9]]}},"alternative-id":["6553"],"URL":"https:\/\/doi.org\/10.1007\/s10994-024-06553-8","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,6,19]]},"assertion":[{"value":"27 May 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 September 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 April 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 June 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Informed consent for publication of this paper was obtained from all authors.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to participate"}},{"value":"Not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}}]}}