Finding a minimal set of equations that determine a variable.

I have a system of $$m$$ linear equations on $$n$$ variables, which I'm representing as $$Ax=b$$, with $$A$$ an $$m\times n$$ matrix representing the equations and $$b$$ an $$\mathbb R^m$$ vector representing the constants of the equations. I'm given that there exists a solution $$s\in\mathbb R^n$$ (i.e., $$As=b$$) and that $$m<.

My goal is the following:

1. Find which variables are determined (i.e., for which there are no solutions with values different than the one in $$s$$).
2. For each variable in 1., find a minimal subsystem of equations which determines that variable. By minimal, I mean the following: the subsystem determines the variable as in 1., and no proper subset of the subsystem does this. I want to find any such minimal subsystem: which one I pick is irrelevant to me.

Progress:

I've solved 1. by computing the nullspace of $$A$$, and looking for those variables for which none of the basis vectors of the null-space have a non-zero coefficient.

I've attempted to solve 2. by computing the pseudo-inverse of $$A$$ and looking at which coefficients in the row corresponding to the chosen variable are non-zero. This approach doesn't work, though, since the pseudo-inverse $$P$$ minimizes the Frobenius norm among all matrices $$X$$ such that $$X\cdot b=s$$. This norm is an $$L_2$$ norm, but what we really want is an $$L_0$$ norm, since we want to minimize the number of non-zero elements in the matrix. Of course, finding the matrix minimizing the $$L_0$$ norm is an NP problem, so that's not a valid approach for me.

Are there any other approaches I'm missing? Perhaps some heuristic methods? I'm struggling to find anything on this subject.

• Good lord, I haven't seen this question somehow, and thanks to that meta post I got here. I'm just letting you know I retain an interest, and I'll get back when I can. Thanks and +1. Sep 6, 2021 at 11:49
• @PeterKošinár It works, but it's very computationally expensive. A rough time estimate would be $O(n\cdot m^2\cdot m^2n)=O(n^2m^4)$, which is awful. With my data, in which $m\sim10^6$ and $n\sim10^9$, it's just not possible. Sep 10, 2021 at 1:51
• @DonThousand Thank you once again, and I'm sorry to keep you waiting. I always take time over answers, even when I have them in place, so I'll try to get this one wrapped up when I can. Sep 29, 2021 at 23:39
• I give up : I've tried hard to look at the matrix part of things, but everywhere I go I'm seeing only the minimization of the $L_0$ norm for the vector $s$ i.e. picking $s$ such that it has the least number of non-zero entries. Not once do I unfortunately see the minimization over matrices. I know that matrices are vectors, but it's still quite surprising that nobody considered the same problem as you. I found some randomized algorithms and $L_0$-regularization algorithms for the vector case : these could work for the matrix case, but I'm not sure, that's the problem. Sep 30, 2021 at 4:08
• For example , it is known that changing $L_0$ to $L_p$ for $p \approx 0$ gives a feasible problem that is a non-linear program and has methods available. One can provide other regularizations as well ($L_1$, $\frac{L_2}{L_1}$ etc.) Next, one can "Bayesian-learn" the data by fitting it into a certain distribution, for which the $L_p$ regularized NLP runs quickly and converges to an $L_0$ global minimizer as $p \to 0$. This is what I could find with about 2-3 hours of work, and I'm unhappy that I couldn't bring more to the table. Sep 30, 2021 at 4:11

Of course, if $$s_0$$ is any solution then $$s$$ is a solution iff $$A(s-s_0)=0$$, and we can pass to the question of which rows of $$A$$ imply that some coordinate $$x_i$$ of every $$x$$ with $$Ax=0$$ is zero.
Suppose $$Ax=0$$ implies $$x_1=0$$. Set $$x_1=1$$ in the equations given by $$A$$. The equations are now incompatible. This is still a linear system, in one less variable, given by some $$Mv=c$$. (If $$A$$ had columns $$v_1, ..., v_n$$ then $$c=-v_1$$ and $$M$$ has columns $$v_2, ..., v_n$$.) By Fredholm alternative, this means that some linear combination of the equations gives 0=1, i.e. there is a subset of rows of $$M$$ whose span is lower-dimensional than the span of the corresponding rows of $$A$$. We are looking for a minimal incompatible subsystem, i.e. a minimal such collection.
Start with any such collection. Suppose the corresponding rows of $$M$$ spanning a space $$V$$. Select from these rows a basis of $$V$$, and add more rows one by one, until the dimension spaned by corresponding rows of $$A$$ jumps. Then pick a subset that is a basis for the space spanned by these rows of A. At that point, we have a minimal collection of equations implying $$x_1=0$$.