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 sparse recovery
problem, and finds connections to sparse dictionary learning, sparse PCA, and
many other problems in signal processing and machine learning. In this paper,
we focus on a **planted sparse model** for the subspace: the target sparse
vector is embedded in an otherwise random subspace. Simple convex heuristics
for this planted recovery problem provably break down when the fraction of
nonzero entries in the target sparse vector substantially exceeds
$O(1/\sqrt{n})$. In contrast, we exhibit a relatively simple nonconvex approach
based on alternating directions, which provably succeeds even when the fraction
of nonzero entries is $\Omega(1)$. To the best of our knowledge, this is the
first practical algorithm to achieve linear scaling under the planted sparse
model. Empirically, our proposed algorithm also succeeds in more challenging
data models, e.g., sparse dictionary learning.

本研究提出了一种基于交替方向的非凸方法，可以在种植的稀疏模型下实现线性比例尺，并在稀疏字典学习等更具挑战性的数据模型中取得了成功。