This note demonstrates that we can stably recover rank-rToeplitz matrix$\pmb {X}\in \mathbb {R}^{n\times n}$from a number of rank-one subgaussian measurements on the order of$r\log ^{2} n$with an exponentially decreasing failure probability by employing a nuclear norm minimization program. Our approach utilizes descent cone analysis through Mendelson’s small ball method with the Toeplitz constraint. The key ingredient is to determine the spectral norm of the random matrix of the Toeplitz structure, which may be of independent interest. This improves upon earlier analyses and resolves the conjecture in Chen et al. (IEEE Transactions on Information Theory, 61(7):4034–4059, 2015).

We investigate the phase retrieval problem perturbed by dense bounded noise and sparse outliers that can change an adversarially chosen s-fraction of the measurement vector. The adversarial sparse outliers may depend on both the observation and measurements. We demonstrate that the nonlinear least absolute deviation based on amplitude measurements can tolerate adversarial outliers up to a fraction ofs*, 1≈ 0.2043, while the intensity-based model can tolerate a fraction ofs*, 2≈ 0.1185. Furthermore, we construct adaptive counterexamples to show that these thresholds are theoretically sharp, thereby showing the presentation of phase transition in the adversarial phase retrieval problem when the corruption fraction exceeds the sharp thresholds. This implies that the amplitude-based model exhibits superior adversarial robustness in comparison with the intensity-based model. Corresponding experimental results are presented to further illustrate our theoretical findings. To the best of our knowledge, our results provide the first theoretical examination of the differences in robustness performance between amplitude and intensity measurement. A crucial aspect of our analysis is the exploration of the exact distribution of a combination of two non-independent Gaussian random variables, leading to the presentation of novel probability density functions to derive the sharp thresholds.