# Is the pseudoinverse the same as least squares with regularization?

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?

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.

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:

1. 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.

• When $\lambda=0$ the second does not reduce to the first, if the null space of $A$ is not the trivial. That is, if the columns of $A$ are linearly dependent, the least square problem does not have unique solution and we need to solve, in addition the $\min \| x \|$ problem. I understand your second equation but this does not show that $x \perp \mathcal{N}(A)$ as it should be if we are finding the pseudo-solution. Feb 25, 2021 at 22:12
• $\begin{bmatrix}A \\ \sqrt{\lambda} I\end{bmatrix}$ always has trivial nullspace, because of that identity block. Feb 25, 2021 at 22:29
• Beautiful reduction. But I think @HermanJaramillo has a point: you are proving that minimizing the LHS is equivalent to minimizing the RHS. But when $\lambda=0$ the original problem is not simply to minimize the LHS (which may have infinite solutions) but to pick the unique shortest minimizer. Feb 25, 2021 at 23:57
• @YaakovBaruch I agree; but this can be fixed by agreeing that the second problem is also formulated a double minimization "$\min \|x\|$ such that $x$ minimizes...". Indeed the second problem is not stated formally as well as the first in the original question; just the objective function appears. (That formulation, however, may be considered a bit artificial, because the minimizer of $\|Ax-b\|^2+\lambda \|x\|^2$ is unique unless $\lambda=0$.) Feb 26, 2021 at 7:05

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.

• @Fougeron: I am looking at the link. You hit right on the head. That is the answer to my questions. Thanks again. Feb 25, 2021 at 22:45

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.