Sparse basis for linear subspace

Question

Suppose I have a linear subspace of some vector space, e.g., described as the column space of some big matrix. How would I algorithmically find a basis of that same subspace where the basis matrix is sparse, i.e., most entries in most basis vectors are zero?

I understand that this will depend on the structure of the matrix, so you might prefer to interpret this as “as many entries as possible are zero” instead of “most entries are zero”. I'm interested in good practical solutions, even if the results are not optimal.

Answer 1

Suppose your subspace $V$ is the column space of the $m \times n$ matrix $M$, where $M$ has rank $n < m$. Choose any subset $S$ of $\{1,\ldots, m\}$ of cardinality $n-1$, and consider the $(n-1) \times n$ submatrix $M_S$ of $M$ consisting of the rows enumerated in $S$. If $y$ is a nonzero vector in the null space of $M_S$, then $M y$ is a nonzero member of $V$ with zeros in the positions given by $S$. Do this for $m$ randomly chosen subsets $S$ and and you will probably get enough such vectors to span $V$.

For example, I tried the random $7 \times 4$ matrix $$ M = \left[ \begin {array}{cccc} -6&2&3&9\\ 0&5&-1&2 \\ 1&-2&-1&7\\ 8&1&3&-2 \\ 7&-4&7&-8\\ -1&-1&-6&9 \\ -6&-4&-6&-6\end {array} \right] $$

Using subsets $[2, 3, 7], [4, 5, 7], [3, 5, 6], [3, 5, 7]$ I got the vectors consisting of the columns of $$\left[ \begin {array}{cccc} {\frac {780}{19}}&{\frac {3}{26}}&-{ \frac {289}{28}}&{\frac {681}{13}}\\ 0&-{\frac {80}{ 13}}&{\frac {471}{14}}&-{\frac {311}{26}}\\ 0&{ \frac {151}{13}}&0&0\\ -{\frac {468}{19}}&0&{\frac { 615}{14}}&-{\frac {755}{26}}\\ -{\frac {311}{19}}&0&0 &0\\ -4&{\frac {170}{13}}&0&-{\frac {415}{26}} \\ 0&0&-{\frac {415}{7}}&0\end {array} \right] $$

Since that matrix has rank $4$, these columns span $V$.

Answer 2

I suspect this is a tough problem to solve in one shot but here is an idea. Bear with me as I'm thinking out loud. Suppose you have already identified $a_1, \ldots, a_p \in V$ that are linearly independent. Construct $$ A := \begin{bmatrix} a_1 \cdots a_p \end{bmatrix}. $$ Suppose further that $V$ can be described by the linear system $Bx=d$. One way to find a sparse vector in $V$ that is orthogonal to $a_1, \ldots, a_p$ is to solve the $\ell_1$ problem $$ \min_x \ \|x\|_1 \quad \text{subject to} \ Bx=d, \ A^T x = 0. $$ This can be transformed to a linear programming problem as follows: \begin{align*} \min_{x,v} \quad & \sum_i v_i \\ \text{subject to} \quad & Bx = d, \\ & A^T x = 0, \\ & -v \leq x \leq v. \end{align*} This isn't guaranteed to find the sparsest solution but is generally speaking relatively successful at that. The idea is that the $\ell_1$ norm is the closest convex norm to the so-called $\ell_0$ norm, which isn't really a norm but simply counts the number on nonzeros of a vector.