3
$\begingroup$

I know SVD is a linear algebra topic, but i've seen multiple times in different articles that SVD is a nonlinear function. So i don't know what to think..

$\endgroup$
  • $\begingroup$ Linear algebra is the study of linear transformations. However, we may study them using nonlinear tools. $\endgroup$ – Rahul Aug 20 '16 at 16:12
2
$\begingroup$

In higher mathematics, a function is said to be linear if $f(x+y)=f(x)+f(y)$. The process of SVD decomposition can be seen as a function, which we will call $S$, which take in a matrix and returns three matrices: $S(A)=(U,\Sigma,V)$. The three matrices that are returned have the property that $A=U\Sigma V^T$. However, given two matrices of the same size, say $A$ and $B$, $S(A+B)\neq S(A)+S(B)$. In other words, the $U$ in the SVD decomposition for $A+B$ is not equal to the $U$ in the SVD decomposition for $A$ plus the $U$ in the SVD decomposition for $B$. The same is true for the $\Sigma$ and the $V$.

Linear algebra has the moniker "linear" because all linear functions that act on vectors of finite dimension can be represented by matrices, and all matrices represent linear functions acting on vectors. However, certain aspects of linear algebra are nonlinear. For example, the function that accepts a matrix and returns its square: $f(A)=A^2$ is nonlinear because $(A+B)^2\neq A^2+B^2$ in general. So SVD is a linear algebra topic because it involves breaking up a single linear action into three simpler linear actions, but the function that takes each matrix to its decomposition is nonlinear.

$\endgroup$
  • $\begingroup$ Note also that this $S(A)$ is a multivalued function=) $\endgroup$ – TZakrevskiy Aug 20 '16 at 16:07
  • $\begingroup$ True, you can rearrange the rows and columns of $U$, $\Sigma$, and $V$ in a consistent way. Is it multivalued even beyond that? $\endgroup$ – Alex S Aug 20 '16 at 16:08
  • $\begingroup$ @AlexS Yes, you can change the signs of the columns, but not arbitrarily so. $\endgroup$ – Rodrigo de Azevedo Aug 20 '16 at 16:12
  • $\begingroup$ @AlexS the simpliest case, take $A=I$. The matrix $U=V^*$ is an arbitrary orthogonal matrix. Therefore, in some cases, we can go beyond rearrangements and multiplications by $-1$ and even make linear combinations of rows/columns. $\endgroup$ – TZakrevskiy Aug 20 '16 at 16:19
  • $\begingroup$ @AlexS, if I am not wrong, in the way you analyse the problem then it is also shown that PCA is non-linear while we know that PCA is linear and for example t-SNE is labeled loosely speaking as non-linear PCA. $\endgroup$ – Poete Maudit Oct 26 '18 at 9:21

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.