In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a block matrix pseudoinverse is a formula for the
pseudoinverse of a
partitioned matrix. This is useful for decomposing or approximating many algorithms updating parameters in
signal processing, which are based on the
least squares
The method of least squares is a standard approach in regression analysis to approximate the solution of overdetermined systems (sets of equations in which there are more equations than unknowns) by minimizing the sum of the squares of the res ...
method.
Derivation
Consider a column-wise partitioned matrix:
:
If the above matrix is full rank, the
Moore–Penrose inverse 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
:
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
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
External links
The Matrix Reference Manualb
b
John BurkardtThe Matrix Cookbookb
Kaare Brandt PetersenLecture 8: Least-norm solutions of undetermined equationsb
Stephen P. Boyd
{{DEFAULTSORT:Block Matrix Pseudoinverse
Numerical linear algebra
Matrix theory