Is it possible to find the sparsest vector (direction) in a generic subspace
$\mathcal{S} \subseteq \mathbb{R}^p$ with $\mathrm{dim}(\mathcal{S})= n < p$?
This problem can be considered a homogeneous variant of the spar
本文介绍了一种用于从一个由稀疏向量和 k 个随机向量张成的子空间中恢复稀疏向量的方法,并证明了当其支撑大小 s 满足 s ≦ n/√(k log n) 时,这种方法的稀疏向量恢复率较高;此外,该方法还可以近似地处理稀疏向量,但需要根据任何代理来选择最稀疏的输出,不同的代理对这种方法的表现也会有所影响,其中选出的代理越来越基于 ℓ1/ℓ2 范数,比起 ℓ1/ℓ∞ 范数,这种代理的成功恢复范围更大。