Generating sparse vectors in a subspace (of $\mathbb{R}^n$)

Question

I have an orthonormal basis for a given subspace (of $\mathbb{R}^n$). I am also given the sparsest ($l_0$ norm) vector direction (since $l_0$ norm is independent of scaling) belonging to the subspace (obtained using this algorithm). Using this information, is there any efficient way to generate the $2^{nd}$ sparsest vector (direction) in the subspace?

Answer 1

Here is one approach

---

Span the complement to the subspace, build a matrix from it with basis vectors as rows, call it $\bf M$.

Now for a column vector $\bf v$ to lie in the subspace : $\bf Mv = 0$ must hold, alright? This gives us a first optimization term $\|\bf Mv\|_2^2$. This is also true if we have a collection of vectors stored in a matrix, say $\bf V = [v_1,v_2,\cdots,v_n]$ with the corresponding optimization term $$\|\bf MV\|_F^2$$ Okay? Now we want $\bf v_1$ to be sparser than $\bf v_2$ which is sparser than $\bf v_3$ etc. It is well known we can get close to $L_1$ solutions using iterated reweighting of linear programs, where weights ${\bf W}_{ii}$ on the entries of the vectors $\bf \|Wv\|_2^2$ increase the closer ${\bf v}_i$ was to 0 ( in the previous iteration ). Now we will need to vectorize our $\bf V$, since otherwise it would be difficult to choose individual $\bf W$ matrices for each ${\bf v}_k$, something that is required to achieve an order of importance of sparsity.

---

Now what is left is something to avoid getting $\bf 0$-vector solutions, and to find good sequence of functions $f_l$ for the reweighting: $$({{\bf W_{k+1}})_l} = f_l({{(\bf W_k})_l},({\bf v_k})_l), \text{ where } \cases{k \text{ is iteration number }\\ l \text{ is vector number}}$$