Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 0827.68054
Natarajan, B.K.
Sparse approximate solutions to linear systems. (English)
[J] SIAM J. Comput. 24, No.2, 227-234 (1995). ISSN 0097-5397; ISSN 1095-7111/e

Summary: The following problem is considered: given a matrix $A$ in $\bbfR^{m \times n}$, ($m$ rows and $n$ columns), a vector $b$ in $\bbfR^m$, and $\varepsilon > 0$, compute a vector $x$ satisfying $|Ax - b|_2 \leq \varepsilon$ if such exists, such that $x$ has the fewest number of non-zero entries over all such vectors. It is shown that the problem is $NP$-hard, but that the well-known greedy heuristic is good in that it computes a solution with at most $\lceil 18 \text {Opt} (\varepsilon / 2) |{\bold A}^+ |^2_2 \text {ln} (|b|_2/\varepsilon) \rceil$ non-zero entries, where $\text {Opt} (\varepsilon/2)$ is the optimum number of nonzero entries at error $\varepsilon/2$, $\bold A$ is the matrix obtained by normalizing each column of $A$ with respect to the $L_2$ norm, and ${\bold A}^+$ is its pseudo-inverse.

MSC 2000:: *68Q25 Analysis of algorithms and problem complexity

Keywords: sparse solutions

Cited in: Zbl 1113.15004

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]