Training-free Ultra Small Model for Universal Sparse Reconstruction in Compressed Sensing

Despite large models drive unprecedented growth in data and model parameters, many real-world problems prioritize interpretability and generality, and lack sufficient training data. For instance, in Compressed Sensing (CS) where sparse reconstruction solves underdetermined systems, traditional iterative methods remain the practical choice due to their interpretability and out-of-the-box applicability to arbitrary conditions, but suffer from poor quality and inefficiency at low sampling rates. To address this, we propose Coefficients Learning (CL), a novel training-free framework for sparse reconstruction. CL employs ultra-small neural models with only <inline-formula><tex-math notation="LaTeX">$n$</tex-math><alternatives><mml:math><mml:mi>n</mml:mi></mml:math><inline-graphic xlink:href="tang-ieq1-3680162.gif"/></alternatives></inline-formula> trainable parameters for a length-<inline-formula><tex-math notation="LaTeX">$n$</tex-math><alternatives><mml:math><mml:mi>n</mml:mi></mml:math><inline-graphic xlink:href="tang-ieq2-3680162.gif"/></alternatives></inline-formula> signal. It retains the interpretability and generality of traditional iterative methods by adopting their residual-based solving process, while enhancing efficiency and accuracy by replacing closed-form solutions with automatic differentiation and embedding prior knowledge into the model losses. We evaluate CL extensively on synthetic and real one-dimensional and two-dimensional signals. A detailed analysis is first conducted using an implemented CLOMP. To demonstrate general applicability, CL is also implemented on three types of classic iterative CS reconstruction methods. Results show that CL maintains the generality of iterative methods while significantly boosting accuracy. Although it adds minor overhead for convex optimization or message-passing methods, it achieves efficiency gains of 100 to 1000 times for greedy algorithms. On the tested nine diverse image datasets, CL improves median reconstruction accuracy by approximately 163%, 78%, and 35% at sampling rates of 0.04, 0.25, and 0.5, respectively, compared to classic iterative methods. This training-free CS reconstruction method can truly empower countless industrial or medical machines that rely on sparse solution.