1. 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≦M<N), using iterative calculations performed by a computer, the method comprising, in each iteration, operating said computer to execute: an extraction step of extracting at least M non-zero element candidates from said N elements of said variable; a subproblem solving step of setting a subproblem having only said extracted non-zero element candidates as a variable, and solving said subproblem as an ill-posed problem; and an updating step of updating values of said N elements of said variable to be determined on the basis of values of said non-zero element candidates obtained in said subproblem solving step.