This is an old revision of this page, as edited by Cg78ithaca wiki(talk | contribs) at 18:55, 21 September 2015(Question regarding use of theoretical developments presented in previous section.). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.Revision as of 18:55, 21 September 2015 by Cg78ithaca wiki(talk | contribs)(Question regarding use of theoretical developments presented in previous section.)
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 pseudoinverse matrices of it and its transpose are as follows.
The pseudoinverse requires (n + p)-square matrix inversion.
To reduce complexity and introduce parallelism, we derive the following decomposed formula. From a block matrix inverse, we can have[citation needed]
Interestingly, from the idempotence of projection matrix, we can verify that the pseudoinverse of block matrix consists of pseudoinverse of projected matrices:
Thus, we decomposed the block matrix pseudoinverse into two submatrix pseudoinverses, which cost n- and p-square matrix inversions, respectively.
Note that the above formulae 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:
Considering parallel algorithms, we can compute and
in parallel. Then, we finish to compute and also in parallel.
Block matrix inversion
Let a block matrix be
We can get an inverse formula by combining the previous results in.[1]
where and , respectively, Schur complements of
and , are defined by , and . This relation is derived by using Block Triangular
Decomposition. It is called simple block matrix inversion.[2]
Now we can obtain the inverse of the symmetric block matrix:
Since the block matrix is symmetric, we also have
Then, we can see how the Schur complements are connected to the projection matrices of the symmetric, partitioned matrix.