la4j
la4j copied to clipboard
vkostyukov
Minimum Norm Solution
We need to support this:
When m < n and rank(A) = m, there are an infinite number of solutions x which exactly satisfy b-Ax=0. In this case it is often useful to find the unique solution x which minimizes |x|2, and the problem is referred to as finding a minimum norm solution to an underdetermined system of linear equations.
Some note: when linear system has more than one solution, it has a system of basic solutions, and any other solution is a linear combination of elements from that system. So we need to find this system and any particular solution and then to solve some problem of non-linear optimization.
Some other note: this problem of non-linear optimization brings us to (n+m)-dimensional full linear system which has an unique solution. For the theory, see http://www.machinelearning.ru/wiki/images/8/81/MOMO12_ipm.pdf (Russian) and http://cbio.ensmp.fr/~jvert/teaching/2006insead/slides/6_algo2/algo2.pdf (English)
So, the problem is to clearify: can we enlarge system dimension twice, or we need to find some other way?
Found a paper on Stanford site: http://see.stanford.edu/materials/lsoeldsee263/08-min-norm.pdf
In brief, for full-rank matrices there is a direct expression for minimum norm solution as a_ln = A*(A*A)^-1 b. So, we can implement "pseudo-inverse" matrix computation (which is A*(A*A)^-1) and then simply produce matrix-vector multiplication (throwing exceptions when matrix is not full-rank).