Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How to prove that if you have $x^*$ such that $x^*=\text{psuedoinverse}(A) b$, and $Ay=b$, then $$\Vert x^* \Vert_2 \leq \Vert y \Vert_2$$

share|improve this question
    
Some people define the pseudoinverse as the mapping that takes $b$ as input and returns the vector $x$ of least norm such that $Ax=\hat{b}$, where $\hat{b}$ is the projection of $b$ onto the range of $A$. Formulas for the pseudoinverse are then derived from this more conceptual definition. –  littleO Oct 27 '12 at 23:57
    
@Marcus. You don't specify, but should it be assumed that $A$ has more columns than rows and has full row rank? –  Daryl Oct 28 '12 at 8:29

3 Answers 3

up vote 0 down vote accepted

Let me try a one liner solution.

$Ay=b$ $\Rightarrow$ $A(y-x^*)=0$ $\Rightarrow$ $\langle x^*,y-x^*\rangle=0$ $\Rightarrow$ $\|y\|^2=\|y-x^*\|^2+\|x\|^2\ge \|x\|^2$.

Remark. $R=A^t(AA^t)^{-1}$, $x^*=Rb$. Then we have $\langle x^*,y-x^*\rangle=\langle Rb,y-x^*\rangle=$ $\langle (AA^t)^{-1}b,A(y-x^*)\rangle=0$.

share|improve this answer

Let $A: \mathbb{U} \mapsto \mathbb{V}$, then in terms of SVD, we can write $A$ as $$A=\sum_{n=1}^R\sigma_nv_nu_n^{\dagger},$$ where $\sigma_n$ is a nonzero singular value; $u_n$ and $v_n$ are the right and left singular vector, respectively; $R$ is the rank of $A$.

Since {$u_n$} form an orthonormal basis of $\mathbb{U}$, we can expand $y$ as $$y=\sum_{m=1}^M\alpha_m u_m,$$ where $M\ge R$ is the dimension of $\mathbb{U}$.

So $$b=Af=\sum_{n=1}^R\sigma_nv_nu_n^{\dagger}\sum_{m=1}^M\alpha_mu_m=\sum_{n=1}^R\alpha_n\sigma_nv_n$$

Also, the pseudoinverse is $$A^+=\sum_{m=1}^R\frac{1}{\sigma_m}u_mv_m^{\dagger}$$

Then $$x^*=A^+b=\sum_{m=1}^R\frac{1}{\sigma_m}u_mv_m^{\dagger}\sum_{n=1}^R\alpha_n\sigma_nv_n=\sum_{m=1}^R\alpha_mu_m$$.

Finally, we can see that $$\|y||_2=(\sum_{m=1}^M\alpha_m^2)^{1/2},$$ $$\|x^*||_2=(\sum_{m=1}^R\alpha_m^2)^{1/2}.$$ Therefore, $$\|x^*||_2 \le \|y||_2,$$ where equality holds when $M=R$ or $\alpha_m=0$ for $m=R+1, \cdots, M$.

In other words, if we define $$\|y_{null}\|_2=(\sum_{m=R+1}^M\alpha_m^2)^{1/2},$$ we have $$\|y\|_2^2=\|x^*||_2^2+\|y_{null}\|_2^2.$$

share|improve this answer

You essentially want to find the solution to he following optimization problem. $$\min_{x}\Vert x \Vert_2 \text{ such that } Ax = b$$ Using Lagrange multipliers, we get that $$\min_{x, \lambda} \dfrac{x^Tx}2 + \lambda^T (Ax - b)$$ Differentiate with respect to $x$ and $\lambda$ to get that $$x^* = \underbrace{A^T(AA^T)^{-1}}_{\text{pseudoinverse}}b$$

Proof: $$\dfrac{d \left(\dfrac{x^Tx}2 + \lambda^T (Ax - b) \right)}{dx} = 0 \implies x^* + A^T \lambda = 0 \implies x^* = -A^T \lambda$$ We also have $$Ax^* = b \implies AA^T \lambda = -b \implies \lambda = - \left( AA^T\right)^{-1}b$$ Hence, $$x^* = \underbrace{A^T(AA^T)^{-1}}_{\text{pseudoinverse}}b$$

share|improve this answer
    
But how does that prove that it is less than the 2-norm of y? –  Marcus Oct 27 '12 at 21:29
    
@Marcus We have found the $x$ satisfying $Ax=b$ such that $\Vert x \Vert_2$ is minimum. –  user17762 Oct 27 '12 at 21:30
    
Of course, sorry for being a bit dense there. Thank you –  Marcus Oct 27 '12 at 21:36
    
Your pseudoinverse is only true if $A$ has full row rank, so that $AA^T$ has full rank. (I.e. it is a right inverse of $A$ only.) –  Daryl Oct 28 '12 at 3:46
    
@Daryl True. This is assuming that $A$ has full rank. –  user17762 Oct 28 '12 at 3:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.