Solving shortest length least-squares problems via dynamic-programming

If the matrix A is not of full rank, there may be many solutions to the problem of minimizing ||Ax-b|| over x. Among such vectors x, the unique one for which ||x|| is minimum is of importance in applications. This vector may be represented as x=A(¸+)b. In this paper, the functional equation technique of dynamic programming is used to find the shortest solution to the least-squares problem in a sequential fashion. The algorithm is illustrated with an example.