Underdetermined system
Encyclopedia
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.
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.
, sub-Nyquist sampling
, compressed sensing
etc...
The concept can also be applied to more general systems of equations, such as partial differential equations.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, 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
Variable (mathematics)
In mathematics, a variable is a value that may change within the scope of a given problem or set of operations. In contrast, a constant is a value that remains unchanged, though often unknown or undetermined. The concepts of constants and variables are fundamental to many areas of mathematics and...
can be seen as an available degree of freedom
Degrees of freedom (statistics)
In statistics, the number of degrees of freedom is the number of values in the final calculation of a statistic that are free to vary.Estimates of statistical parameters can be based upon different amounts of information or data. The number of independent pieces of information that go into the...
. 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.
Exact solutions to some underdetermined systems
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 sensingCompressed sensing
Compressed sensing, also known as compressive sensing, compressive sampling and sparse sampling, is a technique for finding sparse solutions to underdetermined linear systems...
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
Linear programming
Linear programming is a mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear relationships...
to greedy algorithms.
In general use
Underdetermined systems appear in a whole slew of problems where there far fewer equations than unknowns such as genomicsGenomics
Genomics is a discipline in genetics concerning the study of the genomes of organisms. The field includes intensive efforts to determine the entire DNA sequence of organisms and fine-scale genetic mapping efforts. The field also includes studies of intragenomic phenomena such as heterosis,...
, sub-Nyquist sampling
Compressed sensing
Compressed sensing, also known as compressive sensing, compressive sampling and sparse sampling, is a technique for finding sparse solutions to underdetermined linear systems...
, compressed sensing
Compressed sensing
Compressed sensing, also known as compressive sensing, compressive sampling and sparse sampling, is a technique for finding sparse solutions to underdetermined linear systems...
etc...
The concept can also be applied to more general systems of equations, such as partial differential equations.
See also
- Regularization (mathematics)Regularization (mathematics)In mathematics and statistics, particularly in the fields of machine learning and inverse problems, regularization involves introducing additional information in order to solve an ill-posed problem or to prevent overfitting...
- Boundary conditions
- Inverse problemsInverse ProblemsInverse Problems is a peer-reviewed, broad-based interdisciplinary journal for pure and applied mathematicians and physicists. It combines theoretical, experimental and mathematical papers on inverse problems with numerical and practical approaches to their solution...
- Compressed SensingCompressed sensingCompressed sensing, also known as compressive sensing, compressive sampling and sparse sampling, is a technique for finding sparse solutions to underdetermined linear systems...
- Overdetermined systemOverdetermined systemIn mathematics, a system of linear equations is considered overdetermined if there are more 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...