In light of the challenges highlighted by David Donoho and Jared Tanner in Precise Undersampling Theorems, I am wondering (aloud) if there would be an interest in crowdsourcing (a la polymath) a large set of computations in support of Challenges A.B,E and F for different measurements ensembles (beyond the already exhaustive set of Donoho and Tanner) and different solvers, a situation we know has led to an explosion of possibilities. As a reminder, the challenges that could be helped with a larger set of phase transition computations include:
- A. Characterize Universality classes of Gaussian Phase Transitions. We have shown that many ‘random’ matrix ensembles yield phase transitions matching those of Gaussian matrices. Characterize the precise universality class of such matrices.
- B. Discover New Transitions for (LP) and (P1) Many but not all matrix ensembles yield phase transitions matching those of Gaussian matrices. Discover more examples which don’t, and which are also interesting matrix ensembles, either because the phase transition is better or because the matrix is explicit and deterministic.
- E. Derive phase transitions of new algorithms. Discover formal theory which precisely locates phase transitions that have been observed for other algorithms
- F. Derive phase transitions for Accurate Recovery in Noise. When noise is present we can no longer expect exact reconstruction, but we can expect stable recovery (error at most proportional to noise level). phase transitions have been observed empirically for such properties. Formal results would give undersampling theorems in noise. Derive such results.
At a minimum, the intent here is to define/write a generic script that could be run in a distributed manner a la Folding@home. If you are interested and have specific ideas on how one could go about this, please contact me by e-mail or write in the comment section so we can start a discussion on the subject.
In the end, a project like this one could be expanded on the cloud like the application Pedro and I just wrote as a Facebook app.