Finding a sparse vector in a subspace: Linear sparsity using alternating directions

Qing Qu, Ju Sun, John Wright

Is it possible to find the sparsest vector (direction) in a generic subspace $\mathcal{S}\subseteq {\mathbb{R}}^p$ with $\dim (\mathcal{S})=n<p$? This problem can be consi…