2
$\begingroup$

for arbitrary matrix $\mathbf A\in \mathbb R^{m \times n}$ and $rank(\mathbf A) = r$, solve the least squares: $$\min \|\mathbf Ax - b\|_2. $$ According to SVD, pseudo inverse of $\mathbf A$ is $$\mathbf A^{\dagger}=\mathbf{V} \mathbf \Sigma^{\dagger} {\mathbf U^T}$$ where $$\mathbf \Sigma^{\dagger}= \begin{bmatrix} \mathbf \Sigma_{r \times r}^{-1} & \mathbf 0 \\ \mathbf 0 & \mathbf 0 \end{bmatrix}_{n \times m}.$$ I get $x = \mathbf A^{\dagger}b$ is the canonical solution $(A^TA)^{-1}A^Tb$ for linear least squares when $m=n=r$. But don't know why it is the solution that minimizes $|x|$.

$\endgroup$
  • $\begingroup$ My favorite definition of the pseudoinverse is that it is the mapping that takes a vector $b$ as input and returns as output the least norm solution to $Ax= \hat b$, where $\hat b$ is the projection of $b$ onto the range of $A$. $\endgroup$ – littleO Dec 4 '18 at 6:14
  • $\begingroup$ See math.stackexchange.com/questions/1816364. $\endgroup$ – Royi Dec 27 '19 at 17:23
1
$\begingroup$

The column space of $A$ is the same as the span of the first $r$ columns of $U$; let $U_r$ be this $m \times r$ matrix. So the projection of $b$ onto the column space of $A$ is $\hat{b} := U_r (U_r^\top U_r)^{-1} U_r^\top b = U_r U_r^\top b$.

If $x$ is a solution to the optimization problem, then $Ax = \hat{b}$.

Thus, we can consider a second optimization problem: minimize $\|x\|_2$ subject to $Ax = \hat{b}$.

First, we check that $x := A^\dagger b$ is feasible, i.e. $A A^\dagger b = \hat{b}$. $$AA^\dagger b = U \Sigma V^\top V \Sigma^\dagger U^\top = U \begin{bmatrix} I_{r \times r} \\ & 0_{m-r \times m-r}\end{bmatrix} U^\top b = U_r U_r^\top b = \hat{b}.$$

Next we justify that it is minimum norm. Note that all other feasible $x$ can be written as $x = A^\dagger b + z$ for some $z$ in the nullspace of $A$. Note that the nullspace of $A$ is the same as the span of the last $n - r$ columns of $V$. On the other hand, $A^\dagger b = V\Sigma^\dagger U b$ lies in the span of the first $r$ columns of $V$. Thus $A^\dagger b$ and $z$ are orthogonal and we have $$\|x\|_2^2 = \|A^\dagger b\|_2^2 + \|z\|_2^2.$$ Thus choosing $z = 0$ minimizes $\|x\|_2$, so $A^\dagger b$ is the minimum norm solution.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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