19
$\begingroup$

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?

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
5
  • 5
    $\begingroup$ Hi, I'm new to linear algebra. Could the downvoter please identify what issues this answer has? It seems fine to me, so I would appreciate knowing where my knowledge is off. $\endgroup$ Feb 25 at 22:07
  • 1
    $\begingroup$ @Ben Lim: Thanks, I like your approach. $\endgroup$ Feb 25 at 22:17
  • 1
    $\begingroup$ @Ben Linn: I keep looking at your solution and it looks great. I derived all the things that you have here but did not connect well the dots. I ask the same question. Why would anybody down vote you? I would like to see where the problem is in your analysis. $\endgroup$ Feb 25 at 22:58
  • 1
    $\begingroup$ Not all downvotes are on purpose. Sometimes it's just someone's phone in a pocket. $\endgroup$
    – user1504
    Feb 26 at 0:54
  • $\begingroup$ @Benn Linn: How do I accept the answer, other than up vote it? $\endgroup$ Feb 26 at 2:37
10
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Feb 25 at 22:12
  • $\begingroup$ $\begin{bmatrix}A \\ \sqrt{\lambda} I\end{bmatrix}$ always has trivial nullspace, because of that identity block. $\endgroup$ Feb 25 at 22:29
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 25 at 23:57
  • $\begingroup$ @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$.) $\endgroup$ Feb 26 at 7:05
8
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Fourgeron : thanks for the link. That is useful. $\endgroup$ Feb 25 at 22:15
  • $\begingroup$ @Fougeron: I am looking at the link. You hit right on the head. That is the answer to my questions. Thanks again. $\endgroup$ Feb 25 at 22:45
3
$\begingroup$

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.

$\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.