# Fast and Accurate Pseudoinverse with Sparse Matrix Reordering and Incremental Approach

arXiv: https://arxiv.org/abs/2011.04235 · HTML: https://mlsanity.com/paper/2011.04235/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Nov 2020.

## Built on by (most cited first, 3 of 3)

- [NeuKron: Constant-Size Lossy Compression of Sparse Reorderable Matrices and Tensors](https://mlsanity.com/paper/2302.04570/) (2023)
- [Effective and Lightweight Representation Learning for Link Sign Prediction in Signed Bipartite Graphs](https://mlsanity.com/paper/2412.18720/) (2024)
- [Structure-Attribute Transformations with Markov Chain Boost Graph Domain Adaptation](https://mlsanity.com/paper/2509.21059/) (2025)

## Abstract (arXiv)

How can we compute the pseudoinverse of a sparse feature matrix efficiently and accurately for solving optimization problems? A pseudoinverse is a generalization of a matrix inverse, which has been extensively utilized as a fundamental building block for solving linear systems in machine learning. However, an approximate computation, let alone an exact computation, of pseudoinverse is very time-consuming due to its demanding time complexity, which limits it from being applied to large data. In this paper, we propose FastPI (Fast PseudoInverse), a novel incremental singular value decomposition (SVD) based pseudoinverse method for sparse matrices. Based on the observation that many real-world feature matrices are sparse and highly skewed, FastPI reorders and divides the feature matrix and incrementally computes low-rank SVD from the divided components. To show the efficacy of proposed FastPI, we apply them in real-world multi-label linear regression problems. Through extensive experiments, we demonstrate that FastPI computes the pseudoinverse faster than other approximate methods without loss of accuracy. %and uses much less memory compared to full-rank SVD based approach. Results imply that our method efficiently computes the low-rank pseudoinverse of a large and sparse matrix that other existing methods cannot handle with limited time and space.