Recovery of Integer Images from Minimal DFT Measurements: Uniqueness and Inversion Algorithms
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908964560568320 |
|---|---|
| author | Levinson, Howard W Viviano, Isaac |
| author_facet | Levinson, Howard W Viviano, Isaac |
| contents | Exact reconstruction of an image from measurements of its Discrete Fourier Transform (DFT) typically requires all DFT coefficients to be available. However, incorporating the prior assumption that the image contains only integer values enables unique recovery from a limited subset of DFT coefficients. This paper develops both theoretical and algorithmic foundations for this problem. We use algebraic properties of the DFT to define a reduction from two-dimensional recovery to several well-chosen one-dimensional recoveries. Our reduction framework characterizes the minimum number and location of DFT coefficients that must be sampled to guarantee unique reconstruction of an integer-valued image. Algorithmically, we develop reconstruction procedures which use dynamic programming to efficiently recover an integer signal or image from its minimal set of DFT measurements. While the new inversion algorithms still involve NP-hard subproblems, we demonstrate how the divide-and-conquer approach drastically reduces the associated search space. To solve the NP-hard subproblems, we employ a lattice-based framework which leverages the LLL approximation algorithm to make the algorithms fast and practical. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_11949 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Recovery of Integer Images from Minimal DFT Measurements: Uniqueness and Inversion Algorithms Levinson, Howard W Viviano, Isaac Numerical Analysis 68U10, 90C39, 90C10, 65T50 Exact reconstruction of an image from measurements of its Discrete Fourier Transform (DFT) typically requires all DFT coefficients to be available. However, incorporating the prior assumption that the image contains only integer values enables unique recovery from a limited subset of DFT coefficients. This paper develops both theoretical and algorithmic foundations for this problem. We use algebraic properties of the DFT to define a reduction from two-dimensional recovery to several well-chosen one-dimensional recoveries. Our reduction framework characterizes the minimum number and location of DFT coefficients that must be sampled to guarantee unique reconstruction of an integer-valued image. Algorithmically, we develop reconstruction procedures which use dynamic programming to efficiently recover an integer signal or image from its minimal set of DFT measurements. While the new inversion algorithms still involve NP-hard subproblems, we demonstrate how the divide-and-conquer approach drastically reduces the associated search space. To solve the NP-hard subproblems, we employ a lattice-based framework which leverages the LLL approximation algorithm to make the algorithms fast and practical. |
| title | Recovery of Integer Images from Minimal DFT Measurements: Uniqueness and Inversion Algorithms |
| topic | Numerical Analysis 68U10, 90C39, 90C10, 65T50 |
| url | https://arxiv.org/abs/2510.11949 |