Sparse approximation

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,\; ext\{\; 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.

References

*.