Weak NP-Hardness for the 2-D L 0 -Norm InSAR Phase Unwrapping

Two-dimensional (2-D) phase unwrapping (PU) is an essential step in interferometric synthetic aperture radar (InSAR) analysis. Although the L ⁰ -norm PU method is desired, it is nondeterministic polynomial (NP)-hard. Thus, many PU methods have been proposed to find near-optimal solutions of the L ⁰ -norm. As PU is an ill-posed problem, it is difficult to choose the method with the most accurate solution unless reference data are available. In this letter, we prove that the NP-hardness of the L ⁰ -norm is weak, suggesting that the α-approximation algorithm of the L ⁰ -norm can be devised, i.e., the obtained near-optimal solutions can be within a factor of α of the L ⁰ -norm optimal value. The primary contribution of the proof is that the α value of each obtained PU solution can be considered as a new index to assess the PU performance without using reference data. The validity and effectiveness of the α-based index have been verified using simulated and acquired interferometric datasets and three PU methods.