Lower Bounds for Sparse Recovery.
Khanh Do BaPiotr IndykEric PriceDavid P. WoodruffPublished in: SODA (2010)
Keyphrases
- lower bound
- upper bound
- lower bounding
- objective function
- branch and bound algorithm
- sparse data
- upper and lower bounds
- np hard
- branch and bound
- image recovery
- compressive sensing
- lower and upper bounds
- sparse representation
- optimal solution
- vc dimension
- worst case
- recovery algorithm
- set of randomly generated instances
- random projections
- high dimensional