Block matrix pseudoinverse
In mathematics, block matrix pseudoinverse is a formula of pseudoinverse of a partitioned matrix. This is useful for decomposing or approximating many algorithms updating parameters in signal processing, which are based on least squares method.
Derivation
Consider a column-wise partitioned matrix:
If the above matrix is full rank, the Moore–Penrose pseudoinverse matrices of it and its transpose are
This computation of the pseudoinverse requires (n + p)-square matrix inversion and does not take advantage of the block form.
To reduce computational costs to n- and p-square matrix inversions and to introduce parallelism, treating the blocks separately, one derives [1]
where orthogonal projection matrices are defined by
The above formulas are not necessarily valid if does not have full rank – for example, if , then
Application to least squares problems
Given the same matrices as above, we consider the following least squares problems, which appear as multiple objective optimizations or constrained problems in signal processing. Eventually, we can implement a parallel algorithm for least squares based on the following results.
Column-wise partitioning in over-determined least squares
Suppose a solution solves an over-determined system:
Using the block matrix pseudoinverse, we have
Therefore, we have a decomposed solution:
Row-wise partitioning in under-determined least squares
[Comment re. below: According to section "Derivation" above this method of calculating [A, B]+ for m>=n+p. Can it then be used for an underdetermined system where by definition m (size of x and equal to number of variables) > n+p (number of equations)?]
Suppose a solution solves an under-determined system:
The minimum-norm solution is given by
Using the block matrix pseudoinverse, we have
Comments on matrix inversion
Instead of , we need to calculate directly or indirectly
In a dense and small system, we can use singular value decomposition, QR decomposition, or Cholesky decomposition to replace the matrix inversions with numerical routines. In a large system, we may employ iterative methods such as Krylov subspace methods.
Considering parallel algorithms, we can compute and in parallel. Then, we finish to compute and also in parallel.
See also
References
- ↑ J.K. Baksalary and O.M. Baksalary (2007). "Particular formulae for the Moore–Penrose inverse of a columnwise partitioned matrix". Linear Algebra Appl. 421: 16–23. doi:10.1016/j.laa.2006.03.031.
External links
- The Matrix Reference Manual by Mike Brookes
- Linear Algebra Glossary by John Burkardt
- The Matrix Cookbook by Kaare Brandt Petersen
- Lecture 8: Least-norm solutions of undetermined equations by Stephen P. Boyd