10
$\begingroup$

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<<n$.

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.

$\endgroup$
23
  • 2
    $\begingroup$ 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. $\endgroup$ Sep 6, 2021 at 11:49
  • 2
    $\begingroup$ @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. $\endgroup$ Sep 10, 2021 at 1:51
  • 2
    $\begingroup$ @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. $\endgroup$ Sep 29, 2021 at 23:39
  • 2
    $\begingroup$ 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. $\endgroup$ Sep 30, 2021 at 4:08
  • 2
    $\begingroup$ 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. $\endgroup$ Sep 30, 2021 at 4:11

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .