arXiv:2602.00386math.NAcs.AI2026-02

提出矩阵乘积广义逆的统一框架,揭示随机化算法的几何本质。

Generalized Inverses of Matrix Products: From Fundamental Subspaces to Randomized Decompositions

  • 基于四个基本子空间几何,推导矩阵乘积伪逆公式
  • 给出随机化逆的充要条件:投影矩阵保持原矩阵秩
  • 解释随机SVD、Nyström、CUR等算法的内在结构

本文研究矩阵乘积 $A=CR$ 的 Moore-Penrose 伪逆与广义逆,建立统一的广义与随机矩阵逆框架。分析基于四个基本子空间的几何性质:(1)当 $C$ 列满秩且 $R$ 行满秩时,反序律 $A^+ = R^+C^+$ 成立;(2)通用公式 $A^+ = (C^+CR)^+(CRR^+)^+$ 提供了子空间映射的几何解释;(3)提出新随机公式 $A^+_p = (P^TA)^+P^TAQ(AQ)^+$,当且仅当 $ ank(P^TA) = ank(AQ) = ank(A)$ 时 $A^+_p = A^+$。框架拓展至广义 $\\(1,2\)$-逆及特殊形式,揭示了随机线性代数算法(如随机SVD、Nyström近似、CUR分解)的内在结构。应用于稀疏传感器布置与有效电阻估计,严格证明该近似始终低估真实电阻,并给出电阻差误差的最坏谱界。

原文摘要 · Abstract (English)

We investigate the Moore-Penrose pseudoinverse and generalized inverse of a matrix product $A=CR$ to establish a unifying framework for generalized and randomized matrix inverses. This analysis is rooted in first principles, focusing on the geometry of the four fundamental subspaces. We examine: (1) the reverse order law, $A^+ = R^+C^+$, which holds when $C$ has independent columns and $R$ has independent rows, (2) the universally correct formula, $A^+ = (C^+CR)^+(CRR^+)^+$, providing a geometric interpretation of the mappings between the involved subspaces, (3) a new generalized randomized formula, $A^+_p = (P^TA)^+P^TAQ(AQ)^+$, which gives $A^+_p = A^+$ if and only if the sketching matrices $P$ and $Q$ preserve the rank of $A$, i.e., $\mathrm{rank}(P^TA) = \mathrm{rank}(AQ) = \mathrm{rank}(A)$. The framework is extended to generalized $\{1,2\}$-inverses and specialized forms, revealing the underlying structure of established randomized linear algebra algorithms, including randomized SVD, the Nyström approximation, and CUR decomposition. We demonstrate applications in sparse sensor placement and effective resistance estimation. For the latter, we provide a rigorous quantitative analysis of an approximation scheme, establishing that it always underestimates the true resistance and deriving a worst-case spectral bound on the error of resistance differences.

矩阵分析随机算法伪逆子空间

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。