We introduce a novel framework to reconstruct highly undersampled signals from their measurements using a correlated signal as an aid. The correlated signal, called side information, need not be close or similar to the signal to reconstruct. Thus, our framework applies to the case in which the signals are multimodal. We use two main ingredients: the theory of l1–l1 minimization, which establishes precise reconstruction guarantees of sparse signals using a similar signal as an aid, and a set of training data consisting of several examples of pairs of the signal to reconstruct and the side information. We adopt a statistical framework where the training and the test data are drawn from the same joint distribution, which is assumed unknown. Our main insight is that a quantity arising in the l1–l1 minimization theory to measure the quality of the side information can be written as the 0-1 loss of a classification problem. Therefore, our problem can be solved with classification methods, such as support vector machines. Furthermore, using statistical learning theory, we provide guarantees for our method. Specifically, the expected value of the side information quality decreases with O(1/√T), where T is the number of training samples. Simulations with synthetic data validate our approach.