Introduction
Super Resolution (SR) is the process of recovering high-frequency details, such as sharp point sources or "spikes," from low-frequency, blurred observations. While SR is well-understood in 1D and 2D, extending these techniques to higher dimensions or complex geometries has historically been hindered by the "dimension barrier." Traditional methods rely on the Fejér-Riesz theorem, which does not generalize beyond two dimensions or to non-standard domains like spheres. This paper presents a novel framework that leverages the Lasserre hierarchy of semidefinite programming (SDP) to achieve exact SR in any dimension and on semi-algebraic domains.
Methodology: The Moment-SOS Hierarchy
The core innovation of this work is shifting the focus from the dual optimization problem to the primal problem. The authors utilize the Moment-Sum-of-Squares (SOS) hierarchy, also known as the Lasserre hierarchy.
Key Components
- Jordan Decomposition: The unknown signal is treated as a signed measure $\mu$, decomposed into positive and negative components ($\mu = \mu_+ - \mu_-$).
- Moment Sequences: Instead of direct signal recovery, the method identifies the "moments" (statistical averages) of the signal.
- Semidefinite Programming (SDP): A sequence of SDP relaxations is solved. As the relaxation order $k$ increases, the solution converges to the true signal.
- Rank Condition: A critical feature is the "certificate of success." When the rank of the moment matrix stabilizes, the algorithm has identified the exact discrete spikes, which can then be extracted via linear algebra.
Experimental Validation
The authors demonstrate the versatility of the Moment-SOS approach through several synthetic benchmarks, including disconnected 1D domains, 2D boxes, and 3D spheres.
1D and 2D Recovery
The method was tested on a disconnected 1D domain and a 2D box. In both cases, the hierarchy successfully recovered the exact locations and amplitudes of the spikes.
For the 2D case, the algorithm processed moments up to degree 12, achieving high-fidelity reconstruction in under 3 seconds. The visualization below shows the successful localization of multiple peaks on a 2D domain.
3D Sphere
The framework's flexibility is further proven by localizing points on a 3D sphere using 56 spherical harmonic-like measurements. This task was completed in under 20 seconds, highlighting the method's computational efficiency even in higher dimensions.
Key Insights and Results
- Semi-Algebraic Flexibility: The method applies to any "basic semi-algebraic set," encompassing a wide variety of shapes used in physics and engineering.
- Exactness and Efficiency: The approach provides the first exact SDP formulation for SR in dimensions greater than two. Recovery times range from 0.2 seconds for 1D problems to under 20 seconds for 3D spherical problems.
- The "Aha" Moment on Rank: The realization that the rank of the moment matrix indicates when the "atomic" solution (the spikes) has been reached allows users to know for certain if they have the exact answer.
Limitations and Future Work
Despite its power, the method faces challenges in scaling. The size of the SDPs grows polynomially with dimension and relaxation order, which may limit applications involving extremely high-frequency data. Additionally, while the current work focuses on exact recovery, future research will address robustness to measurement noise and provide "a priori" estimates for the required relaxation order $k$.
Summary updated