Sparse approximation

From Wikipedia, the free encyclopedia

 This article is orphaned as few or no other articles link to it.
Please help introduce links in articles on related topics. (April 2008)


Sparse approximation is the problem of finding a signal or vector estimate with sparseness property, that is having a small number of nonzero elements, that satisfies (approximately) a system of equations.

For example, consider a linear system of equations y = Ax, where A is a real M-by-N matrix and M < N. In general, this problem is ill-posed as there are infinitely many x that solve this system.

One way to enforce sparsity is to choose x such that as many components as possible are zero. In other words, we want to solve

\min_x \|x\|_0, \text{ such that } y = A x,

where the objective function is defined by

\|x\|_0 = \#\{ k : x_k = 0, \, k=1,\ldots,N \}

and # denotes the cardinality of the set. However, this problem is NP-complete because classical combinatorial optimization can be reduced to it.

[edit] References