Is the pseudoinverse the same as least squares with regularization?

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.

EDIT: made additional conditions clearer to answer the comments.


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.


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.