Source-linked AI summary
Fast Computation of Moore-Penrose Inverse Matrices
Pierre Courrieu
TL;DR
Large least-square systems in neural learning require solutions that remain useful when the system matrix is rank deficient, while minimum-norm weights support regularization. The paper proposes a Moore-Penrose inverse algorithm based on full-rank Cholesky factorization and reports substantially shorter computation time, particularly for large systems. The method is most relevant when rank deficiency is possible, since simpler least-square solutions apply otherwise.
Problem
Neural learning needs large least-square systems solved under possible rank deficiency, with minimum-norm synaptic-weight solutions that contribute to input-output regularization.
Method
The paper computes Moore-Penrose inverses using a full-rank Cholesky factorization of possibly singular symmetric positive matrices, combined with a reverse order law.
Results
The proposed pseudoinverse matrices are similar to those from other algorithms, while computation time is substantially shorter, particularly for large systems.
Takeaways & Limitations
The approach supports fast solution of large rank-deficient least-square systems and minimum-norm weights for neural-learning applications.
Takeaways & Limitations
When rank deficiency is not a risk, simpler least-square methods are available, so using the proposed tool depends on the basis-function choice.
Abstract
from arXiv · showhide
Many neural learning algorithms require to solve large least square systems in order to obtain synaptic weights. Moore-Penrose inverse matrices allow for solving such systems, even with rank deficiency, and they provide minimum-norm vectors of synaptic weights, which contribute to the regularization of the input-output mapping. It is thus of interest to develop fast and accurate algorithms for computing Moore-Penrose inverse matrices. In this paper, an algorithm based on a full rank Cholesky factorization is proposed. The resulting pseudoinverse matrices are similar to those provided by other algorithms. However the computation time is substantially shorter, particularly for large systems.
1. Introduction
Neural learning uses least-square systems to obtain synaptic weights, but rank deficiency makes solutions nonunique and can affect regularization. The paper motivates a fast Moore-Penrose inverse algorithm for this setting.
- Least-square minimization is commonly used in feed-forward neural-network learning algorithms.
- Rank deficiency makes the least-square solution nonunique and potentially dependent on the solution method or algorithmic random variables.The cited passage mentions initial conditions and search parameters as possible sources of variation.
- The Moore-Penrose inverse solves least-square systems with rank-deficient matrices while selecting minimum-norm solution columns.Minimum-norm weights are presented as desirable for regularizing the input-output mapping.
- For full-rank G, the Moore-Penrose inverse reduces to the usual pseudoinverse expression.The supplied formula is G+ = (G’G )-1 G’.
- Existing approaches include SVD, Greville’s algorithm, full-rank QR factorization, iterative methods, and expansion-based algorithms.SVD is described as accurate but time-consuming for large matrices.
- The paper proposes a fast Moore-Penrose inverse algorithm based on a reverse order law and full-rank Cholesky factorization of possibly singular symmetric positive matrices.
2. Algorithm Foundations
The algorithm factors G’G with a rank-aware Cholesky procedure, removes zero rows to form a full-rank factor, and derives G+ through matrix-product identities. Its implementation centers on Cholesky factorization and inversion of L’L.
- A rank-r symmetric positive matrix G’G is factored as S’S, where S has n − r zero rows and a unique upper-triangular form.The factorization extends ordinary Cholesky factorization to possibly singular matrices.
- Removing S’s zero rows yields a full-rank r × n matrix L’.
- The method uses a general Moore-Penrose inverse relation for matrix products together with a condition involving B = A’ and rank r.
- Theorem 1 expresses G+ through L, (L’L)-1, and G’, establishing the proposed pseudoinverse construction.
- The Matlab geninv function returns the Moore-Penrose inverse of any rectangular matrix using full-rank Cholesky factorization and inversion of L’L.
- On serial processors, the two main operations have complexity orders O(n3) for Cholesky factorization and O(r3) for inversion.The passage states possible parallel reductions to O(n) and O(log r), respectively.
3. Computational Test
The proposed geninv method was tested against four established Moore-Penrose inverse algorithms on large, rank-deficient matrices. All methods achieved highly accurate approximations, while the test records computation time as matrix size increased.
- Algorithms and test setup: The test compared geninv with Greville's method, SVD, full-rank QR factorization, and an optimized-order iterative method.The matrices were rectangular, rank deficient, and generated with real random coefficients.
- Algorithms and test setup: The experiments used matrices with n = 2^k, k = 10..15, m = 2n, and rank r = 7n / 8.Accuracy was evaluated using error matrices corresponding to the four Moore-Penrose properties.
- Accuracy: 2 x 10^-10 was the largest absolute error coefficient observed for every algorithm and test matrix.The result indicates reliable numerical approximations under the tested conditions.
- Computation time: Table 1 reports computation time in seconds as a function of matrix size for the four algorithms and geninv.Its caption specifies random rectangular rank-deficient real matrices and the same error bound for all cases.
4. Application Fields
The proposed tool targets neural learning settings where least-square systems may be rank deficient or ill-conditioned. Its implementation uses a full-rank Cholesky factorization, while its usefulness is bounded when rank deficiency is not a concern.
- Neural learning applications: The proposed tool computes Moore-Penrose inverses and solves large least-square systems, including systems with rank-deficient matrices.The implementation is provided as the Matlab geninv function.
- Neural learning applications: In rank-deficient learning problems, the resulting solution has minimum norm and contributes to regularizing the input-output mapping.This property is presented as an advantage for learning processes.
- Scope and conditions: When rank deficiency is unlikely, simpler least-square methods may be preferable, so use of the proposed tool depends on the basis-function choice.The paper also discusses near-linear dependence as a source of ill-conditioning.
- Neural learning applications: Fast Moore-Penrose inverse computation supports neurocomputational learning procedures because existing fast updating procedures do not support rank deficiency or later basis-function modification.The paper notes that rescaling Radial Basis Functions can be desirable as network size increases.
- Implementation: The geninv implementation computes the inverse using a full-rank Cholesky factorization of a matrix formed from G and its transpose.The code uses G*G' when m < n and G'*G otherwise.