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

[Research] [News] [Tech Reports] [Palo Alto] [Bristol] [Japan] [Israel] [Site Map] [Home] [Hewlett-Packard]