Least Norm Solution

Least Norm Solution

Mathematical Definition

Consider a system of linear equations represented by the matrix equation Ax = b, where A is an m × n matrix with m < n (fewer equations than variables), and assume A has full row rank (rank(A) = m). Because the system is underdetermined, there are infinitely many vectors x that satisfy the equation.

The least norm solution, denoted as x_ln, is the solution to the following optimization problem:

Using the method of Lagrange multipliers, the analytical solution is found to be:

Key Concepts

The Moore-Penrose Pseudoinverse

The expression A^T(AA^T)^-1 is a specific form of the Moore-Penrose pseudoinverse, often denoted as A⁺, for a matrix with full row rank. It acts as a right inverse of A, meaning AA⁺ = I. Therefore, we can write the least norm solution simply as x_ln = A⁺b.

Geometric Interpretation

Geometrically, the set of all solutions to Ax = b forms a linear manifold (a shifted subspace) in n-dimensional space. The least norm solution is the vector in this manifold that is closest to the origin. This point is exactly where the position vector from the origin is orthogonal to the solution manifold. Thus, x_ln lies in the row space of A.

Orthogonality Principle

Any solution x to Ax = b can be written as x = x_ln + x_null, where x_null is a vector in the null space of A (meaning Ax_null = 0). Because x_ln is in the row space of A, it is orthogonal to any vector in the null space. By the Pythagorean theorem, ||x||² = ||x_ln||² + ||x_null||². This clearly shows that the norm is minimized when x_null = 0.

Historical Context

The study of least norm solutions grew alongside the development of the pseudoinverse by Eliakim Hastings Moore in 1920 and independently by Roger Penrose in 1955. While least squares methods (dealing with overdetermined systems) have roots tracing back to Gauss and Legendre in the early 19th century, the formalized least norm problem became prominent in the mid-20th century with the rise of modern control theory, where minimum energy solutions were required for systems with multiple inputs.

Real-world Applications

• Control Systems: Finding a sequence of control inputs (e.g., thruster bursts for a spacecraft) that achieves a desired state transition while minimizing fuel or energy consumption.
• Robotics: Inverse kinematics for redundant manipulators (robots with more joints than degrees of freedom in their task space). The least norm solution finds the joint velocities that achieve the desired end-effector velocity while minimizing the overall movement of the robot arm.
• Signal Processing: In underdetermined signal recovery, the least norm solution reconstructs a signal that satisfies given measurements while possessing the minimum possible energy. (Note that finding sparse solutions requires changing the norm from L2 to L1, leading to techniques like basis pursuit).
• Machine Learning: When training linear models with more parameters than data points, finding the least norm weights provides a form of implicit regularization, improving generalization by preferring simpler models.

Related Concepts

• Least Squares Approximation — The dual problem for overdetermined systems (minimizing the residual ||Ax - b||).
• SVD Decomposition — Provides a general method for computing the pseudoinverse and the least norm solution even when A is rank-deficient.
• Null Space & Column Space — Fundamental concepts explaining the geometry of the solution space.
• Orthogonal Projections — The least norm solution can be viewed as an orthogonal projection onto the row space.