In mathematics, a system of linear equations is considered underdetermined if there are fewer equations than unknowns. The terminology can be described in terms of the concept of counting constraints. Each unknown can be seen as an available degree of freedom. Each equation introduced into the system can be viewed as a constraint that restricts one degree of freedom.
Therefore the critical case occurs when the number of equations and the number of independent variables are equal. For every degree of freedom, there exists a corresponding restraint. The underdetermined case occurs when the system has been underconstrained—that is, when the number of unknowns outnumbers the number of the equations.
Contents |
While in the general case, there are an infinite number of solutions to an underdetermined system, there is a subset of problems fitting the compressed sensing framework, where sparse solutions can be found to be the unique solutions of an underdetermined system. Exact solutions can be found using a variety of solvers implementing a wide range of techniques ranging from linear programming to greedy algorithms.
Underdetermined systems appear in a whole slew of problems where there far fewer equations than unknowns such as genomics, sub-Nyquist sampling, compressed sensing etc... The concept can also be applied to more general systems of equations, such as partial differential equations.