Can there be underdetermined linear systems whose set of minimal support solutions is infinite?

Question

Let $A \in \mathbb{F}^{m \times n},$ $m<n,$ and let $b \in \mathbb{F}^{m \times n}$ be such that the system $Ax=b$ is consistent. Does it follow that the set $X$ of minimal support solutions of this system $$ X:= \arg \min\limits_{x:Ax=b, x \in \mathbb{F}^n}\{\|x\|_0\}$$ is such that $|X| < \infty?$

I thought of this question randomly today while thinking about improvements I can make to my dissertation. Oddly, even though I have been studying compressive sensing for almost a year now, I have never thought about this question, nor do I recall seeing any results in the literature or in Foucart and Rauhut's text.

It seems almost immediate intuitively that the answer to this question is ``yes'' given that the problem involves vector spaces that are not infinite.

The linear algebraic interpretation, and my attempt at an actual proof, is that all minimal support solutions to, say, the consistent system $Ax=b$ where $A \in \mathbb{R}^{3 \times n}, b \in \mathbb{R}^3,$ $3 < n,$ are represented by taking any triplet of $n\choose{3}$ columns and row reducing the system to turn these columns into identity columns -the order of appearance of the identity columns in the modified system won't matter, and if the columns are dependent, at least one variable is free; the minimal support solution will set any coefficients of $x$ matching the indices of any free variables, and all the other $n-3$ elements of $x,$ to zero. Therefore $|X| \leq $ $n \choose 3$ $<\infty$.

This spells out the geometric intuition that drove me to my quick answer; a line, plane, or the whole space $\mathbb{R}^3$ (which can be representative of $x$ if $\|x\|_0 \leq 3$) must cross a unique point with lowest weight somewhere (corresponding to setting free variables to zero after reduction of my system to exchange my three column choices with identity columns).

I did not use any properties unique to real fields, nor did I use the particular row rank of $3,$ having merely assumed that $3<n,$ so it seems like I can rewrite the above argument for a comprehensive proof.

I am still uneasy with this line of thinking for some reason. I feel like there is either a much more elegant, simple, and direct formal proof, or else a glaringly obvious counterexample (perhaps over $\mathbb{C}$) that disproves this conjecture.

I apologize ahead of time if this question is too trivial for this forum, but I felt this belonged here rather than on Mathematics SE, as compressive sensing seems to be at the research level in general.

Answer 1

If the minimal $\|x\|_0$ for a solution is $k$, any solution with $\|x\|_0 = k$ has support one of the ${n \choose k}$ subsets of $n$ with cardinality $k$. The $m \times k$ submatrix $A_S$ of $A$ consisting of these columns has the property that $A_S x = b$ has a solution with all entries nonzero, but no solution with any entries $0$. That implies that the solution of $A_S x = b$ is unique (if there were two different solutions $y$ and $z$, they would differ on some coordinate, and then we could take a solution $y + t (z-y)$ for some $t \in \mathbb F$ to make that coordinate $0$). So we conclude that there are at most ${n \choose k}$ minimal support solutions.