Learning Trees of $\ell_0$-Minimization Problems
This work addresses the challenge of solving sparse optimization problems in practical applications where existing methods like RIP-based convex minimization are insufficient, offering a novel approach for mathematicians and researchers in computational mathematics.
The paper tackles the NP-hard problem of finding minimally sparse solutions in under-determined linear systems by introducing adaptable classes that become tractable after training on a curriculum of increasingly difficult samples, with the result being a candidate model for human mathematicians to handle flexible subclasses effectively.
The problem of computing minimally sparse solutions of under-determined linear systems is $NP$ hard in general. Subsets with extra properties, may allow efficient algorithms, most notably problems with the restricted isometry property (RIP) can be solved by convex $\ell_1$-minimization. While these classes have been very successful, they leave out many practical applications. In this paper, we consider adaptable classes that are tractable after training on a curriculum of increasingly difficult samples. The setup is intended as a candidate model for a human mathematician, who may not be able to tackle an arbitrary proof right away, but may be successful in relatively flexible subclasses, or areas of expertise, after training on a suitable curriculum.