In
mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, a block matrix pseudoinverse is a formula for the
pseudoinverse
In mathematics, and in particular, algebra, a generalized inverse (or, g-inverse) of an element ''x'' is an element ''y'' that has some properties of an inverse element but not necessarily all of them. The purpose of constructing a generalized inv ...
of a
partitioned matrix. This is useful for decomposing or approximating many algorithms updating parameters in
signal processing
Signal processing is an electrical engineering subfield that focuses on analyzing, modifying and synthesizing ''signals'', such as audio signal processing, sound, image processing, images, Scalar potential, potential fields, Seismic tomograph ...
, which are based on the
least squares
The method of least squares is a mathematical optimization technique that aims to determine the best fit function by minimizing the sum of the squares of the differences between the observed values and the predicted values of the model. The me ...
method.
Derivation
Consider a column-wise partitioned matrix:
:
If the above matrix is full column rank, the
Moore–Penrose inverse
In mathematics, and in particular linear algebra, the Moore–Penrose inverse of a matrix , often called the pseudoinverse, is the most widely known generalization of the inverse matrix. It was independently described by E. H. Moore in 1920, Ar ...
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
In linear algebra and functional analysis, a projection is a linear transformation P from a vector space to itself (an endomorphism) such that P\circ P=P. That is, whenever P is applied twice to any vector, it gives the same result as if it we ...
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
In linear algebra, the singular value decomposition (SVD) is a Matrix decomposition, factorization of a real number, real or complex number, complex matrix (mathematics), matrix into a rotation, followed by a rescaling followed by another rota ...
,
QR decomposition
In linear algebra, a QR decomposition, also known as a QR factorization or QU factorization, is a decomposition of a matrix ''A'' into a product ''A'' = ''QR'' of an orthonormal matrix ''Q'' and an upper triangular matrix ''R''. QR decom ...
, or
Cholesky decomposition
In linear algebra, the Cholesky decomposition or Cholesky factorization (pronounced ) is a decomposition of a Hermitian, positive-definite matrix into the product of a lower triangular matrix and its conjugate transpose, which is useful for eff ...
to replace the matrix inversions with numerical routines. In a large system, we may employ
iterative methods
In computational mathematics, an iterative method is a Algorithm, mathematical procedure that uses an initial value to generate a sequence of improving approximate solutions for a class of problems, in which the ''i''-th approximation (called an " ...
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