Is the pseudoinverse the same as least squares with regularization?

Question

Given a linear system $Ax=b$, the pseudoinverse of $A$ is found as the matrix $A^+$ such that $x=A^+ b$ where $x$ solves the least squares problem $\min \| Ax - b \|^2 $ and $x \perp \mathcal{N}(A)$. That is, $x$ is the shortest vector in the solution space.

That is, find $x$ : \begin{eqnarray} \min \| x \| \text{ such that } x \text{ minimizes } \| Ax - b \|^2 . \end{eqnarray}

This is similar to the regularization problem of minimizing \begin{eqnarray} \| Ax - b \|^2 + \lambda \| x \|^2 \end{eqnarray} I do not quite can get from one to the other? Are these two things equivalent? Is there a way to post this as the same problem? Is there a connection?

Answer 1

Here's one way to see this directly. I will assume that $A$ is $m \times n$. Let $$ A = U \Sigma V^T$$ be the SVD for A. Recall that the regularized solution to the least squares problem $Ax = b$ is given by $$\hat{x} = (A^TA + \lambda I)^{-1}A^Tb.$$ Now substitute the SVD of $A$ in place of $A$. Simplifying algebra, we get that $$\hat{x} = V(\Sigma^T \Sigma + \lambda I)^{-1} \Sigma^T U^T b. \hspace{1cm} (\ast) $$ OTOH, the solution by considering the pseudoinverse is given by $$ A^+b = V\Sigma^+ U^Tb.\hspace{3cm} (\ast\ast) $$ Therefore, $(\ast)$ and $(\ast \ast)$ are equivalent (in the limit) if $$\Sigma^+ = \lim_{\lambda \to 0} (\Sigma^T \Sigma + \lambda I)^{-1} \Sigma^T.$$

Without referring to the arxiv preprint in G. Fougeron's answer, let us show this as follows. Let $\sigma_1,\ldots, \sigma_r$ be the singular values of $A$. By direct computation, we find that $\Sigma^T \Sigma + \lambda I $ is the $n \times n$ diagonal matrix given by $$ \Sigma^T \Sigma + \lambda I = \begin{pmatrix} \sigma_1^2 + \lambda & \\ & \ddots \\ && \sigma_r^2 + \lambda \\ &&& \lambda \\ &&&& \ddots \\ &&&&&\lambda \end{pmatrix}$$

Since this is diagonal, it is easy to invert and therefore $ (\Sigma^T \Sigma + \lambda I)^{-1}\Sigma^T$ is given explicitly as the $n \times m$ matrix

$$(\Sigma^T \Sigma + \lambda I)^{-1}\Sigma^T = \left(\begin{array}{ccc|cc} \frac{\sigma_1}{\sigma_1^2 + \lambda} & \\ & \ddots &&&0 \\ && \frac{\sigma_r}{\sigma_r^2 + \lambda} \\ \hline &&& \\ &0&&& 0 \\ &&&&& \end{array}\right). $$ with top-left block a digonal $r \times r$ matrix. In the limit as $\lambda \to 0$, the top-left block is just $$\begin{pmatrix} \frac{1}{\sigma_1} \\ &\ddots\\ && \frac{1}{\sigma_r} \end{pmatrix} $$ and hence the entire matrix is just $\Sigma^+$ as desired.

Answer 2

Yes, they are connected.

1. The first problem is a special case of the second when $\lambda=0$, if the first problem has a unique solution (i.e., $\ker A = 0$), or if the second is also formulated as a double minimization "$\min \|x\|$ such that $x$ minimizes $\|Ax-b\|^2+\lambda \|x\|^2$".

But there is also a reduction in the other direction:

2. The second problem is a special case of the first with slightly different matrices, because $$ \| Ax - b \|^2 + \lambda \| x \|^2 = \left\| \begin{bmatrix} A\\ \sqrt{\lambda}I \end{bmatrix} x - \begin{bmatrix}b\\0\end{bmatrix} \right\|^2. $$ This reduction works without imposing any additional conditions, because $\ker \begin{bmatrix} A\\ \sqrt{\lambda}I \end{bmatrix} = 0$ always (thanks to that full-rank second block). So if you have an algorithm to solve full-rank least-squares problems you can also apply it to solve Tikhonov-regularized least-squares problems.

EDIT: made additional conditions clearer to answer the comments.

Answer 3

TL;DR : Yes, the two problems are equivalent in the limit $\lambda \rightarrow 0$ !

One freely available reference is the following (excellent in my opinion) review paper : https://arxiv.org/abs/1110.6882

Specifically, your question is addressed on Theorem 4.3 of this paper on Tikhonov’s Regularization.

Answer 4

As usual with such problems, it is most insightful to forget about matrices for a while and think about abstract vector spaces instead.

Let $V$ and $W$ vector spaces and $A: V\to W$ linear^†. Furthermore let $d_V$ and $d_W$ be metrics on each of the spaces.

Now, given $b\in W$, we have two convex functions $\zeta_V, \zeta_b: V\to\mathbb{R}^+$: $$\begin{align} \zeta_V(v) =& d_V(v,\vec0) \\ \zeta_b(v) =& d_W(A\:v, b) \end{align}$$

The point of the Tikhonov problem is to make a tradeoff between these two cost functions, i.e. you minimise $$ \zeta_\lambda := \zeta_b(v) + \lambda\cdot\zeta_V(v). $$ But why would you want that? Basically, $\zeta_b$ is what we really care for, because it tells us by how much we're missing our target point. The problem is when $A$ fails to be injective, because in that case $\zeta_b$ will not be strictly convex and you have a whole set of solutions $\Xi_b\subset V$ on which $\zeta_b$ is minimised – some of which are very bad solutions, in the sense of, unbounded as visible by huge $d_V$ values.
Those solutions can be eliminated by even an arbitrarily small $\lambda$, because $\zeta_b$ is constant on $\Xi_b$. So, in the limit $\lambda\to 0$, you're only really minimising $\zeta_b$, but still preventing solutions that have a needlessly big norm in $V$.

In actual applications though, you're already in trouble even if $A$ is injective but badly conditioned, i.e. when there are $v\in V$ for which $d_W(A\:v,\vec0)$ happens to be very small. Because then, just a small bit of measurement noise on $b$ could cause the minimum of $\zeta_b$ to be thrown off by a big amount, even though the actual cost is barely changed. That can still be prevented by the $\zeta_V$ contribution, but in this case you can't make $\lambda$ arbitrarily small anymore but have to select an application-appropriate finite value.

---

^†_{Really, there's no reason for $W$ to actually be a vector space, it could as well be any metric space – but only for affine spaces and affine mappings can the problem be solved so easily.}