5
$\begingroup$

I thought that it would be obvious that in a transform the eigenvectors are the ones that are stretched the most as those are the directions in which the matrix acts. But according to this short video and what others have said: https://youtube.com/watch?v=vs2sRvSzA3o that does not seem to be the case.

I thought so beacuse repeated application of a transform on any vectors makes that vector converge to its largest eigenvalue vector. I'm having a hard time digesting that there are other vectors stretched more. Can someone explain me why it makes sense?

Consider the classic case of a 2D sphere being deformed to an ellipse by a transform. How would I find the vectors then which would become the major and minor axis? [Please dont use SVD but solve more fundamentally through calculus or basic linear algebra]

$\endgroup$
4
  • 3
    $\begingroup$ if you wish to maximize $|Ax|$ for (column vector) $|x|=1,$ you are asking for maximal $(Ax) \cdot (Ax) = x^T A^T A x.$ So it is eigenvectors of $A^T A$ you are asking about. Your third paragraph is some other question.. $\endgroup$
    – Will Jagy
    Commented Aug 25, 2019 at 19:24
  • $\begingroup$ How did you conclude its the eigenvectors suddenly? $\endgroup$ Commented Aug 26, 2019 at 5:17
  • $\begingroup$ @RahulDeora Is this question answered? $\endgroup$
    – stochastic
    Commented May 16, 2020 at 16:45
  • $\begingroup$ Yup, figured it out myself later, thanks. $\endgroup$ Commented May 18, 2020 at 9:13

2 Answers 2

4
$\begingroup$

Update: OP is asking for a solution without SVD decomposition. To solve the same problem using calculus, you are looking for a vector that maximizes $$f(\vec v)=\frac{|M\vec v|^2}{|\vec v|^2}$$ We can achieve that by setting the gradient of $f$ to zero: $$ \nabla f = \nabla \left(\frac{(M\vec v)\cdot(M\vec v)}{\vec v\cdot \vec v}\right) = \frac{2M^*M\vec v}{|\vec v|^2}-\frac{2\vec v|M\vec v|^2}{|\vec v|^4}=\vec 0. $$ Since the length of $\vec v$ does not matter, I'm just going to set it to $1$. Now, we have $$ M^*M\vec v = |M\vec v|^2 \vec v. $$ This tells you that the vector maximizing $f$ is an eigenvector of $M^*M$ with eigenvalue $|M\vec v|^2$. Note that all of the eigenvectors of $M^*M$ are critical points of $f$, but only the one with the largest eigenvalue is the one that maximizes $f$.

To see how this is consistent with the solution from SVU decomposition, note that

  1. If $M=U\Sigma V^*$, then $M^*M = V\Sigma U^*U\Sigma V^* = V\Sigma^2V^*$ with eigenvectors that are the right singular vectors of $M$ and eigenvalues being the square of singular values of $M$.
  2. If $\vec v$ is an eigenvector of $M^*M$ with length $1$ and eigenvalue $\lambda$, $|M\vec v|^2 =\vec v.(M^*M\vec v)= \lambda \vec v.\vec v= \lambda $.

Original Answer with SVD

Let $U\Sigma V^*$ be the singular value decomposition of matrix $M$. Without loss of generality, assume the largest singular value is given by $\Sigma_{11}$. Let us analyze the action of $M$ on a vector $\vec v$: there is a rotation of $\vec v$ by $V^*$, followed by stretching by $\Sigma$ and then rotation by $U$. Since $\Sigma_{11}$ gives the largest stretch, the vector that gets mapped to $(1,0, 0,\dots)^T$ under $V^*$ will end up getting stretched the most and gets mapped to the major axis of the ellipse in the 2D case (after rotation by $U$). $$ V^*\vec v= (1,0,\dots)^T\implies \vec v = V (1,0,\dots)^T $$ The major axis will be $M\vec v$ where $\vec v$ is found from the above equation.

enter image description here

$\endgroup$
5
  • $\begingroup$ I stated "Please dont use SVD but solve more fundamentally through calculus or basic linear algebra" becuase the text I was reading mentions a way to find this vector with basic techniques. I was hoping that would shed more intution $\endgroup$ Commented Aug 26, 2019 at 8:37
  • $\begingroup$ @RahulDeora I updated my solution. Does this help? $\endgroup$
    – stochastic
    Commented Aug 27, 2019 at 0:00
  • $\begingroup$ Your formulas do not appear properly, unless I have a problem on my screen... $\endgroup$
    – Jean Marie
    Commented Aug 27, 2019 at 0:04
  • 2
    $\begingroup$ @JeanMarie They render in just fine in my browser. I have been having a similar problem with SE recently that sometimes I have to refresh the page to get the tex to render. Let me know if that works $\endgroup$
    – stochastic
    Commented Aug 27, 2019 at 0:08
  • $\begingroup$ @stochastic It works ; indeed, a page refreshment was needed. $\endgroup$
    – Jean Marie
    Commented Aug 27, 2019 at 0:13
0
$\begingroup$

Disclaimer : This is not a rigorous approach, and cannot be considered as a true answer, but a research direction.

First of all, we need to have a precise definition of what you call a stretch. It should be a measure of discrepancy combining

  • a length discrepancy $\|AV\|/\|V\|$ large (as @Will Jagy considers)

  • and an angle discrepancy $\langle AV,V \rangle$ closest to zero ($AV$ and $V$ almost orthogonal...).

In the absence of such a definition, one can still consider the very important $QR$ decomposition (https://en.wikipedia.org/wiki/QR_decomposition) of $A$ into the product of a triangular matrix $R$ and an orthogonal one, $Q$.

Indeed, $R$ is a good candidate for providing "extreme discrepancy vectors". Why ? Because this decomposition (see below an example) can be interpreted geometrically as the separation between the shearing effect and an orthogonal transformation (which does no stretch anything, whatever the definition of stretching...). See for example what happens for this matrix, that we have selected with complex eigenvalues in order that the issue is not "polluted" by (real) eigenvectors :

$$\begin{pmatrix}0.5&1.5\\-1&2\\\end{pmatrix}= \underbrace{\begin{pmatrix}-0.4472 &0.8944 \\ \ \ 0.8944&0.4472\end{pmatrix}}_{Q} \underbrace{\begin{pmatrix} -1.1180 &1.1180 \\ 0&2.2361\end{pmatrix}}_R\tag{1}$$

The second column $U$ of $R$ and its image $AU$ by $A$ have an important discrepancy, materialized on the following figure (thick black vectors that have at he same time a big amplification factor and are almost orthogonal). We observe that this discrepancy is more important than the most important discrepancies obtained by considering random unit vectors and their images by matrix $A$ (bearing the same number). We can't do more than this constatation due, said again, to the lack of an objective definition of what exactly is "stretching".

enter image description here

Fig. 1 : Vectors having the same code come by pairs : one of them is a (random) unit norm vector $V_k$, and the other one its image $AV_k$. The two thick black vectors are the last (normalized) column of $R$ (see (1)) and its image by $A$, providing "in general" a maximal "visual" discrepancy.

Remark : in (1) the orthogonal transformation is a symmetry.

$\endgroup$

You must log in to answer this question.

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