Solution method and solution apparatus for underdetermined system of linear equations

摘要

A solution method for solving an underdetermined system of linear equations, in which the number of elements of a variable to be determined is N and the number of linear equations is M (where M and N are integers satisfying 1≦MN), using iterative calculations, comprises, in each iteration: an extraction step of extracting at least M non-zero element candidates from the N elements of the variable; a subproblem solving step of setting a subproblem having only the extracted non-zero element candidates as a variable, and solving the subproblem as an ill-posed problem; and an updating step of updating values of the N elements of the variable to be determined on the basis of values of the non-zero element candidates obtained in the subproblem solving step.