HP Labs Technical Reports

Sparse Approximate Solutions to Linear Systems

Natarajan, Balas K.

HPL-92-167

Keyword(s):

Abstract: We consider the problem of computing a sparse approximate solution to a given linear system and tolerance, i.e., a vector with a minimum number of non-zero entries that satisfies the system within the given tolerance. While the problem is NP-hard, we prove that a well-known greedy heuristic is almost optimal.

Back to Index