Overdetermined homogeneous linear equation system - $A$ vs $A^TA$

Question

Actually I am working with a overdetermined homogeneous system of linear equations $Ax=0$. In literature I found, that a least square result can be found with helpf of SVD. The solution is the eigenvector corresponding to the smallest eigenvalue of $A^TA$.

So far so good. But in some literature I could read, that one should look for the eigenvalue/eigenvector of $A$. Unfortunately I cannot find the literature, which says $A$ instead of $A^TA$.

Does the method change, if the system is not overdetermined?

Please help me to solve my confusion. Thanks.

Answer 1

If the system is not over-determined then there should be a solution, so you should try to solve the original problem,

$$A x = 0.$$

More generally, it sounds like you want to do something like minimizing the norm of the vector, $A x$. But of course you'd just choose $x=0$. So do you want to instead minimize the norm of $A x$ for a fixed magnitude of $x$?. If so, the way I'd do it is to minimize $(A x)^2 = x^T A^T A x$ subject to the condition $x^T x = 1$. I'd do that by adding the Lagrange multiplier term and enforcing the first-order conditions on:

$$x^T A^T A x + \lambda (x^T x - 1).$$

That is, I'd differentiate it with respect to the vector $x$ and set it equal to zero, yielding:

$$A^T A x + \lambda x = 0.$$

Consequently, indeed, if this is what you want then your answer should be an eigenvector of $A^T A$, specifically any one with the lowest eigenvalue. I think similar analysis applies to the complex case where the transpose is replaced with the conjugate transpose.

Answer 2

With the answer and the comments I finally could answer the question by myself and solve my confusion. Thanks again for putting me on the right track. Both leads to a valid solution.

Edit: And as user amsmath commented, it always holds that $min_{||x||=1}||Ax|| = min_{||x||=1}\sqrt{\langle A^TAx, x \rangle}$ which is always (!) the square root of the smallest eigenvalue of $A^TA$ (and at the same time the smallest singular value of $A$)

An overdetermined homogeneous linear equation system can be represented as $Ax=0$, where $A\in R^{m\times n}$ with $m>n$ subject to $||x||=1$. Desired is a non trivial solution ($x\neq 0$), which minimizes $||Ax||$. Solutions form a hyperspace. If $x_0$ is a solution, then $\kappa x_0$ for $\kappa \in R$ is also a solution.

Case 1 - Solution is the right-singular vector corresponding to the smallest singular value of $A$

Edit: I was mixing up eigenvalues and singular value. Beeing precise helps to improve understanding. In that post the difference of eigenvalues and singular values is discussed.

We are looking for an $x$ that minimizes $||Ax||$ subject to $||x||$. The SVD decomposition of $A$ leads to $$A = UDV^T,$$ where $U\in R^{m\times m}$, $D\in R^{m\times n}$, and $V \in R^{n\times n}$.

Since $U$ is an orthogonal matrix $$||Ax||=||UDV^Tx||$$ leads to $$||Ax||=||DV^Tx||.$$

$V$ is also an orthogonal matrix. So if $||x||=1$ holds, then $||V^Tx||=1$ holds, too. We substitute $V^Tx$ with $y$ and minimizing $||Dy||c$ subject to $||y||=1$. The matrix $D$ is a diagonal matrix $$D=\begin{pmatrix} d_1 & 0 & \dots & 0\\ 0 & d_2 & \dots & 0\\ \vdots & & \ddots & \vdots\\ 0 & 0 & \dots & d_n\\ 0 & 0 & \dots & 0\\ \vdots & \vdots & & \vdots\\ 0 & 0 & \dots & 0\\ \end{pmatrix}\in R^{m\times n},$$ with $d_1 > d_2 > \dots > d_n$ we can minimize $||Dx||$ by chosing $$y = \begin{pmatrix}0\\0\\ \vdots \\ 1\end{pmatrix} \in R^{n\times 1},$$ which satisfy $||y||=1$. The substitution of $V^T$ with $y$ leads to $$x=Vy=\begin{pmatrix}V_{1n}\\V_{2n}\\\vdots\\V_{nn}\end{pmatrix}$$ $\square$

Case 2 - Solution is the eigenvector corresponding to the smallest eigenvalue of $A^TA$.

Applying Lagrange function \begin{align}L(x,\lambda) & := ||Ax|| + \lambda (1-||x||) \\& = x^TA^TAx + \lambda (1-x^Tx) \end{align} Critical points of the Lagrange function are found by equaling derivatives to zeros \begin{align} \frac{\partial L(x,\lambda)}{\partial x} & = 2A^TAx - 2\lambda x = 0\\ \frac{\partial L(x,\lambda)}{\partial \lambda} & = 1- x^Tx = 0 \end{align} First partial derivative can be rewritten as the characteristic polynom $$(A^TA - \lambda I)x = 0$$ of $A^TA$. So every eigenvector $x$ with corresponding eigenvalue $\lambda$ is a critical point and hence a solution for the equation above. We choose the smallest eigenvalue to minimize $||Ax||$. Combining equations lead to \begin{align}||Ax|| &= x^TA^TAx \\ &= x^T\lambda x\\ &= \lambda x^Tx\\ &=\lambda||x||\\& = \lambda \end{align} Therefore the solution is the eigenvector of $A^TA$ with the smallest corresponding eigenvalue. $\square$

Answer 3

Both the SVD method and the Lagrange method for the non-trivial ‘solution’ of overdetermined homogeneous simultaneous linear equations are described by Patterson (2012). I put the word ‘solution’ in single quote marks as these are almost always not exact solutions, rather a least squares fit. Also note, Patterson (2012) is an application to an ecological network problem, and may fall short of a more complete mathematicial treatment of the topic … that said, I can’t find a a treatment of these 2 solution methods in the more mathematical journals/literature and I would be grateful if anyone could provide me with a reference to any such publication. Reference: Patterson,M.G. 2012. Are all processes equally efficient from an emergy perspective? Analysis of ecological and economic networks using matrix algebra methods. Ecological Modelling Volume 226 pp. 77-91