Oblivious near-optimal sampling for multidimensional signals with Fourier constraints

Xingyu Xu, Yuantao Gu
Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, PMLR 206:4532-4555, 2023.

Abstract

We study the problem of reconstructing a continuous multidimensional signal from a small number of samples under Fourier constraints assuming that the Fourier power spectrum of the signal has some desirable properties, e.g. being compactly supported, being sparse. We further assume that the Fourier constraint can be expressed as a prior distribution on the Fourier power spectrum, which subsumes the aforementioned examples. The study of sampling and reconstructing in this vein has attracted much attention with a long history. In this paper, we are interested in finding oblivious sampling strategies, that is, sampling without knowing what specific constraint is put on the Fourier power spectrum. We show that it is possible to obliviously sample a Fourier-constrained multidimensional signal with a near-optimal (up to a logarithmic factor) number of samples that guarantee successful reconstruction, partially answering an open question in Avron et al. (2019) which considered the $1$-dimensional case. Our approach highlights a phenomenon that is unique for dimension $d\ge 2$ that the sampling strategy should depend on the geometry of the region on which the signal is to be reconstructed, unlike the case $d=1$ where all regions are of the form $[a,b]$ which are all geometrically equivalent. Our proof, using tools from convex geometry, also illuminates an idea obscured in $d=1$, that to reconstruct a signal in a given region, it can be helpful to take some samples outside that region.

Cite this Paper

BibTeX
@InProceedings{pmlr-v206-xu23f, title = {Oblivious near-optimal sampling for multidimensional signals with Fourier constraints}, author = {Xu, Xingyu and Gu, Yuantao}, booktitle = {Proceedings of The 26th International Conference on Artificial Intelligence and Statistics}, pages = {4532--4555}, year = {2023}, editor = {Ruiz, Francisco and Dy, Jennifer and van de Meent, Jan-Willem}, volume = {206}, series = {Proceedings of Machine Learning Research}, month = {25--27 Apr}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v206/xu23f/xu23f.pdf}, url = {https://proceedings.mlr.press/v206/xu23f.html}, abstract = {We study the problem of reconstructing a continuous multidimensional signal from a small number of samples under Fourier constraints assuming that the Fourier power spectrum of the signal has some desirable properties, e.g. being compactly supported, being sparse. We further assume that the Fourier constraint can be expressed as a prior distribution on the Fourier power spectrum, which subsumes the aforementioned examples. The study of sampling and reconstructing in this vein has attracted much attention with a long history. In this paper, we are interested in finding oblivious sampling strategies, that is, sampling without knowing what specific constraint is put on the Fourier power spectrum. We show that it is possible to obliviously sample a Fourier-constrained multidimensional signal with a near-optimal (up to a logarithmic factor) number of samples that guarantee successful reconstruction, partially answering an open question in Avron et al. (2019) which considered the $1$-dimensional case. Our approach highlights a phenomenon that is unique for dimension $d\ge 2$ that the sampling strategy should depend on the geometry of the region on which the signal is to be reconstructed, unlike the case $d=1$ where all regions are of the form $[a,b]$ which are all geometrically equivalent. Our proof, using tools from convex geometry, also illuminates an idea obscured in $d=1$, that to reconstruct a signal in a given region, it can be helpful to take some samples outside that region.} }
Endnote
%0 Conference Paper %T Oblivious near-optimal sampling for multidimensional signals with Fourier constraints %A Xingyu Xu %A Yuantao Gu %B Proceedings of The 26th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2023 %E Francisco Ruiz %E Jennifer Dy %E Jan-Willem van de Meent %F pmlr-v206-xu23f %I PMLR %P 4532--4555 %U https://proceedings.mlr.press/v206/xu23f.html %V 206 %X We study the problem of reconstructing a continuous multidimensional signal from a small number of samples under Fourier constraints assuming that the Fourier power spectrum of the signal has some desirable properties, e.g. being compactly supported, being sparse. We further assume that the Fourier constraint can be expressed as a prior distribution on the Fourier power spectrum, which subsumes the aforementioned examples. The study of sampling and reconstructing in this vein has attracted much attention with a long history. In this paper, we are interested in finding oblivious sampling strategies, that is, sampling without knowing what specific constraint is put on the Fourier power spectrum. We show that it is possible to obliviously sample a Fourier-constrained multidimensional signal with a near-optimal (up to a logarithmic factor) number of samples that guarantee successful reconstruction, partially answering an open question in Avron et al. (2019) which considered the $1$-dimensional case. Our approach highlights a phenomenon that is unique for dimension $d\ge 2$ that the sampling strategy should depend on the geometry of the region on which the signal is to be reconstructed, unlike the case $d=1$ where all regions are of the form $[a,b]$ which are all geometrically equivalent. Our proof, using tools from convex geometry, also illuminates an idea obscured in $d=1$, that to reconstruct a signal in a given region, it can be helpful to take some samples outside that region.
APA
Xu, X. & Gu, Y.. (2023). Oblivious near-optimal sampling for multidimensional signals with Fourier constraints. Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 206:4532-4555 Available from https://proceedings.mlr.press/v206/xu23f.html.

Related Material