On the error of estimating the sparsest solution of underdetermined linear systems

Massoud Babaie-Zadeh, Christian Jutten, Hosein Mohimani

Let A be an n by m matrix with m>n, and suppose that the underdetermined linear system As=x admits a sparse solution s0 for which ||s0||_0 < 1/2 spark(A). Such a sparse solution is…