2-norm Pseudoinverse Upper Bound

[baggiano]

Hello

I'm trying to show that the following upper bound on the matrix 2-norm is true:

$\left\|(AB)^+\right\|_2\leq\left\|A^+\right\|_2 \left\|B^+\right\|_2$

where + is the matrix pseudoinverse and $A\in\Re^{n\times m}$ and $B\in\Re^{m\times p}$ are full-rank matrices with $n\geq m\geq p$.

Any hint how I can show it?

Thanks in advance!

Bag

 

[Hawkeye18]

Are you sure that $m\ge p$ and not $p\ge m$?
Also I assume that by pseudoinverse you mean the Moore-Penrose pseudoinverse.

If $n\ge m$ and $p\ge m$, then $(AB)^+ =B^+ A^+$ holds, and this identity gives your estimate.

If $n\ge m\ge p$, then $A$, $B$ and so $AB$ are left invertible. For a left invertible matrix $A$, the Moore-Penrose pseudoinverse $A^+$ is the minimal left inverse, $A^{min}_L = (A^*A)^{-1}A^*$.

The minimal left inverse $A^{min}_L$ has the property that for any other left inverse $A_L$ of $A$ we have $A^{min}_L = P_{Ran (A)} A_L$, where $P_{Ran (A)}$ is the orthogonal projection onto the range (column space) of $A$. In particular, this implies that the norm of the minimal left inverse is the minimal possible norm of a left inverse.

Now let us gather all this information together: both $A$ and $B$, are left invertible, so $A^+$ and $B^+$ are the minimal left inverses of $A$ and $B$ respectively. Therefore, $B^+A^+$ is a left inverse of $AB$; generally it is not the minimal left inverse, but the minimality property for the norm of minimal left inverse implies

$\|(AB)^+\| \le \| B^+A^+\| \le\|B^+\|\cdot\|A^+\|$

 

[baggiano]

Hello

Thanks a lot for the details of your illustration.

Yes, $m\geq p$ was actually correct.

In the fourth paragraph of your reply you say that $A_L^{min}=P_{Ran(A)}A_L$. Shouldn't it be $A_L^{min}=A_LP_{Ran(A)}$ instead?

Thanks again!

Bag

 

[Hawkeye18]

Yes, it should be $A_L^{min} = A_L^{min} P_{Ran(A)}$.

 

[blue_raver22]

us

Hello Bagus,

Thank you for your question. It is an interesting problem to consider. To show the upper bound on the matrix 2-norm, we can use the definition of the pseudoinverse and the properties of matrix norms.

First, let's define the pseudoinverse of a matrix A as A+ = (A*A)^(-1)*A^T. This definition is valid for any full-rank matrix A. We can also define the 2-norm of a matrix A as ||A||_2 = \sqrt{\lambda_{max}(A^T*A)}, where \lambda_{max} represents the maximum eigenvalue.

Now, let's consider the matrix (AB)+. Using the definition of the pseudoinverse, we can write (AB)+ = ((AB)*(AB))^(-1)*(AB)^T. Then, we can use the properties of matrix norms to write ||(AB)+||_2 = \sqrt{\lambda_{max}((AB)^T*(AB))}.

Next, let's consider the matrix A+. Using the properties of matrix norms, we can write ||A+||_2 = \sqrt{\lambda_{max}(A^T*A)}. Similarly, we can write ||B+||_2 = \sqrt{\lambda_{max}(B^T*B)}.

Now, we can combine these equations to obtain ||(AB)+||_2 = \sqrt{\lambda_{max}((AB)^T*(AB))} = \sqrt{\lambda_{max}(B^T*A^T*A*B)}.

Since A and B are full-rank matrices, we know that the product A^T*A and B^T*B are also full-rank. This means that their maximum eigenvalues are positive, which allows us to write \lambda_{max}(B^T*A^T*A*B) = \lambda_{max}(B^T*B)*\lambda_{max}(A^T*A).

Substituting this into our equation for ||(AB)+||_2, we get ||(AB)+||_2 = \sqrt{\lambda_{max}(B^T*B)*\lambda_{max}(A^T*A)}.

Finally, using the properties of square roots and maximum eigenvalues, we can write ||(AB)+||_2 = \sqrt{\lambda_{max}(B^T*B)}*\sqrt{\lambda_{max}(A^T*A)}