On recursive calculation of the generalized inverse of a matrix

ABSTRACT

The generalized inverse of a matrix is an extension of the ordinary square matrix inverse which applies to any matrix (e.g., singular, rectangular). The generalized inverse has numerous important applications such as regression analysis, filtering, optimization and, more recently, linear associative memories. In this latter application known as Distributed Associative Memory, stimulus vectors are associated with response vectors and the result of many associations is spread over the entire memory matrix, which is calculated as the generalized inverse. Addition/deletion of new associations requires recalculation of the generalized inverse, which becomes computationally costly for large systems. A better solution is to calculate the generalized inverse recursively. The proposed algorithm is a modification of the well known algorithm due to Rust et al. [2], originally introduced for nonrecursive computation. We compare our algorithm with Greville's recursive algorithm and conclude that our algorithm provides better numerical stability at the expense of little extra computation time and additional storage.

REFERENCES

• 1: T. Kohonen, Self-organization and associative memory: 3rd edition, Springer-Verlag New York, Inc., New York, NY, 1989
• 2: B. Rust , W. R. Burrus , C. Schneeberger, A simple algorithm for computing the generalized inverse of a matrix, Communications of the ACM, v.9 n.5, p.381-385, May 1966 [doi>10.1145/355592.365659]
• 3: BEN-ISRAEL, A., AND GREVILLE, T. N. E. Generalized Inverses Theory and Applicatwns, Wiley, New York, 1974.
• 4: FLETCHER, R. A technique for orthogonalization. J. Inst. Math. Appl. 5 (1969) 162-166.
• 5: GOLUB, G., AND VAN LOAN, C. F. Matrix Computations, The Johns Hopkins University Press, 1983.
• 6: ABDELMALEK, N. N. Roundoff error analysis for Gram-Schmidt methods and solution of linear least squares problem. BIT 11 (1971), 345-368.
• 7: J. M. Char , V. Cherkassky , H. Wechsler , G. L. Zimmerman, Distributed and Fault-Tolerant Computation for Retrieval Tasks Using Distributed Associative Memories, IEEE Transactions on Computers, v.37 n.4, p.484-490, April 1988 [doi>10.1109/12.2196]
• 8: Malathi Rio , Harry Wechsler, Fault-tolerant database using distributed associative memories, Information Sciences: an International Journal, v.53 n.1-2, p.135-158, 1991 [doi>10.1016/0020-0255(91)90061-X]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Matrix inversion

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods); Pseudoinverses**
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Performance, Theory

Keywords:
associative data retrieval, associative memory, recursive algorithm