5
$\begingroup$

I wish to understand linear transformations of the type $M = \left(\alpha I_n+ D^TD\right)^{-1}$

where $\alpha \neq 0$ and $D$ is a (full-rank) $k$ by $n$ matrix. ($k<n$)

My understanding is that though $D^TD$ is singular and thus does not have an inverse, $\left(\alpha I_n+ D^TD\right)^{-1}$ for $\alpha \ll 1$ could be a "good" approximation for it. (or am I mistaken?)

Ideally I would like to relate the eigenvectors of $M$ to my original $D$ (probably dependent also on $\alpha$) (see footnote [1])

So my question is: Is it possible to compute the eigenvalues and eigenvectors of this matrix $M$? Is there any interesting fact that you know about these types of matrices (thinking them of linear transformations)

I tried to use Woodbury identity to arrive at an expression

$$M = \left(\alpha I_n+ D^TD\right)^{-1}\\ =\alpha^{-1}I_n - \alpha^{-1}D^T\left(I_k+\alpha^{-1}DD^T\right)^{-1}D\alpha^{-1}\\ =\alpha^{-1}I_n - \alpha^{-1}D^T\left(\alpha I_k+DD^T\right)^{-1}D\\ = \alpha^{-1}I_n - \alpha^{-1}D^T\left(\alpha^{-1}I_k - \alpha^{-1}D\left(\alpha I_n+D^TD\right)^{-1}D^T\right)D\\ = \alpha^{-1}I_n - \alpha^{-2}D^TD + \alpha^{-2}D^TD\left(\alpha I_n+D^TD\right)^{-1}D^TD\\ = \alpha^{-1}I_n - \alpha^{-2}D^TD + \alpha^{-2}D^TDMD^TD$$

and got to an implicit equation for $M$ but could not solve it.

Any help is appreciated either in finding a closed-form solution or geometrical interpretations of the effect of $M$

[1] Some initial experimentation with simple $D$ lead me to believe that the rows of $D$ are eigenvectors for $M$ is this possible?

$\endgroup$
2
  • 1
    $\begingroup$ If $D^T D$ is singular, then shouldn't your limit fail to exist? $\endgroup$ Nov 15, 2016 at 17:30
  • $\begingroup$ You are right! I will clarify $\endgroup$
    – gota
    Nov 16, 2016 at 22:43

2 Answers 2

5
+25
$\begingroup$

The eigenvalues of $\alpha I + D^TD$ can be written as $\alpha + \lambda_j$, where $\lambda_j$ are the eigenvalues of $D^TD$, of which at least $n-k$ are zero. The eigenvectors of $D^TD$ and $\alpha I+ D^TD$ can be computed by the right-singular vectors of $D$.

The matrix $(\alpha I+D^TD)^{-1}D^T$ is an approximation of the inverse $D$ in the following sense: $\lim_{\alpha \searrow0}(\alpha I+D^TD)^{-1}D^T =D^\dagger$, where $D^\dagger$ is the Moore-Penrose pseudo-inverse of $D$, see Moore-Penrose pseudo-inverse.

The matrix $(\alpha I+D^TD)^{-1}D^T$ also appears if you want to solve a least-square problem $\|Dx -y\|_2\to 0$ by Tikhonov regularization, where for $\alpha>0$ the problem $$ \min \frac12\|Dx-y\|_2^2 + \frac\alpha2\|x\|_2^2 $$ is solved. Then $x$ solves this problem if and only if $$ (\alpha I + D^TD)x = D^Ty \quad \Leftrightarrow \quad x = (\alpha I + D^TD)^{-1}D^Ty. $$

$\endgroup$
4
  • $\begingroup$ Thanks for the response! I don't understand whether that limit exists or not, because for $a=0$ that matrix is no longer invertible right? $\endgroup$
    – gota
    Nov 18, 2016 at 12:39
  • $\begingroup$ The matrix in question arose in fact through the Tikhonov reg of the least squares $\endgroup$
    – gota
    Nov 18, 2016 at 12:41
  • $\begingroup$ Also, I mistakenly wrote eigenvalues when I wanted to know the relationship between the eigenvectors of $D$ and $\alpha I + D^TD$ $\endgroup$
    – gota
    Nov 18, 2016 at 12:43
  • $\begingroup$ The eigenvectors of $D^TD$ correspond to the right-singular vectors of $D$. $\endgroup$
    – daw
    Nov 18, 2016 at 13:01
1
$\begingroup$

To get the eigenvalues of $M$ we have to evaluate $\det(M-\lambda I)=0$ and can therefore use $M(\alpha I+D^TD)=I$ . Multiplicated $\det(M-\lambda I)=0$ with $(-1)^n\det(\alpha I+D^TD)$ we get $\det(-I+\lambda (\alpha I+D^TD))=\det((\lambda\alpha-1)I+\lambda D^TD)=\lambda^n\det((\alpha-\lambda^{-1})I+D^TD)=0$ . If we define $\overline{\lambda}$ as the eigenvalues of $D^TD$ and if $\lambda\neq 0$ then the eigenvalues of $M$ are $\lambda=\frac{1}{\alpha+\overline{\lambda}}$ .

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .