The Simplest Solution to an Underdetermined System of Linear Equations

David Donoho, Hossein Kakavand, James Mammen

Consider a d*n matrix A, with d<n. The problem of solving for x in y=Ax is underdetermined, and has infinitely many solutions (if there are any). Given y, the minimum Kolmogorov co…