Let A be a linear system of size m x n and b be a vector of size m x1. We look for a solution x such that

Ax=b.

It is known that the existence, uniqueness of the solution x whem m=n. We also know how to solve x when m=n by Gaussian elimination.

When m>n, we also know how to find a solution x such that the distance Ax to b is the smallest, the least squares solution. We know many properties of the least squares solutions.

When m< n, we know that there are many solutions to solve Ax=b. A problem is how to find a solution x which has the smallest number of nonzero entries. Such a kind of solution is called the sparest solution. Let ||x||_0 be the number of nonzero entries. We want to solve

minimize { ||x||_0, such that A x= b }.

This is our research problem of this VIGRE seminar

Here are some links of researches related to this problem.

• I have one paper joint with Simon Foucart in this direction of research. In this paper, we show how to use quasi-norm \ell_q, 0<= q<1 to find the sparsest solution.
• Rice University has been keeping an updated list of references related to the research problem. Check out.
• There will be a conference on this topic of research in May, 2009.
• I wrote a survey paper to simply explain an overview of this research problem.