[beauty of algebra] solution method of linear equations ax=0

stay 3D In vision , We often encounter such a problem ： Solve linear equations $Ax=0$, From the perspective of matrix mapping , All solutions form a matrix $A$ Zero space of . A typical scenario, such as using the eight point method to solve the essential matrix $E$, See my previous blog ： Introduction to stereo vision （2）： Key matrix （ The essential matrix , Basic matrix , Homography matrix ）. This is a basic and common linear algebra problem , In this article, we will discuss the solution of this kind of problem , It is also an introductory course .

The obvious solution

about $Ax=0$, Obviously ,$x=0$ It must be one of the solutions , But for our practical application , Getting a zero solution is often meaningless , So no discussion .

Nonzero special solution

As mentioned earlier , What we actually want , Nonzero solution , They are obviously deeper than the zero solution .

Before discussing nonzero solutions , We must introduce the concept of special solution . One obvious point is ,$Ax=0$ The scale is constant , I.e $x_s$ Is one of the solutions , be $k_s{x}_s$ It must also be the solution （$k_s$ Is the set of real Numbers ）, and $k_s{x}_s$ and $x_s$ It's linear ; Further , If $x_t$ It's another one with $x_s$ Linearly independent solutions , namely
$$A{x}_s=0,A{x}_t=0,x_{s}and{x}_{t}LinesexnothingTurn\; off$$

Obviously $A(k_s{x}_s+k_t{x}_t)=0$ It's also true （$k_s,k_t$ Is the set of real Numbers ）, namely $k_s{x}_s+k_t{x}_t$ It's also the solution of the equation . This reveals a phenomenon ： If the equations $Ax=0$ There are several linearly independent solutions $x_1,x_2,...,x_n$, be $x_1,x_2,...,x_n$ Any linear combination of is also its solution , let me put it another way , All solutions can pass $x_1,x_2,...,x_n$ Linear combination . Let's take these linear independent solutions $x_1,x_2,...,x_n$ It is called a system of equations $Ax=0$ Special solution of .

therefore , Our purpose , In fact, we need to calculate all non-zero special solutions .

First of all, we want to find out , How many non-zero special solutions are there ？

We analyze it from the elimination and substitution solution , Suppose a matrix $A\in R^{m\times n}(m=3,n=4)$：
$$A=\left[\begin{array}{cccc}1& 3& 6& 6\\ 2& 2& 4& 8\\ 4& 4& 8& 16\end{array}\right]$$

First of all, $A$ Carry out elimination ,
$$\left[\begin{array}{cccc}1& 3& 6& 6\\ 2& 2& 4& 8\\ 4& 4& 8& 16\end{array}\right]\to \left[\begin{array}{cccc}1& 3& 6& 6\\ 2& 2& 4& 8\\ 0& 0& 0& 0\end{array}\right]\to \left[\begin{array}{cccc}\boxed{1}& 3& 6& 6\\ 0& \boxed{2}& 4& 2\\ 0& 0& 0& 0\end{array}\right]$$

In the matrix after elimination , In box 1 and 2 It is called the primary variable （pivot variable）, Also known as principal . The number of principal elements is called the rank of the matrix , The number of principal elements here is 2, So the matrix A The rank of （rank） Also for the 2, namely $rank(A)=2$.

The column in which the primary element is located is called the primary column （pivot column）, The main columns here are 1 Column and the first 2 Column , Other columns 3 Column and the first 4 List as free column （free column）. The variables in the free column are free variables （free variable）, The number of free variables is $n-rank(A)=4-2=2$.

According to the elimination solution , After elimination, we assign values to free variables , Back substitution to find the value of the main column variable . Give free variables respectively $\left[\begin{array}{c}{x}_3\\ x_4\end{array}\right]$ The assignment is $\left[\begin{array}{c}1\\ 0\end{array}\right]$ and $\left[\begin{array}{c}0\\ 1\end{array}\right]$, The following two solution vectors are obtained by substituting the equation ：
$$\left[\begin{array}{c}0\\ -2\\ 1\\ 0\end{array}\right],\left[\begin{array}{c}-3\\ -1\\ 0\\ 1\end{array}\right]$$

These two solution vectors are linear equations $Ax=0$ Two non-zero special solutions of , Other solutions can be expressed linearly by these two solutions ：$x=a\left[\begin{array}{c}0\\ -2\\ 1\\ 0\end{array}\right]+b\left[\begin{array}{c}-3\\ -1\\ 0\\ 1\end{array}\right]$. It can also be said that any linear combination of special solutions constructs a matrix $A$ The whole zero space of .

You know , System of linear equations $Ax=0$ The number of non-zero special solutions of is $n-rank(A)$.

Least square solution

The above analysis is only from the perspective of Pure Mathematics , But in the application of Computer Science , The most common situation we encounter is , Through a large number of observations with certain noise , The number of construction equations is much larger than the unknown Overdetermined linear equations $Ax=0,A\in R^{m\times n},m\gg n$, At this time, there is often no strict solution .

For example, in solving the essential matrix of two images $E$ when , We will match a large number of feature point pairs , Then linear equations are constructed based on antipolar constraints $Ae=0$ Solve the element vector of the essential matrix $e$, The number of characteristic point pairs is often far more than the number of elements of the essential matrix （ namely $m\gg n$）, And because of the existence of point noise , The antipolar constraint is not strictly established （ namely $Ax\approx 0$）. In the face of this situation , Our usual practice is to ask Least square solution . namely ：
$$\hat{x}=\arg \underset{x}{\min }||Ax|{|}_2^2$$

But we immediately found a problem , Scale invariance as mentioned above , If $x_s$ It's a solution , be $k_s{x}_s$ It's also the solution , Then when we find a solution , Infinitely reduce the module length of the solution vector ,$||Ax|{|}_2^2$ Wouldn't it be infinitely small , Which one should I choose ？ This is obviously an impasse .

therefore , We're going to give $x$ A constraint , That is, its module length is limited to a constant , For example, the most commonly used unit module length 1, namely $x$ Must satisfy ,$||x|{|}_2^2=1$. This reconstructs a constrained least squares problem ：
$$\hat{x}=\arg \underset{x}{\min }||Ax|{|}_2^2,\text{subject to}||x|{|}_2^2=1$$

According to the Lagrange multiplier method , another
$$L(x,\lambda )=||Ax|{|}_2^2+\lambda (1-||x|{|}_2^2)$$

requirement $L(x,\lambda )$ minimum value , Then first find the extreme value , That is, the first partial derivative is 0 The point of , We are respectively right $x,\lambda$ Find the partial derivative and make it equal to 0：
$$\begin{array}{rl}{L}^{{}^{\prime }}(x)& =2A^{T}Ax-2\lambda x=0\\ L^{{}^{\prime }}(\lambda )& =1-x^{T}x=0\end{array}$$

Then there are $A^{T}Ax=\lambda x$, This familiar formula tells us ,$x$ It's a matrix $A^{T}A$ The characteristic value is $\lambda$ Eigenvector of .

But the matrix $A^{T}A$ At most $n$ Eigenvalues , Corresponding $n$ eigenvectors , Which is the minimum point ？

Let's make another derivation ： When $x$ It's a matrix $A^{T}A$ The characteristic value is $\lambda$ When the eigenvector of , Yes
$$||Ax|{|}_2^2=x^T{A}^{T}Ax=x^T\lambda x=\lambda x^{T}x=\lambda$$

therefore , When $\lambda$ Take the minimum ,$||Ax|{|}_2^2$ Minimum value , namely Least square solution $\hat{x}$ It's a matrix $A^{T}A$ The eigenvector corresponding to the minimum eigenvalue . This is a system of overdetermined linear equations $Ax=0$ The least square solution of .