Robust instance optimal phase-only compressed sensing

Abstract Phase-only compressed sensing (PO-CS) concerns the recovery of sparse signals from the phases of complex measurements. Recent results show that sparse signals in the standard sphere $\mathbb{S}^{n-1}$ can be exactly recovered from complex Gaussian phases by a linearization procedure, which recasts PO-CS as linear compressed sensing and then applies (quadratically constrained) basis pursuit to obtain $\textbf{x}^\sharp$. This paper focuses on the instance optimality and robustness of $\textbf{x}^{\sharp }$. First, we strengthen the non-uniform instance optimality of Jacques and Feuillen (2021, IEEE Trans. Inf. Theory, 67, 4150–4161) to a uniform one over the entire signal space. We show the existence of some universal constant $C$ such that $\|\textbf{x}^\sharp -\textbf{x}\|_{2}\le Cs^{-1/2}\sigma _{\ell _{1}}(\textbf{x},\varSigma ^{n}_{s})$ holds for all $\textbf{x}$ in the unit Euclidean sphere, where $\sigma _{\ell _{1}}(\textbf{x},\varSigma ^{n}_{s})$ is the $\ell _{1}$ distance of $\textbf{x}$ to its closest $s$-sparse signal. This is achieved by showing that the new sensing matrices corresponding to all approximately sparse signals simultaneously satisfy restricted isometry property. Second, we investigate the estimator’s robustness to noise and corruption. We show that dense noise with entries bounded by some small $\tau _{0}$, appearing either prior or posterior to retaining the phases, increments $\|\textbf{x}^\sharp -\textbf{x}\|_{2}$ by $O(\tau _{0})$. This is near-optimal (up to log factors) for any algorithm. On the other hand, adversarial corruption, which changes an arbitrary $\zeta _{0}$-fraction of the measurements to any phase-only values, increments $\|\textbf{x}^\sharp -\textbf{x}\|_{2}$ by $O(\sqrt{\zeta _{0}\log (1/\zeta _{0})})$. We demonstrate the tightness of this result via a partial analysis under suboptimal noise parameter and numerical evidence, while showing that the impact of sparse corruption can be eliminated: to this end, we propose an extended linearization approach that can exactly recover $\textbf{x}$ from the corrupted phases. The developments are then combined to yield a robust instance optimal guarantee that resembles the standard one in linear compressed sensing.