IDEAS home Printed from https://ideas.repec.org/a/spr/joptap/v202y2024i2d10.1007_s10957-024-02486-3.html
   My bibliography  Save this article

A Globally Convergent Inertial First-Order Optimization Method for Multidimensional Scaling

Author

Listed:
  • Noga Ram

    (Technion—Israel Institute of Technology)

  • Shoham Sabach

    (Technion—Israel Institute of Technology)

Abstract

Multidimensional scaling (MDS) is a popular tool for dimensionality reduction and data visualization. Given distances between data points and a target low-dimension, the MDS problem seeks to find a configuration of these points in the low-dimensional space, such that the inter-point distances are preserved as well as possible. We focus on the most common approach to formulate the MDS problem, known as stress minimization, which results in a challenging non-smooth and non-convex optimization problem. In this paper, we propose an inertial version of the well-known SMACOF Algorithm, which we call AI-SMACOF. This algorithm is proven to be globally convergent, and to the best of our knowledge this is the first result of this kind for algorithms aiming at solving the stress MDS minimization. In addition to the theoretical findings, numerical experiments provide another evidence for the superiority of the proposed algorithm.

Suggested Citation

  • Noga Ram & Shoham Sabach, 2024. "A Globally Convergent Inertial First-Order Optimization Method for Multidimensional Scaling," Journal of Optimization Theory and Applications, Springer, vol. 202(2), pages 949-974, August.
    • Handle: RePEc:spr:joptap:v:202:y:2024:i:2:d:10.1007_s10957-024-02486-3
    DOI: 10.1007/s10957-024-02486-3
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10957-024-02486-3
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10957-024-02486-3?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Warren Torgerson, 1952. "Multidimensional scaling: I. Theory and method," Psychometrika, Springer;The Psychometric Society, vol. 17(4), pages 401-419, December.
    2. J. Kruskal, 1964. "Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis," Psychometrika, Springer;The Psychometric Society, vol. 29(1), pages 1-27, March.
    3. Jan Leeuw, 1988. "Convergence of the majorization method for multidimensional scaling," Journal of Classification, Springer;The Classification Society, vol. 5(2), pages 163-180, September.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Kagie, M. & van Wezel, M.C. & Groenen, P.J.F., 2009. "Map Based Visualization of Product Catalogs," ERIM Report Series Research in Management ERS-2009-010-MKT, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    2. Leung, Pui Lam & Lau, Kin-nam, 2004. "Estimating the city-block two-dimensional scaling model with simulated annealing," European Journal of Operational Research, Elsevier, vol. 158(2), pages 518-524, October.
    3. Gruenhage, Gina & Opper, Manfred & Barthelme, Simon, 2016. "Visualizing the effects of a changing distance on data using continuous embeddings," Computational Statistics & Data Analysis, Elsevier, vol. 104(C), pages 51-65.
    4. Morales José F. & Song Tingting & Auerbach Arleen D. & Wittkowski Knut M., 2008. "Phenotyping Genetic Diseases Using an Extension of µ-Scores for Multivariate Data," Statistical Applications in Genetics and Molecular Biology, De Gruyter, vol. 7(1), pages 1-20, June.
    5. Bijmolt, T.H.A. & Wedel, M., 1996. "A Monte Carlo Evaluation of Maximum Likelihood Multidimensional Scaling Methods," Research Memorandum 725, Tilburg University, School of Economics and Management.
    6. Si-Tong Lu & Miao Zhang & Qing-Na Li, 2020. "Feasibility and a fast algorithm for Euclidean distance matrix optimization with ordinal constraints," Computational Optimization and Applications, Springer, vol. 76(2), pages 535-569, June.
    7. Wayne DeSarbo & Joonwook Park & Crystal Scott, 2008. "A Model-Based Approach for Visualizing the Dimensional Structure of Ordered Successive Categories Preference Data," Psychometrika, Springer;The Psychometric Society, vol. 73(1), pages 1-20, March.
    8. Michael W. Trosset, 2002. "Extensions of Classical Multidimensional Scaling via Variable Reduction," Computational Statistics, Springer, vol. 17(2), pages 147-163, July.
    9. Lin, Sheng-Wei & Lu, Wen-Min, 2024. "Discretionary investment managers evaluation in pension fund: Shared input dynamic network DEA approach," Omega, Elsevier, vol. 127(C).
    10. Groenen, P.J.F. & Borg, I., 2013. "The Past, Present, and Future of Multidimensional Scaling," Econometric Institute Research Papers EI 2013-07, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    11. Groenen, P.J.F. & van de Velden, M., 2004. "Multidimensional scaling," Econometric Institute Research Papers EI 2004-15, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    12. Herden, Gerhard & Pallack, Andreas, 2002. "Consistency in ordinal data analysis I," Mathematical Social Sciences, Elsevier, vol. 43(1), pages 79-113, January.
    13. Venera Tomaselli, 1996. "Multivariate statistical techniques and sociological research," Quality & Quantity: International Journal of Methodology, Springer, vol. 30(3), pages 253-276, August.
    14. Bijmolt, T.H.A. & Wedel, M., 1996. "A Monte Carlo Evaluation of Maximum Likelihood Multidimensional Scaling Methods," Other publications TiSEM f72cc9d8-f370-43aa-a224-4, Tilburg University, School of Economics and Management.
    15. Kagie, M. & van Wezel, M.C. & Groenen, P.J.F., 2007. "A graphical shopping interface bases on product attributes," Econometric Institute Research Papers EI 2007-02, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    16. Cristian Rizzo & Matteo Di Giuseppe & Domenico Moramarco & Simone Pizzi & Myriam Portaluri & Gianluigi Guido, 2016. "L?effetto dell?inquinamento acustico sulla distanza percepita dei punti vendita," ESPERIENZE D'IMPRESA, FrancoAngeli Editore, vol. 2016(1), pages 65-79.
    17. Xiaomeng Cao & Yuan Gao & Jingwei Cui & Shuangbiao Han & Lei Kang & Sha Song & Chengshan Wang, 2020. "Pore Characteristics of Lacustrine Shale Oil Reservoir in the Cretaceous Qingshankou Formation of the Songliao Basin, NE China," Energies, MDPI, vol. 13(8), pages 1-25, April.
    18. He, Jiayi & Shang, Pengjian & Xiong, Hui, 2018. "Multidimensional scaling analysis of financial time series based on modified cross-sample entropy methods," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 500(C), pages 210-221.
    19. Lin, L. & Fong, D.K.H., 2019. "Bayesian multidimensional scaling procedure with variable selection," Computational Statistics & Data Analysis, Elsevier, vol. 129(C), pages 1-13.
    20. W. J. Krzanowski, 2006. "Sensitivity in Metric Scaling and Analysis of Distance," Biometrics, The International Biometric Society, vol. 62(1), pages 239-244, March.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:joptap:v:202:y:2024:i:2:d:10.1007_s10957-024-02486-3. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.