Language:   Search:   Contact
Zentralblatt MATH has released its new interface!
For an improved author identification, see the new author database of ZBMATH.

# 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

Login Username: Password:

Highlights
Master Server

### Zentralblatt MATH Berlin [Germany]

© FIZ Karlsruhe GmbH

Zentralblatt MATH master server is maintained by the Editorial Office in Berlin, Section Mathematics and Computer Science of FIZ Karlsruhe and is updated daily.

Other Mirror Sites

Copyright © 2013 Zentralblatt MATH | European Mathematical Society | FIZ Karlsruhe | Heidelberg Academy of Sciences
Published by Springer-Verlag | Webmaster