This paper addresses the problem of reconstructing a discrete-time signal from incomplete frequency samples. The authors show that if the signal is sparse and the set of frequencies used for sampling is randomly chosen, then the signal can be exactly reconstructed with high probability by solving a convex optimization problem. Specifically, they prove that for a signal \( f \in \mathbf{C}^N \) supported on a set \( T \) of size \( |T| \leq \alpha(M) \cdot (\log N)^{-1} \cdot |\Omega| \), where \( \Omega \) is a randomly chosen set of frequencies of mean size \( \tau N \), the solution to the \( \ell_1 \) minimization problem \[ \min_g \sum_{t=0}^{N-1} |g(t)|, \quad \text{subject to } \hat{g}(\omega) = \hat{f}(\omega) \text{ for all } \omega \in \Omega, \] is unique and equal to \( f \) with probability at least \( 1 - O(N^{-M}) \). The authors also provide numerical values for \( \alpha \) and discuss extensions to higher dimensions and other setups. The methodology is based on duality theory and random matrix theory, and the results are connected to uncertainty principles in signal processing.This paper addresses the problem of reconstructing a discrete-time signal from incomplete frequency samples. The authors show that if the signal is sparse and the set of frequencies used for sampling is randomly chosen, then the signal can be exactly reconstructed with high probability by solving a convex optimization problem. Specifically, they prove that for a signal \( f \in \mathbf{C}^N \) supported on a set \( T \) of size \( |T| \leq \alpha(M) \cdot (\log N)^{-1} \cdot |\Omega| \), where \( \Omega \) is a randomly chosen set of frequencies of mean size \( \tau N \), the solution to the \( \ell_1 \) minimization problem \[ \min_g \sum_{t=0}^{N-1} |g(t)|, \quad \text{subject to } \hat{g}(\omega) = \hat{f}(\omega) \text{ for all } \omega \in \Omega, \] is unique and equal to \( f \) with probability at least \( 1 - O(N^{-M}) \). The authors also provide numerical values for \( \alpha \) and discuss extensions to higher dimensions and other setups. The methodology is based on duality theory and random matrix theory, and the results are connected to uncertainty principles in signal processing.