Scaling Law for Recovering the Sparsest Element in a Subspace

Understand

We address the problem of recovering a sparse $n$-vector within a given subspace.

• This problem is a subtask of some approaches to dictionary learning and sparse principal component analysis.
• Hence, if we can prove scaling laws for recovery of sparse vectors, it will be easier to derive and prove recovery results in these applications.
• In this paper, we present a scaling law for recovering the sparse vector from a subspace that is spanned by the sparse vector and $k$ random vectors.