Probabilistic and nonlinear compressive sensing
This work addresses convergence speed and parameter recovery challenges in compressive sensing for researchers in signal processing and machine learning, with incremental improvements in linear methods and novel theoretical insights into nonlinear cases.
The paper tackles the problem of slow convergence in best subset selection by introducing a smooth probabilistic reformulation of ℓ₀ regularized regression that enables exact gradient computation, achieving faster convergence than Monte Carlo approaches and outperforming compressive sensing algorithms like IHT and Lasso across various settings. It also investigates nonlinear compressive sensing, showing theoretically that global optimum enforces parameter recovery up to symmetries in the infinite-data limit, but empirically finds exact recovery is not possible even with symmetries due to a rebound effect where teacher and student configurations diverge despite decreasing test loss.
We present a smooth probabilistic reformulation of $\ell_0$ regularized regression that does not require Monte Carlo sampling and allows for the computation of exact gradients, facilitating rapid convergence to local optima of the best subset selection problem. The method drastically improves convergence speed compared to similar Monte Carlo based approaches. Furthermore, we empirically demonstrate that it outperforms compressive sensing algorithms such as IHT and (Relaxed-) Lasso across a wide range of settings and signal-to-noise ratios. The implementation runs efficiently on both CPUs and GPUs and is freely available at https://github.com/L0-and-behold/probabilistic-nonlinear-cs. We also contribute to research on nonlinear generalizations of compressive sensing by investigating when parameter recovery of a nonlinear teacher network is possible through compression of a student network. Building upon theorems of Fefferman and Markel, we show theoretically that the global optimum in the infinite-data limit enforces recovery up to certain symmetries. For empirical validation, we implement a normal-form algorithm that selects a canonical representative within each symmetry class. However, while compression can help to improve test loss, we find that exact parameter recovery is not even possible up to symmetries. In particular, we observe a surprising rebound effect where teacher and student configurations initially converge but subsequently diverge despite continuous decrease in test loss. These findings indicate fundamental differences between linear and nonlinear compressive sensing.