Suppose a ''brute-force'' algorithm is designed to systematically select from the first $n$ columns of an $m \times (n+1),$ $m<n$ augmented matrix $G$ representing a consistent underdetermined system $Ax=b$ with $b \neq 0$ and $A$ of full row rank. Row-swapping if necessary, the algorithm first checks by exchanging each of the first $n$ columns with $e_1$ (skipping columns whose row entries are nonzero if and only if $b$ has a zero entry in these respective rows), then proceeding to exchange all $n \choose 2$ columns for $e_1$ and $e_2$ (again, row exchanging from below if necessary), and so forth. The algorithm halts when some selection of $r$ rows is row reduced to $e_1, \ldots, e_r, r<m$ and only zeros appear in the other $m-r$ rows of the target column $n+1,$ or halts by reporting all solutions recovered from row reducing (at most) $n \choose m$ of the first $n$ columns of the augmented matrix.

When this algorithm halts, must the reported solution always recover nonzeros in the entries for the successfully discovered support for a minimal support solution?

I am using the above algorithm in my dissertation as a tool for drawing conclusions about the efficiency of an algorithm of my own creation.

At first blush, the answer to this question seems to be "yes." Given the sweeping nature of such an algorithm, a minimal support solution of weight $d$ that is discovered while the algorithm reaches the stage of operating on all $n \choose d+1$ columns should have been discovered during the previous loop that operated on all $n \choose d$ columns, halting the program at that depth.

However, when actually describing this aspect about this "trial and error" method, it no longer seems obvious to me, though I still think it is true. What if (without loss of generality) row operations turning the $d-1$ columns matching the indices of minimal support $k_1, \ldots, k_{d-1}$ caused the last support column $k_d$ to appear ineligible?

My attempt to prove this conjecture is as follows. Assume that the situation in the previous paragraph occurs: columns $k_1, \ldots, k_{d-1}$ are exchanged for $e_1, \ldots, e_{d-1}$ (not necessarily in that order). Then if the column of support $k_d$ of $G$ appears to not be a candidate because of previous row operations, column $k_d$ has nonzero row entries in $d$ to $m$ if and only if the target column $n+1$ is zero among these same row entries. Since $e_1, \ldots, e_{d-1}$ have zeros in rows $d$ through $m,$ any solution involving a nonzero multiple of column $k_d$ cannot equal column $n+1,$ contradicting the assumption that $k_1, \ldots, k_d$ were indices of minimal support.

This proof seems insufficient, as it assumes $k_d$ is to be the last column of true support chosen, and depends on aspects unique to this case. I attempted to try again with an inductive proof on the size of support of the minimal support solution - this size is one if and only if one column of $A$ is a direct nonzero multiple of $b,$ so the minimal support solution must be identified after exchanging the correct column for $e_1$ (again, row-swapping if necessary) and finding the nonzero multiple in row $1$ of column $n+1$ and $0$ elsewhere. Inductively, if a support of size $d$ returns a solution that has at least $t$ zeros in the rows indexed by the indices of placement for $e_1, \ldots, e_d,$ the program would have identified this solution earlier in the $d-t$ loop by the inductive assumption. This, too, does not seem like a correct employment of induction, as it assumes the case for all solutions of support $2, \ldots, d-1,$ and not just for $d-1.$

This seems like a result that should be elementary, but it is bothering me that I can't confidently endorse any attempts I've made at a proof. Any suggestions for improvement in these attempts would be greatly appreciated!

  • 1
    $\begingroup$ Isn't this this idea of the orthogonal matching pursuit, in a way? Have you looked into the paper of Tong Zhang about recovery via restricted isometry properties? $\endgroup$ – Jean-Luc Bouchot Apr 4 '17 at 19:57
  • $\begingroup$ I have not looked at Zhang, but I have seen papers by Tao and Donoho, and more specific by Bioglio et. al. for OMP for finite fields (and have in fact contacted them), and have read parts of the text from Foucart. Here, though, is a combinatorial full-search recovery, where unconstrained total recovery is the interest, rather than improved-time approximation. $\endgroup$ – Thomas Rasberry Apr 6 '17 at 13:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.