Phase Transitions in Recovery of Structured Signals From Corrupted Measurements

DOI10.1109/TIT.2022.3161227zbMATH Open1505.94022arXiv2101.00599OpenAlexW3119963548MaRDI QIDQ5088596

Publication date: 13 July 2022

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: This paper is concerned with the problem of recovering a structured signal from a relatively small number of corrupted random measurements. Sharp phase transitions have been numerically observed in practice when different convex programming procedures are used to solve this problem. This paper is devoted to presenting theoretical explanations for these phenomenons by employing some basic tools from Gaussian process theory. Specifically, we identify the precise locations of the phase transitions for both constrained and penalized recovery procedures. Our theoretical results show that these phase transitions are determined by some geometric measures of structure, e.g., the spherical Gaussian width of a tangent cone and the Gaussian (squared) distance to a scaled subdifferential. By utilizing the established phase transition theory, we further investigate the relationship between these two kinds of recovery procedures, which also reveals an optimal strategy (in the sense of Lagrange theory) for choosing the tradeoff parameter in the penalized recovery procedure. Numerical experiments are provided to verify our theoretical results.

Full work available at URL: https://arxiv.org/abs/2101.00599

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)