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?
 A: 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.
A: 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.
A: 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.
A: Yes, they are connected.

*

*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:


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