Pseudo-Inverse Algorithm

A Pseudo-Inverse Algorithm is a Matrix Decomposition Algorithm that can solve a least square system such that each column vector of the solution has a minimum norm.

• AKA: Moore-Penrose Inverse Algorithm, Generalized Inverse Algorithm.
• Example(s):
  • a Bose-Nguyen Generalized Inverse Algorithm (Bose & Nguyen, 2016),
  • a Weighted Pseudo-Inverse Algorithm (Shao et al., 2015),
  • a Online PseudoInverse Update Method (OPIUM) Algorithm (Tapson & Schaik, 2013),
  • a Courrieu's Fast Moore-Penrose Inverse Algorithm (Courrieu (2008)),
  • a Fast B-Spline Pseudo-inversion Algorithm (Tristan & Arribas, 2007),
  • a Herron's Pseudo-Inverse Algorithm (Herron, 1966),
  • a Greville's Pseudo-Inverse Algorithm (Greville, 1960).
  • …
• Counter-Example(s):
  • a Matrix Multiplication Algorithm such as:
    • Coppersmith-Winograd Algorithm;
    • Strassen Algorithm,
  • a Matrix Normalization Algorithm,
  • a Gram-Schmidt Algorithm,
  • a Householder Algorithm.
• See: Function Fitting Algorithm, Pseudoinverse Matrix, Matrix Decomposition, QR Factorization, Singular Value Decomposition.

---

---

References

2019

• (Wikipedia, 2019) ⇒ https://en.wikipedia.org/wiki/Moore–Penrose_inverse Retrieved:2019-7-11.
  • In mathematics, and in particular linear algebra, a pseudoinverse A⁺ of a matrix A is a generalization of the inverse matrix. The most widely known type of matrix pseudoinverse is the Moore–Penrose inverse,which was independently described by E. H. Moore in 1920, Arne Bjerhammar in 1951, and Roger Penrose in 1955. Earlier, Erik Ivar Fredholm had introduced the concept of a pseudoinverse of integral operators in 1903. When referring to a matrix, the term pseudoinverse, without further specification, is often used to indicate the Moore–Penrose inverse. The term generalized inverse is sometimes used as a synonym for pseudoinverse.

    A common use of the pseudoinverse is to compute a "best fit" (least squares) solution to a system of linear equations that lacks a unique solution (see below under § Applications).

    Another use is to find the minimum (Euclidean) norm solution to a system of linear equations with multiple solutions. The pseudoinverse facilitates the statement and proof of results in linear algebra.

    The pseudoinverse is defined and unique for all matrices whose entries are real or complex numbers. It can be computed using the singular value decomposition.

2016

• (Kadiam Bose & Nguyen, 2016) ⇒ S. Kadiam Bose, and D. T. Nguyen. (2016). “Efficient Generalized Inverse for Solving Simultaneous Linear Equations.” In: Journal of Applied Mathematics and Physics, 4. doi:10.4236/jamp.2016.41003
  • QUOTE: The generalized (or pseudo) inverse of a matrix is an extension of the ordinary/regular square (non-singular) matrix inverse, which can be applied to any matrix (such as singular, rectangular etc.). The generalized inverse has numerous important engineering and sciences applications. Over the past decades, generalized inverses of matrices and its applications have been investigated by many researchers 1-6. Generalized inverse is also known as “Moore-Penrose inverse” or “g-inverse” or “pseudo-inverse” etc.

     In this paper we introduce an efficient (in terms of computational time and computer memory requirement) generalized inverse formulation to solve SLE with full or deficient rank of the coefficient matrix. The coefficient matrix can be singular/non-singular, symmetric/unsymmetric, or square/rectangular. Due to popular MATLAB software, which is widely accepted by researchers and educators worldwide, the developed code from this work is written in MATLAB language.

2015

• (Shao et al., 2015) ⇒ Xingyue Shao, Zixuan Liang, Bai Chen, and Cunjia Liu. (2015). “A Modified Weighted Pseudo-inverse Control Allocation Using Genetic Algorithm.” In: Proceedings of 34th Chinese Control Conference (CCC 2015).. doi:10.1109/ChiCC.2015.7260507

2013

• (Tapson & Van Schaik, 2013) ⇒ J. Tapson, and A. Van Schaik. (2013). “2013 Special Issue: Learning the Pseudoinverse Solution to Network Weights.” In: Neural Networks Journal, 45. doi:10.1016/j.neunet.2013.02.008
  • QUOTE: The solution to the network weights is exactly the same as that which would be calculated by singular value decomposition. It converges with a single forward iteration per input data sample, and as such is ideal for realtime online computation of the pseudoinverse solution. It requires significantly less memory than the SVD method, as its memory requirement scales as the square of the size of the hidden layer, whereas the SVD memory requirement scales with the product of the hidden layer size and the size of the training data set. Given that the data set size should significantly exceed the hidden layer size, the former is advantageous. We call the algorithm OPIUM (Online PseudoInverse Update Method).

     OPIUM is adapted from an iterative method for computing the pseudoinverse, known as Greville’s method (Greville, 1960). The existence of OPIUM, and its biological plausibility, suggests that there is no reason why a biological neural network would not arrive at the same weights that are computed using a singular value decomposition, and therefore that this method of synthesizing network structures may be used without the fear that it is biologically implausible.

2008

• (Courrieu, 2008) ⇒ Pierre Courrieu. (2008). “Fast Computation of Moore-Penrose Inverse Matrices .” In: Neural Information Processing - Letters and Reviews Journal, 8.
  • QUOTE: The Moore-Penrose inverse, also called Pseudoinverse, or Generalized Inverse, allows for solving least square systems, even with rank deficient matrices, in such a way that each column vector of the solution has a minimum norm, which is the desired property stated above.

2007

• (Tristán & Arribas, 2007) ⇒ Antonio Tristán, and Juan Ignacio Arribas. (2007). “A Fast B-spline Pseudo-inversion Algorithm for Consistent Image Registration.” In: Proceedings of the 12th International Conference on Computer analysis of images and patterns. ISBN:978-3-540-74271-5

1966

• (Herron, 1966) ⇒ Christopher R. Herron (1966). "Computing the pseudo-inverse".
  • QUOTE: An orthogonalization algorithm for producing the pseudoinverse of a matrix is described, and a FORTRAN program which realizes the algorithm is given in detail.

1965

• (Golub & Kahan, 1965) ⇒ G. Golub and W. Kahan. (1965). “Calculating the Singular Values and Pseudo-Inverse of a Matrix.” In: Journal of the Society for Industrial and Applied Mathematics: Series B, Numerical Analysis, 2(2).

1960

• (Greville,1960) ⇒ T. N. E. Greville (1960). "Some applications of the pseudoinverse of a matrix". SIAM review, 2(1), 15-22.

1955

• (Penrose, 1955) ⇒ Roger Penrose (1955, July). "A generalized inverse for matrices". In Mathematical proceedings of the Cambridge philosophical society (Vol. 51, No. 3, pp. 406-413). Cambridge University Press.

---