One of the biggest breakthroughs in theoretical mathematics for a long time was compressed sensing. A paper by Candes et al. showed that theoretically, we can get a perfect reconstruction from the subsampled Fourier-domain image. In other words, when the signal we are trying to reconstruct is sparse or sparsely structured, then it is possible to perfectly reconstruct it from fewer measurements. But there are some practical requirements for this to work – we don’t need to sample randomly, rather we need to sample incoherently – though in practice, people just end up sampling randomly. Additionally, it takes the same time to sample a full column or half a column, so in practice we also sample entire columns.
L’une des plus grandes percées en mathématiques théoriques est la détection comprimée. Un article de Candes et al. a montré que théoriquement, nous pouvons obtenir une reconstruction parfaite à partir de l’image du domaine de Fourier sous-échantillonnée. En d’autres termes, lorsque le signal que nous essayons de reconstruire est épars ou peu structuré, il est alors possible de le reconstruire parfaitement à partir de moins de mesures. Mais pour que cela fonctionne, il y a certaines conditions pratiques à remplir : nous n’avons pas besoin d’échantillonner au hasard mais plutôt d’échantillonner de manière incohérente, bien qu’en pratique, les gens finissent par échantillonner au hasard. En outre, il faut le même temps pour échantillonner une colonne entière ou une demi-colonne, donc en pratique nous échantillonnons aussi des colonnes entières.