多维标度分析中一类正交性个体差异标度模型的 $\varepsilon$- 加速算法

数学物理学报 ›› 2026, Vol. 46 ›› Issue (5): 1962-1989.

多维标度分析中一类正交性个体差异标度模型的 $\varepsilon$- 加速算法

覃月凤, 韦远芬, 潘雪波, 梁惠宇, 陈新, 李姣芬^*()

桂林电子科技大学数学与计算科学学院, 广西应用数学中心 (桂林电子科技大学), 广西高校数据分析与计算重点实验室桂林 541004

收稿日期:2025-06-29 修回日期:2025-09-15 出版日期:2026-10-26 发布日期:2026-09-07
通讯作者: 李姣芬 E-mail:lixiaogui1290@163.com
基金资助:
国家自然科学基金(12261026);广西科技项目(Guike AD25069086);桂林电子科技大学国家级大学生创新创业训练计划(202410595070);广西自动检测技术与仪器重点实验室基金(YQ23104);广西自动检测技术与仪器重点实验室基金(YQ24105)

Epsilon Acceleration Algorithms for the Orthogonal-Indscal Problem in Multidimensional Scaling Analysis

Yuefeng Qin, Yuanfen Wei, Xuebo Pan, Huiyu Liang, Xin Chen, Jiaofen Li^*()

School of Mathematics and Computing Science, Center for Applied Mathematics of Guangxi (GUET), Guangxi Colleges and Universities Key Laboratory of Data Analysis and Computation, Guilin University of Electronic Technology, Guilin 541004

Received:2025-06-29 Revised:2025-09-15 Online:2026-10-26 Published:2026-09-07
Contact: Jiaofen Li E-mail:lixiaogui1290@163.com
Supported by:
NSFC(12261026);Guangxi Science and Technology Project(Guike AD25069086);National College Student Innovation and Entrepreneurship Training Program at Guilin University of Electronic Technology(202410595070);Guangxi Key Laboratory of Automated Detection Technology and Instrumentation Fund(YQ23104);Guangxi Key Laboratory of Automated Detection Technology and Instrumentation Fund(YQ24105)

摘要/Abstract

摘要：

多维标度分析 (Multidimensional Scaling, MDS) 是一种在低维空间中以点间距离展现主体对象之间相似性测度或亲疏关系的数据分析方法, 其通过在低维空间中表示高维数据, 保留数据点之间的相对距离关系. 个体差异标度 (Individual Differences Scaling, INDSCAL) 模型是一类针对多个对称数据矩阵进行同步 MDS, 揭示不同主体对象之间结构关系同时考虑不同主体之间尺度差异的多维数据分析模型. 该文从数值角度考虑一类正交性INDSCAL (O-INDSCAL) 模型, 其可数学归纳为列正交约束和非负对角约束下的一类多变量矩阵优化模型. 首先基于交替最小二乘法迭代思想转换原问题为一类矩阵形式不动点迭代问题, 进而基于向量序列加速中的 $\varepsilon$-算法加速原理, 提出相应的结合 $\varepsilon$-算法的不动点迭代加速算法. 数值实验表明, 对于求解 O-INDSCAL 模型, 结合 $\varepsilon$-算法的不动点迭代加速算法具有良好的加速效果, 同时与模型求解已有的投影梯度流算法以及流形优化工具箱 Manopt 中若干一阶和二阶算法相比, 在迭代效率方面具有较为明显的优势.

关键词: 多维标度分析, 个体差异标度, 向量序列加速, $\varepsilon$-算法

Abstract:

Multidimensional Scaling (MDS) is a fundamental data analysis technique that represents similarity or dissimilarity among objects by mapping them into a lower-dimensional space while preserving relative distances between data points. The Individual Differences Scaling (INDSCAL) model extends MDS by jointly analyzing multiple symmetric data matrices, capturing structural relationships among different subjects while accounting for individual scale variations. Mathematically, INDSCAL can be formulated as a multivariate matrix optimization problem subject to column orthogonality and non-negative diagonal constraints. This paper presents an efficient numerical algorithm for solving the Orthogonal-INDSCAL (O-INDSCAL) model. The original problem is first reformulated as a matrix fixed-point iteration using the alternating least squares (ALS) method. To enhance convergence, we incorporate the $\varepsilon$-algorithm, a vector sequence acceleration technique, into a corresponding $\varepsilon$-accelerated fixed-point iteration algorithm. Numerical experiments demonstrate that the proposed $\varepsilon$-accelerated fixed-point iteration algorithm significantly improves convergence speed in solving the O-INDSCAL model. Moreover, compared to existing approaches such as projected gradient flow algorithms and various first- and second-order methods in the Manopt toolbox, our method exhibits superior iterative efficiency, highlighting its practical advantages in large-scale optimization.

Key words: multidimensional scaling, individual differences scaling, vector sequence acceleration, $\varepsilon$-algorithm

中图分类号:

O151.1

覃月凤, 韦远芬, 潘雪波, 梁惠宇, 陈新, 李姣芬. 多维标度分析中一类正交性个体差异标度模型的 $\varepsilon$- 加速算法[J]. 数学物理学报, 2026, 46(5): 1962-1989.

Yuefeng Qin, Yuanfen Wei, Xuebo Pan, Huiyu Liang, Xin Chen, Jiaofen Li. Epsilon Acceleration Algorithms for the Orthogonal-Indscal Problem in Multidimensional Scaling Analysis[J]. Acta mathematica scientia,Series A, 2026, 46(5): 1962-1989.

图/表 12

表1

表2

表3

表4

图 1

表5

图 2

表6

图 3

图4

表7

表8

参考文献 50

[1]	Borg I, Groenen P J. Modern Multidimensional Scaling:Theory and Applications. New York: Springer Science & Business Media, 2005
[2]	Trendafilov N, Gallo M. Multivariate Data Analysis on Matrix Manifolds. Berlin: Springer, 2021
[3]	Carroll J D, Chang J J. Analysis of individual differences in multidimensional scaling via an N-way generalization of "Eckart-Young" decomposition. Psychometrika, 1970, 35(3): 283-319 doi: 10.1007/BF02310791
[4]	Husson F, Pagès J. INDSCAL model: geometrical interpretation and methodology. Computational Statistics & Data Analysis, 2006, 50(2): 358-378
[5]	Trendafilov N T. Orthonormality-Constrained INDSCAL with Nonnegative Saliences.//International Conference on Computational Science and Its Applications, Berlin: Springer, 2004: 952-960
[6]	Trendafilov N T. The dynamical system approach to multivariate data analysis. Journal of Computational and Graphical Statistics, 2006, 15(3): 628-650 doi: 10.1198/106186006X130828
[7]	ten Berge J M, Kiers H A, de Leeuw J. Explicit CANDECOMP/PARAFAC solutions for a contrived 2 $\times$ 2 $\times$ 2 array of rank three. Psychometrika, 1988, 53(4): 579-583 doi: 10.1007/BF02294409
[8]	Trendafilov N T. GIPSCAL revisited. A projected gradient approach. Statistics and Computing, 2002, 12(2): 135-145
[9]	Trendafilov N T. Dynamical system approach to factor analysis parameter estimation. British Journal of Mathematical and Statistical Psychology, 2003, 56(1): 27-46 doi: 10.1348/000711003321645322
[10]	Trendafilov N T, Jolliffe I T. Projected gradient approach to the numerical solution of the SCoTLASS. Computational Statistics & Data Analysis, 2006, 50(1): 242-253
[11]	Trendafilov N T. DINDSCAL: direct INDSCAL. Statistics and Computing, 2012, 22: 445-454
[12]	Tendeiro J, Dosse M B, Berge J M T. First and second-order derivatives for CP and INDSCAL. Chemometrics and Intelligent Laboratory Systems, 2011, 106(1): 27-36 doi: 10.1016/j.chemolab.2010.05.013
[13]	Takane Y, Jung K, Hwang H. et al. An acceleration method for Ten Berge et al.'s algorithm for orthogonal INDSCAL. Computational Statistics, 2010, 25(3): 409-428
[14]	陈新, 覃月凤, 周学林, 李姣芬. 多维标度中个体差异标度模型的向量序列加速算法. 计算数学, 2025, 47(2): 255-284 doi: 10.12286/jssx.j2024-1213
	Chen X, Qin Y, Zhou X, Li J. Vector sequence acceleration algorithms for the INDSCAL model in multidimensional scaling analysis. Mathematica Numerica Sinica, 2025, 47(2): 255-284 doi: 10.12286/jssx.j2024-1213
[15]	Shanks D. Non-linear transformations of divergent and slowly convergent sequences. Journal of Mathematics and Physics, 1955, 34(1-4): 1-42 doi: 10.1002/sapm.v34.1
[16]	Wynn P. On a device for computing the $e_m (S_n)$ transformation. Mathematical Tables and Other Aids to Computation, 1956: 91-96
[17]	Wynn P. Acceleration techniques for iterated vector and matrix problems. Mathematics of Computation, 1962, 16(79): 301-322 doi: 10.1090/mcom/1962-16-079
[18]	Brezinski C, Zaglia M R. Extrapolation Methods:Theory and Practice. Amsterdam: Elsevier, 2013
[19]	Brezinski C, Redivo-Zaglia M. The simplified topological $\varepsilon$-algorithms for accelerating sequences in a vector space. SIAM Journal on Scientific Computing, 2014, 36(5): A2227-A2247 doi: 10.1137/140957044
[20]	Brezinski C, Redivo-Zaglia M. The simplified topological $\varepsilon$-algorithms: software and applications. Numerical Algorithms, 2017, 74: 1237-1260 doi: 10.1007/s11075-016-0238-0
[21]	Saâdaoui F. Quadratic extrapolation for accelerating convergence of the EM fixed point problem. Journal of Computational and Applied Mathematics, 2020, 369: Art 112577 doi: 10.1016/j.cam.2019.112577
[22]	Chehab J P, Raydan M. Geometrical inverse matrix approximation for least-squares problems and acceleration strategies. Numerical Algorithms, 2020, 85: 1213-1231 doi: 10.1007/s11075-019-00862-z
[23]	Brezinski C, Cipolla S, Redivo-Zaglia M, Saad Y. Shanks and Anderson-type acceleration techniques for systems of nonlinear equations. IMA Journal of Numerical Analysis, 2022, 42(4): 3058-3093 doi: 10.1093/imanum/drab061
[24]	He H, Tang Z, Zhao S, Saad Y, Xi Y. nltgcr: A class of nonlinear acceleration procedures based on conjugate residuals. SIAM Journal on Matrix Analysis and Applications, 2024, 45(1): 712-743 doi: 10.1137/23M1576360
[25]	Saâdaoui F. Accelerated numerical solutions for discretized Black-Scholes equations. IMA Journal of Management Mathematics, 2026, 37(1): 273-293 doi: 10.1093/imaman/dpae006
[26]	Azzarelli A, Brezinski C, Fenu C, et al. Parameter Choice Rules for Discrete Ill-Posed Problems Based on Extrapolation Methods. Journal of Scientific Computing, 2025, 103(1): Art 9 doi: 10.1007/s10915-025-02822-3
[27]	Gazzola S, Karapiperi A. Image reconstruction and restoration using the simplified topological $\varepsilon$-algorithm. Applied Mathematics and Computation, 2016, 274: 539-555 doi: 10.1016/j.amc.2015.11.027
[28]	Gander W, Shi Q. Matrix completion with $\varepsilon$-algorithm: In memory of Peter Wynn (1931-2017). Numerical Algorithms, 2019, 80(1): 279-301 doi: 10.1007/s11075-018-0579-y
[29]	Cipolla S, Redivo-Zaglia M, Tudisco F. Extrapolation methods for fixed-point multilinear PageRank computations. Numerical Linear Algebra with Applications, 2020, 27(2): e2280 doi: 10.1002/nla.v27.2
[30]	Hiriart-Urruty J B, Lemaréchal C. Convex Analysis and Minimization Algorithms I: Fundamentals. Berlin: Springer, 1996
[31]	Jennrich R I. A simple general procedure for orthogonal rotation. Psychometrika, 2001, 66: 289-306 doi: 10.1007/BF02294840
[32]	Duminil S, Sadok H, Silvester D. Fast solvers for discretized Navier-Stokes problems using vector extrapolation. Numerical Algorithms, 2014, 66: 89-104 doi: 10.1007/s11075-013-9726-7
[33]	Higham N J, Strabić N. Anderson acceleration of the alternating projections method for computing the nearest correlation matrix. Numerical Algorithms, 2016, 72: 1021-1042 doi: 10.1007/s11075-015-0078-3
[34]	An H, Jia X, Walker H F. Anderson acceleration and application to the three-temperature energy equations. Journal of Computational Physics, 2017, 347: 1-19
[35]	Awasthi N, Kalva S K, Pramanik M, Yalavarthy P K. Vector extrapolation methods for accelerating iterative reconstruction methods in limited-data photoacoustic tomography. Journal of Biomedical Optics, 2018, 23(7): Art 071204
[36]	Pollock S, Rebholz L G, Xiao M. Anderson-accelerated convergence of Picard iterations for incompressible Navier-Stokes equations. SIAM Journal on Numerical Analysis, 2019, 57(2): 615-637 doi: 10.1137/18M1206151
[37]	Nazer S A, Jazar M, Rosier C. Convergence acceleration of iterative sequences for equilibrium chemistry computations. Computational Geosciences, 2021, 25(5): 1509-1538 doi: 10.1007/s10596-021-10054-1
[38]	Lai F, Li W, Peng X, Chen Y. Anderson accelerated fixed-point iteration for multilinear PageRank. Numerical Linear Algebra with Applications, 2023, 30(5): e2499 doi: 10.1002/nla.v30.5
[39]	Bentbib A H, Boubekraoui M, Jbilou K. Extrapolation methods for multilinear PageRank. Numerical Algorithms, 2025, 98(2): 1013-1043 doi: 10.1007/s11075-024-01823-x
[40]	Brezinski C, Redivo-Zaglia M, Saad Y. Shanks sequence transformations and Anderson acceleration. SIAM Review, 2018, 60(3): 646-669 doi: 10.1137/17M1120725
[41]	Brezinski C. Convergence acceleration during the 20th century. Journal of Computational and Applied Mathematics, 2000, 122(1/2): 1-21 doi: 10.1016/S0377-0427(00)00360-5
[42]	d' Aspremont A, Scieur D, Taylor A. Acceleration methods. Foundations and Trends® in Optimization, 2021, 5(1/2): 1-245 doi: 10.1561/OPT
[43]	Saad Y. Acceleration methods for fixed point iterations. Acta Numerica, 2025, 34: 805-890 doi: 10.1017/S0962492924000096
[44]	Brezinski C, Redivo-Zaglia M. The genesis and early developments of Aitken's process, Shanks' transformation, the $\varepsilon$-algorithm, and related fixed point methods. Numerical Algorithms, 2019, 80(1): 11-133 doi: 10.1007/s11075-018-0567-2
[45]	Sidi A. Vector Extrapolation Methods with Applications. Philadelphia: SIAM, 2017
[46]	Absil P A, Mahony R, Sepulchre R. Optimization Algorithms on Matrix Manifolds. Princeton: Princeton University Press, 2008
[47]	Boumal N, Mishra B, Absil P A, Sepulchre R. Manopt, a Matlab toolbox for optimization on manifolds. Journal of Machine Learning Research, 2014, 15(1): 1455-1459
[48]	Li J, Zhou J, Zhou X, et al. A trust-region approach for iteration solution of the direct fitting metric MDS. BIT Numerical Mathematics, 2025, 65(2): 1-37 doi: 10.1007/s10543-024-01045-6
[49]	Zhou X, Li J, Li C. An efficient algorithm for fitting the three-way GIPSCAL problem with missing values from asymmetric multidimensional scaling. Numerical Algorithms, 2025, 1-42. Online, https://doi.org/10.1007/s11075-025-02136-3
[50]	Zhou X, Li C, Li J, Duan X. A Riemannian inexact Newton method for solving the orthogonal INDSCAL problem in multidimensional scaling. IMA Journal of Numerical Analysis, https://doi.org/10.1093/imanum/draf047, 2025