Generalized Inverses of Matrix Products: From Fundamental Subspaces to Randomized Decompositions
Preprint
Abstract
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.
Keywords
All Related Versions
This publication has 22 references indexed in Scilit:
- Fast randomized least‐squares solvers can be just as accurate and stable as classical direct solversCommunications on Pure and Applied Mathematics, 2025
- Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositionsAdvances in Computational Mathematics, 2023
- Optimal Sensor and Actuator Selection Using Balanced Model ReductionIEEE Transactions on Automatic Control, 2021
- Randomized numerical linear algebra: Foundations and algorithmsActa Numerica, 2020
- Perspectives on CUR decompositionsApplied and Computational Harmonic Analysis, 2020
- Data-Driven Sparse Sensor Placement for Reconstruction: Demonstrating the Benefits of Exploiting Known PatternsIEEE Control Systems, 2018
- A New Notion of Effective Resistance for Directed Graphs—Part II: Computing ResistancesIEEE Transactions on Automatic Control, 2015
- Kron Reduction of Graphs With Applications to Electrical NetworksIEEE Transactions on Circuits and Systems I: Regular Papers, 2012
- CUR matrix decompositions for improved data analysisProceedings of the National Academy of Sciences, 2009
- The reverse order law revisitedLinear Algebra and its Applications, 1986