HP Labs Technical Reports

Sparse Approximate Solutions to Linear Systems

Natarajan, Balas K.



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]