在线咨询
中国工业与应用数学学会会刊
主管:中华人民共和国教育部
主办:西安交通大学
ISSN 1005-3085  CN 61-1269/O1

工程数学学报 ›› 2026, Vol. 43 ›› Issue (3): 417-425.doi: 10.3969/j.issn.1005-3085.2026.03.002cstr: 32411.14.cjem.CN61-1269/O1.2026.03.002

• • 上一篇    下一篇

一类随机广义奇异值分解方法

宋蒙蕊,   沈卫杰   

  1. 南京信息工程大学数学与统计学院,南京  210044
  • 收稿日期:2023-12-16 接受日期:2026-06-26 出版日期:2026-04-15 发布日期:2026-08-15
  • 通讯作者: 沈卫杰 E-mail: swj@nuist.edu.cn
  • 基金资助:
    国家自然科学基金(11971243).

A Class of Random Generalized Singular Value Decomposition Method

SONG Mengrui,   SHEN Weijie   

  1. School of Mathematics and Statistics, Nanjing University of Information Science and Technology, Nanjing 210044
  • Received:2023-12-16 Accepted:2026-06-26 Online:2026-04-15 Published:2026-08-15
  • Contact: W. Shen. E-mail address: swj@nuist.edu.cn
  • Supported by:
    The National Natural Science Foundation of China (11971243).

摘要:

广义奇异值分解是矩阵计算中重要的数学工具,在正则化计算、信号处理等领域被广泛应用。然而,随着数据集规模的增大,传统方法计算大规模矩阵对面临着较大的时间和空间复杂度问题。针对这一问题,提出了一类基于随机低秩逼近的广义奇异值分解方法。该方法首先利用随机投影技术提取矩阵的主导子空间,通过正交分解构造低秩逼近,从而实现对原矩阵对的有效压缩;随后在压缩空间中计算小矩阵对的广义奇异值分解。对算法的结构性质与计算复杂度进行了分析,并证明了方法的有效性。数值实验结果表明,在低秩情形下,所提方法在保持数值稳定性的同时计算时间较Matlab内置广义奇异值分解函数提升3$\sim$4倍,并具有较高的分解精度;在不适定问题正则化求解中,该方法能够有效提高近似解质量。

关键词: 随机算法, 低秩近似, 随机广义奇异值分解

Abstract:

The generalized singular value decomposition (GSVD) is an important tool in matrix computations and has been widely applied in areas such as regularization and signal processing. However, as the scale of data sets increases, classical methods face significant challenges in terms of computational time and storage complexity when applied to large-scale matrix pairs. To address this issue, a randomized GSVD method based on low-rank approximation is proposed. The method first uses random projection to capture the dominant subspaces of the matrices and constructs low-rank approximations via orthogonal factorization, thereby compressing the original matrix pairs. The GSVD of the compressed small matrix pair is then computed in the compressed space. The structural properties and computational complexity of the algorithm are analyzed, and the effectiveness of the method is established. Numerical experiments demonstrate that, in the low-rank setting, the proposed method maintains numerical stability while achieving a three- to four-fold speedup compared with the built-in GSVD function in Matlab, along with high accuracy. Furthermore, in the regularized solution of ill-posed problems, the method is shown to effectively improve the quality of approximate solutions.

Key words: random algorithm, low-rank approximation, random generalized singular value decomposition

中图分类号: