Optimization Models
Home
Software
Links
Index
Contact
1. Introduction
1.1. Overview
1.2. Optimization Models
2. Linear Algebra
2.1. Vectors
2.2. Matrices
2.3. Linear Equations
2.4.  Least-Squares
2.5. Eigenvalues
2.6  Singular Values
3. Convex Models
3.1. Convexity
3.2. LP and QP
3.3. SOCP
3.4. Robust LP
3.5. GP
3.6. SDP
3.7. Non-Convex Models
4. Duality
4.1. Weak Duality
4.2. Strong Duality
4.3.  Applications
5. Case Studies
5.1. Senate Voting
5.2. Antenna Arrays
5.3. Localization
5.4. Circuit Design

Pseudo-Inverse of a Matrix

The pseudo-inverse of a m times n matrix A is a matrix that generalizes to arbitrary matrices the notion of inverse of a square, invertible matrix. The pseudo-inverse can be expressed from the singular value decomposition (SVD) of A, as follows.

Let the SVD of A be

A = U left( begin{array}{cc} S & 0 0 & 0 end{array} right)V^T,

where U,V are both orthogonal matrices, and S is a diagonal matrix containing the (positive) singular values of A on its diagonal.

Then the pseudo-inverse of A is the n times m matrix defined as

A^dagger = V left( begin{array}{cc} S^{-1} & 0 0 & 0 end{array} right)U^T.

Note that A^dagger has the same dimension as the transpose of A.

This matrix has many useful properties:

  • If A is full column rank, meaning mbox{bf rank}(A) = n le m, that is, A^TA is not singular, then A^dagger is a left inverse of A, in the sense that A^dagger A = I_n. We have the closed-form expression

A^dagger = (A^TA)^{-1}A^T.

  • If A is full row rank, meaning mbox{bf rank}(A) = m le n, that is, AA^T is not singular, then A^dagger is a right inverse of A, in the sense that AA^dagger = I_m. We have the closed-form expression

A^dagger = A^T(AA^T)^{-1}.

  • If A is square, invertible, then its inverse is A^dagger = A^{-1}.

  • The solution to the least-squares problem

min_x : |Ax-y|_2

with minimum norm is x^ast = A^dagger y.

Example: pseudo-inverse of a 4 times 5 matrix.