Sparse approximation

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

*.


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… …   Wikipedia

  • Liste de problèmes NP-complets — Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problème de décision. Puisqu on connaît plus de 3000 problèmes NP complets, cette liste n est pas exhaustive. La …   Wikipédia en Français

  • Incomplete Cholesky factorization — In numerical analysis, a field within mathematics, an incomplete Cholesky factorization of a symmetric positive definite matrix is a sparse approximation of the Cholesky factorization. Incomplete Cholesky factorization are often used as a… …   Wikipedia

  • List of NP-complete problems — Here are some of the more commonly known problems that are NP complete when expressed as decision problems. This list is in no way comprehensive (there are more than 3000 known NP complete problems). Most of the problems in this list are taken… …   Wikipedia

  • Overcompleteness — A system in a Banach space X is complete if every element in X can be approximated arbitrarily well in norm by finite linear combinations of elements in .[1] Such a complete system is overcomplete if removal of a ϕj from the system results in a… …   Wikipedia

  • Incomplete LU factorization — In numerical analysis, a field within mathematics, an incomplete LU factorization of a matrix is a sparse approximation of the LU factorization. Incomplete LU factorization are often used as a preconditioner.References*. See Section 10.3 and… …   Wikipedia

  • Clique problem — The brute force algorithm finds a 4 clique in this 7 vertex graph (the complement of the 7 vertex path graph) by systematically checking all C(7,4)=35 4 vertex subgraphs for completeness. In computer science, the clique problem refers to any of… …   Wikipedia

  • Finite element method — The finite element method (FEM) (sometimes referred to as finite element analysis) is a numerical technique for finding approximate solutions of partial differential equations (PDE) as well as of integral equations. The solution approach is based …   Wikipedia

  • Numerical integration — consists of finding numerical approximations for the value S In numerical analysis, numerical integration constitutes a broad family of algorithms for calculating the numerical value of a definite integral, and by extension, the term is also… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”