A Fast Matrix Majorization-Projection Method for Penalized Stress Minimization with Box Constraint

View Researcher's Other Codes

Disclaimer: The provided code links for this paper are external links. Science Nest has no responsibility for the accuracy, legality or content of these links. Also, by downloading this code(s), you agree to comply with the terms of use as set out by the author(s) of the code(s).

Please contact us in case of a broken link from here

Authors Shenglong Zhou, Naihua Xiu, Hou-Duo Qi
Journal/Conference Name I
Paper Category
Paper Abstract Kruskal's stress minimization, though nonconvex and nonsmooth, has been a major computational model for dissimilarity data in multidimensional scaling. Semidefinite programming (SDP) relaxation (by dropping the rank constraint) would lead to a high number of SDP cone constraints. This has rendered the SDP approach computationally challenging even for problems of small size. In this paper, we reformulate the stress optimization as an Euclidean distance matrix (EDM) optimization with box constraints. A key element in our approach is the conditional positive-semidefinite cone with rank cut. Although nonconvex, this geometric object allows a fast computation of the projection onto it, and it naturally leads to a majorization-minimization algorithm with the minimization step having a closed-form solution. Moreover, we prove that our EDM optimization follows a continuously differentiable path, which greatly facilitated the analysis of the convergence to a stationary point. The superior performance of the proposed algorithm is demonstrated against some of the state-of-the-art solvers in the field of sensor network localization and molecular conformation.
Date of publication 2018
Code Programming Language MATLAB

Copyright Researcher 2022