Random column subsets of fixed-sparsity matrices: an unrestricted theorem

For every fixed column sparsity, aspect ratio, and positive singular-value threshold, we prove that a uniformly sampled proportional-size column subset of any sufficiently redundant signed sparse dictionary has a positive fraction of singular values below that threshold, except with exponentially small probability. No hypothesis is imposed on intersections of column supports. The argument combines a covariance polynomial filter, finite signed conditional trajectories, and a common reservoir of sampled columns. A simultaneous-witness lemma converts reconstruction events into a lower bound for an eigenvalue count. A collision coupling transfers its expectation to sampling without replacement, after which a transposition martingale supplies concentration. This gives an affirmative answer in the nontrivial regime of Huang–Rudelson–Tikhomirov's Conjecture 7.1. The proof is analytic; no finite computation is a premise.