Adversarial Phase Retrieval via Nonlinear Least Absolute Deviation [This work was supported in part by the NSFC under grant numbers U21A20426, 12071426 and the National Key Research and Development Program of China under grant number 2021YFA1003500, the Project funded by China Postdoctoral Science Foundation 2023M733114.]

Gao Huang[ School of Mathematical Science, Zhejiang University, Hangzhou 310027, P. R. China, E-mail address<EMAIL_ADDRESS>Song Li[ School of Mathematical Science, Zhejiang University, Hangzhou 310027, P. R. China, E-mail address<EMAIL_ADDRESS>Hang Xu[ Corresponding Author, School of Physics, Zhejiang University, Hangzhou 310027, P. R. China, E-mail address<EMAIL_ADDRESS>
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 exhibit dependence on both the observation and the measurement.

We demonstrate that the nonlinear least absolute deviation based on amplitude measurement can tolerate adversarial outliers
at a fraction of $s^{*,1}\approx0.2043$, while the intensity-based model can tolerate a fraction of $s^{*,2}\approx0.1185$.

Furthermore, we construct adaptive counterexamples to show that

the 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 distinction in robustness performance between amplitude and intensity measurement.
A crucial point of our analysis is that we explore the exact distribution of some combination of two non-independent Gaussian random variables and present the novel probability density functions to derive the sharp thresholds.

Keywords:  Phase Retrieval; Adversarial Sparse Outliers; Nonlinear Least Absolute Deviation; Sharp Thresholds; Amplitude and Intensity Measurement.

§ INTRODUCTION

Recovering a signal from the magnitude of its linear samples, commonly known as phase retrieval, has gained significant attention in various fields due to its wide range of applications,  including X-ray crystallography [30, 28], astronomy [15], microscopy [29], optics [37] and diffraction imaging [5].
Mathematically, the problem consists of recovering an unidentified discrete signal $\pmb{x}_0\in\mathbb{F}^{n}$ with $\mathbb{F} \in \{ \mathbb{R}, \mathbb{C}\}$ from the general measurements
b_i = 𝒜_i(_0) + η_i,  i=1,⋯,m.
Here, $\eta_i \in \mathbb{R}$ represents arbitrary measurement noise and the sample $\mathcal{A}_i(\x_0)$ may be of the two forms: $\vert\langle \pmb{a}_{i},\pmb{x}_0 \rangle\vert$ and $\vert\langle \pmb{a}_{i},\pmb{x}_0 \rangle\vert^{2}$,
called amplitude and intensity measurement respectively with $\pmb{a}_{i} \in \mathbb{F}^{n}$ being the design measurement vectors known as a priori. [33] offers a comprehensive review of the theory and application of phase retrieval, serving as a valuable resource for readers seeking further insight into this subject matter.

A typical approach to recover  $\pmb{x}_0$ is to consider the least squares (LS) approach i.e. $\ell_2$-loss.

Candès et al. in [3] developed a gradient-based method—Wirtinger flow on the objective related to the intensity measurements. Afterwards, some algorithms based on Wirtinger flow emerged, including [7, 38, 43].
[3, 7] focused on intensity measurement, while
[38, 43] studied a variant of Wirtinger flow on the amplitude-based model and showed that the amplitude-based algorithms perform better in computational complexity and sample complexity than the intensity-based algorithms.

Since the $\ell_2$-loss relies heavily on the bounded variance of the noise vectors in most of the existing literature,
the above methods cannot be directly applied when corrupted by heavy-tailed errors or outliers [42, 12].
To deal with this case, $\ell_1$-loss is invoked and this leads to the least absolute deviation (LAD) approach:
min_x ∈𝔽^n  𝒜(_0) - b _1,
where $\mathcal{A}\left(\x_0\right)$ can be amplitude or intensity measurement.
In real-world applications, outliers may be very common in the measurements due to sensor failure and occlusions.
And these failure and occlusions can often be adversarial.
Adversarial outliers[Adversarial outliers are the data points which can be arbitrarily large and may even depend on the measurement system $(\pmb{b}, \pmb{A})$ and ground-truth $\x_0$. For example, the noise $ \tilde{\pmb{\eta}}$ of a response $\pmb{y} = \mathcal{A}(\pmb{x}_0 + \pmb{\eta}) = \mathcal{A}(\pmb{x}_0) + \tilde{\pmb{\eta}}$ is highly dependent on the measurement.] is prevalent in many applications such as video surveillance [23], face recognition [9] and sensor calibration [25].
Dwork et al. [13] first explored the adversarial robust recovery in decoding and
considered the conflict between the adversary, who corrupts a signal, and the decoder, who attempts to reconstruct the message.
There is also a series of work considering robust recovery in the case of measurements being wiped or even adversarially corrupted in various fields including compressed sensing [6, 21], matrix completion [24], robust PCA [31, 10], low-rank matrix recovery [40]. In addition, the adversarial robustness has also been extensively researched in robust high-dimensional statistics during resent years  [22, 11, 10].

However, phase retrieval under outliers or even adversarial outliers was studied in a minority of work. Most of them [17, 25, 18] considered the intensity-based model and took use of PhaseLift [1, 4] to lift the signal vector $\x_0$ into rank-one matrix $\x_0\x_0^\tp$.
[41] demonstrated that amplitude-based cost functions perform better than intensity-based ones by using simulations and experiments, especially when the dataset contains noise or model mis-match.

Furthermore, outliers arise frequently from the phase imaging applications [39, 41] due to various reasons such as detector failures, recording errors, and missing data or even model mis-match. Such mistakes can even be adversarial, thus considering the theoretical robustness performance of the phase retrieval model with adversarial outliers has great practical significance.

In this paper, we first consider the following amplitude measurements corrupted by dense bounded noise and adversarial sparse outliers:

\begin{equation}\label{formu1}
\pmb{b}=\lv\pmb{A}\x_{0}\rv+\pmb{\omega}+\pmb{z},\quad \|\pmb{z}\|_{0}\leq sm,
\end{equation}

where $\A = [\pmb{a}_1, \dots,\pmb{a}_m]^\tp \in \mathbb{F}^{m\times n}$ is the sampling matrix, $|\pmb{A}\pmb{x}| = [\vert\langle \pmb{a}_{1},\pmb{x} \rangle\vert, \dots, \vert\langle \pmb{a}_{m},\pmb{x}_0 \rangle\vert]$.
Here, $\pmb{\omega}$ denotes the $\ell_{1}$-bounded noise, $\pmb{z}$ represents the adversarial sparse outliers whose
nonzero entries can be arbitrarily large and may even depend on the measurement system $(\pmb{b}, \pmb{A})$ and ground-truth $\x_0$, and $s$ is referred to as the adversarial corruption fraction.
We call it adversarial phase retrieval problem based on amplitude measurements.

We study the reconstruction property of the nonlinear least absolute deviation (nonlinear LAD) for amplitude measurement

\begin{eqnarray} \label{model1}
&&\min   \lV\lv\A \x\rv-\pmb{b}\rV_{1}\\
&&\text{s.t. } \pmb{x}\in \mathcal{K}.		 \nonumber
\end{eqnarray}

Here, $\mathcal{K}$ is a general set to capture the structure of the signal and we assume throughout that $\x_{0}$ lies in it.
A general structural representation is to let $\mathcal{R}:\mathbb{R}^{n}\to\mathbb{R}$ be a regularization function that reflects some priori knowledge of $\x_{0}$. Then $\mathcal{K}$ can be set as $\mathcal{K}=\{\x\in\mathbb{R}^{n}:\mathcal{R}(\x)\le R\}$ where $R$ is a tuning parameter.

For example, we can choose $\mathcal{R}(\x)=\lV\x\rV_{1}$ if $\x$ is sparse.
For Gaussian measurements, we show that the nonlinear robust outlier bound condition (nonlinear ROB condition, see Section <ref>)
holds for any submatrices consisting of a $(1- s)$-fraction of the measurements with high probability under appropriate samples, where $s < s^{*,1} \approx 0.2043$.
Utilizing the nonlinear ROB condition, we can show the amplitude-based nonlinear LAD (<ref>) is additionally robust against a fraction $s^{*,1} \approx 0.2043$ of arbitrary errors.
To the best of our knowledge, it is the first sharp sparsity threshold of adversarial outliers in phase retrieval based on the amplitude-based model.

And [38, 43, 34] showed that the amplitude-based algorithms perform better in sample complexity and computational complexity experimentally and theoretically.
[42] demonstrated that amplitude-based algorithms can tolerate a larger fraction of outliers than intensity-based algorithms by experiments but lack of theoretical guarantees.
Therefore, we are encouraged to explore and compare the robust performance of models based on the two kinds of measurements.

In the intensity-based nonlinear LAD model, we consider that

\begin{eqnarray} \label{model3}
&&\min \lV\lv\mA \x\rv^{2}-\pmb{b}\rV_{1}\\
&&\text{s.t. }   \pmb{x}\in \mathcal{K},\nonumber
\end{eqnarray}

with intensity measurements
$\pmb{b}=\lv\pmb{A}\x_{0}\rv^2+\pmb{\omega}+\pmb{z}$ where $|\pmb{A}\pmb{x}|^2 = [\vert\langle \pmb{a}_{1},\pmb{x} \rangle\vert^2, \dots, \vert\langle \pmb{a}_{m},\pmb{x}_0 \rangle\vert^2]$.
We use the similar analytical approach to give the sharp sparsity threshold $s^{*,2}\approx 0.1185$ of adversarial outliers,
which is consistent with the bound of [18].
Compared to [18], we consider the nonlinear model instead of the one using PhaseLift and remove the Rademacher distribution assumption of the outliers to give more general analysis.

Our results not only give the two sharp sparsity thresholds of adversarial outliers in the models based on amplitude and intensity measurements, but also theoretically analyze the robust performance of the two models and explain the superiority of the amplitude-based nonlinear LAD model (<ref>) compared to the intensity-based nonlinear one (<ref>), since $s^{*,1}$ is larger than $s^{*,2}$.

We also construct adaptive counterexamples that are related to measurement $\mA$ and observation $\pmb{b}$ to show that the recovery fails when adversarial corruption fraction exceeds $s^{*,1}$ and $s^{*,2}$ in the two cases.  We conduct extensive numerical experiments to corroborate our results.

§.§ Our Contributions

We summarize the main contributions of this work.
We first give a general framework in phase retrieval for the analyses of nonlinear LAD model based on a general set $\mathcal{K}$ under the corruption of adversarial sparse outliers. It is an underlying paradigm for dealing with different measurements to elaborate the corresponding ROB conditions.
We present the probability density function (PDF) of the combination $\bigl|\lv X \rv-\lv Y\rv\bigr|$ and $\lv X\cdot Y \rv$ of two Gaussian variables (may be not normal or independent) $X$, $Y$. The PDF of $\bigl|\lv X \rv-\lv Y\rv\bigr|$ may be first presented in this paper.
Based on this, we give the nonlinear ROB condition to cope with the adversarial outliers.
We then give the sharp sparsity threshold $s^{*,1} \approx 0.2043$ of adversarial outliers in the nonlinear LAD model for amplitude measurement.

For intensity-based nonlinear LAD model, we give the sharp sparsity threshold $s^{*,2} \approx 0.1185$ without the Rademacher distribution assumption for outliers.
Our analyses of these two models leads to the first theoretical examination of the distinction in robustness performance between amplitude and intensity measurement such that the amplitude-based nonlinear LAD model has superior adversarial robustness in comparison to the intensity-based one.

§.§ Comparisons to Related Work

A majority of existing work has considered stable performance in phase retrieval [4, 14, 7, 43, 19].
These work aimed to recover the signal from observations with bounded noise or random noise.

Only a handful of papers analyzed the phase retrieval problem in the presence of outliers, especially adversarial outliers [17, 25, 12].

[17] proved that the PhaseLift with LAD can tolerate a small, fixed fraction of gross outliers and
[25] restricted the signs of sparse noise to be generated from Rademacher distribution and
extended the performance guarantee to the general low-rank PSD matrix case.
[12] developed the prox-linear algorithm to solve phase retrieval problems even with adversarially faulty measurements.
Most of them did not consider the adaptive outliers but set the outliers to obey some specified distribution such as Gaussian or uniform distribution in numerical simulation. [18] provided corresponding threshold $s^{*}\approx0.1185$ for robust PhaseLift model, considering intensity measurement.
They also assumed  that the signs of adversarial sparse outliers follow the Rademacher distribution as [25].

Our paper considers adversarial sparse outliers without any additional assumptions and we give the sharp theoretical thresholds of the adversarial corruption fraction $s$ for both amplitude and intensity measurement.

Adversarial analysis could be at the intersection of two lines of research, signal recovery and privacy-preservation.
In decoding, [13] first provided that adversary accounts for at most 0.239 in the measurement by statistical methods, and the result has been successively extended to compressed sensing <cit.> and low-rank matrix recovery [40]. These work could be utilized in privacy-preservation, which is a very important and popular theme in the era of big data. For example, [44] showed that a similar setting can be used for sparse regression and analyzed its privacy properties. Besides, researchers have applied deep learning to solve the phase retrieval problem such as [20, 27].
They used convolutional neural network to denoise and create new algorithms. Their algorithms are exceptionally robust to noise in simulation but lack of theoretical analysis.
We hope that our work serves as an important step towards privacy-preserving phase retrieval and decoding by nonlinear encryption, and also give some theoretical support for these novel algorithms in the future.

§.§ Notations and Preliminaries

Throughout this paper, we use the following notations. We first define two different metrics.
For amplitude-based model
we use metric

\begin{equation}\label{dist1}
\mathrm{dist}_{1}\left(\x,\y\right)=\min\left\{\lV\x-\y \rV_2,\lV\x+\y \rV_2\right\}
\end{equation}

and for intensity-based model the distance between $\x$ and $\y$ can be defined as

\begin{equation}\label{dist2}
\mathrm{dist}_{2}\left(\x,\y\right)=\lV\x-\y \rV_2\cdot\lV\x+\y \rV_2.
\end{equation}

Evidently, we have  $\left(\mathrm{dist}_{1}\left(\x,\y\right)\right)^{2}\le\mathrm{dist}_{2}\left(\x,\y\right)$.
For two non-negative real sequences $\{a_t\}_t$ and $\{b_t\}_t$, we write $b_t = O\left(a_t\right)$ (or $b_t \lesssim a_t$) if $b_t \leq Ca_t$.
For $\alpha \geq 1$, the $\psi_\alpha$-norm (which is the Orlicz norm taken with respect to function $\exp\left(x^\alpha\right) -1$) of a random variable $X$ is defined as

\begin{eqnarray*}
\lV X\rV_{\psi_\alpha} := \inf\{ t >0: \mathbb{E} \exp(\lv X\rv^\alpha/t^\alpha) \leq 2\}.
\end{eqnarray*}

In particular, $\alpha=2$ gives the sub-Gaussian norm and $\alpha=1$ gives the sub-exponential norm. The random variable $X$ is called sub-Gaussian if $\lV X\rV_{\psi_2}<\infty$ and sub-exponential if $\lV X\rV_{\psi_1}<\infty$.  The Gaussian error function is denoted as $\text{erf}\left(x\right)=\frac{2}{\sqrt{\pi}}\int_{0}^{x}\exp\left(-t^{2}\right)dt.$

To describe the structure of possible signals, we mainly introduce tools for characterizing the complexity of set $\mathcal{K}$. If we assume that $\x$ lies in some set $\mathcal{K} \subset B_2^n$ where $B_2^n$ denotes the Euclidean unit ball in $\mathbb{R}^n$, then a key characteristic of structure  of the signal set
is its Gaussian width $w\left(\mathcal{K}\right)$, defined as

\begin{equation}\label{Gaussian width}
w\left(\mathcal{K}\right) := \mathbb{E} \sup_{\x \in \mathcal{K}} \langle  \pmb{g} , \x \rangle,
\end{equation}

where $\pmb{g}\sim\mathcal{N}\left(0,\pmb{I}_{n}\right)$.  In particular, denote $\text{cone}\left(\mathcal{K}\right):=\{tx:t\geq0, x\in \mathcal{K}\}$, then $w^2\left(\text{cone}\left(\mathcal{K}\right)\cap \mathbb{S}^{n-1}\right)$ is a meaningful approximation for dimension [36], it can also be said that $w^2\left(\mathcal{K}\right)$ can serve as the effective dimension of set $\mathcal{K}$.
We point out some common examples of Gaussian width in the literature.
If $\mathcal{K} = B_2^n$ or $\mathcal{K} = \mathbb{S}^{n-1}$ then $w\left(\mathcal{K}\right) =\mathcal{O}\left(\sqrt{n}\right)$.

If $\mathcal{K}=\mathcal{K}_{n,s}:=\{\x\in\mathbb{R}^{n}:\lV\x\rV_{2}=1,\lV\x\rV_{1}=\sqrt{s}\}$, then $w\left(\mathcal{K}\right)=\mathcal{O}\left(\sqrt{s\log\left(en/s\right)}\right)$. The relationship between Gaussian width and covering number can be obtained by Sudakov's minoration inequality in $\mathbb{R}^{n}$  [35]. Let $\mathcal{N}\left(\mathcal{K},\delta\right)$ be the $\delta$-covering number of set $\mathcal{K}$ then for any $\delta\textgreater0$, we have

\begin{eqnarray}\label{Sudakov}
w\left(\mathcal{K}\right)\ge c\delta\sqrt{\log \mathcal{N}\left(\mathcal{K},\delta\right)}.
\end{eqnarray}

It can be seen that Gaussian width can provide an upper bound for covering number.

§.§ Organization

The rest of this paper is organized as follows.

The main results are presented in Section <ref>. In this section, we provide recovery guarantees based on the amplitude-based nonlinear LAD model (<ref>) and intensity-based nonlinear LAD model (<ref>).
In Section <ref>, we give a framework for adversarial robust recovery in phase retrieval.
In Section <ref>, we introduce the notion of nonlinear ROB condition and show that it holds with high probability
for Gaussian measurements.

We provide the proofs for our main results in Section <ref>.

Proof of
Dvoretzky-Kiefer-Wolfowitz type inequality is presented in Appendix  <ref> and related probability density function is presented in Appendix <ref>. Partial proofs of nonlinear ROB condition are presented in Appendix <ref>.

§ MAIN RESULTS

We mainly focus on the amplitude-based nonlinear LAD model (<ref>) and  intensity-based nonlinear LAD model (<ref>), and provide corresponding sharp thresholds for the adversarial corruption fraction.
Our theoretical conclusion aligns with the empirical evidence, indicating that the amplitude-based nonlinear LAD model has superior adversarial robustness in comparison to the intensity-based one. To this end, we assume a tractable model in which the design vectors $\{ \pmb{a}_i \}_i$ are i.i.d standard Gaussian vectors.

§.§ Adversarial Robust Recovery for Amplitude Measurement

In this subsection, we provide theoretical results for the nonlinear amplitude-based LAD model (<ref>). Our results show that
the solution of (<ref>) is robust to any fraction of adversarial corruption $s\textless s^{*,1}\approx 0.2043$.

Suppose that $s\textless s^{*,1}-2\xi$ and $s=\lV\pmb{z}\rV_{0}/m$, where $s^{*,1}\approx 0.2043$. If the
number of measurements satisfies

\begin{eqnarray}\label{measurement}
m \gtrsim \xi^{-4}\cdot w^2\left(\text{cone}\left(\mathcal{K}\right)\cap \mathbb{S}^{n-1}\right),
\end{eqnarray}

then for all $\pmb{x}_0\in \mathbb{R}^{n}$ with probability at least $1-\mathcal{O}\left(e^{-cm\xi^{2}}\right)$, the solution $\x_{\star}$ of (<ref>) satisfies

\begin{eqnarray}\label{noise}
\mathrm{dist}_{1}\left(\x_{\star},\x_{0}\right)\leq C\frac{\lV\pmb{\omega}\rV_1}{m},
\end{eqnarray}

where $C,c$ are positive numerical constants related to adversarial corruption fraction $s$.

By (<ref>) we have $	\mathrm{dist}_{1}\left(\x_{\star},\x_{0}\right)\lesssim\frac{\lV\pmb{\omega}\rV_{1}}{m}\le\frac{\lV\pmb{\omega}\rV_{2}}{\sqrt{m}}$.
Thus, the estimation error in our nonlinear LAD model has a better error bound than LS model.

In the case of $\pmb{\omega}=0$, the ground-truth $\x_{0}$ can be exactly reconstructed via (<ref>)
even adversarial corruption fraction approaches $s^{*,1}\approx 0.2043$.
If we choose $\mathcal{K}=\mathbb{R}^{n}$ then we have $m=\mathcal{O}\left(n\right)$ and if $\mathcal{K}=\mathcal{K}_{n,s}$ then $m=\mathcal{O}\left(s\log\left(en/s\right)\right)$. Thus the number of measurement (<ref>) is nearly optimal in many cases.

In the following theorem, we also illustrate that in the case of dense noise $\pmb{\omega}=0$, (<ref>) exhibits a significant inability to accurately reconstruct the ground-truth $\x_{0}$ when adversarial sparse fraction $s>s^{*,1}$.
It indicates that the threshold $s^{*,1}\approx 0.2043$ is sharp.

Set $s\textgreater s^{*,1}+2\xi$ where $s^{*,1}\approx 0.2043$. If $\pmb{\omega}=\pmb{0}$ and $\mathcal{K}=\mathbb{R}^{n}$, then for any $\x_0\in \mathbb{R}^{n}$, there exists  an adversarial sparse outlier $\pmb{z}$ with $\Vert \pmb{z}\Vert_{0}=sm$, such that the solution of (<ref>) is not exactly the ground-truth $\x_0$ with probability exceeding $1-\mathcal{O}\left(e^{-cm\xi^{2}}\right)$.

§.§ Adversarial Robust Recovery for Intensity Measurement

We provide theoretical results for the nonlinear intensity-based LAD model (<ref>) where the solution of (<ref>) is robust to any fraction of corruptions $s\textless s^{*,2}\approx 0.1185$ and in the case $\pmb{\omega}=0$, (<ref>) fails to exactly recover the vector $\x_{0}$ when $s$ exceeding $s^{*,2}$.

Suppose that $s\textless s^{*,2}-2\xi$ and $s=\lV\pmb{z}\rV_{0}/m$, where $s^{*,2}\approx 0.1185$. If the
number of measurements satisfies

\begin{eqnarray*}
m \gtrsim \xi ^{-4}\cdot w^2\left(\text{cone}\left(\mathcal{K}\right)\cap \mathbb{S}^{n-1}\right),
\end{eqnarray*}

then for all $\pmb{x}_0\in \mathbb{R}^{n}$ with probability at least $1-\mathcal{O}\left(e^{-cm\xi^{2}}\right)$, the solution $\x_{\star}$ of (<ref>) satisfies

\begin{eqnarray}\label{d2}
\mathrm{dist}_{2}\left(\x_{\star},\x_{0}\right)\leq C\frac{\lV\pmb{\omega}\rV_1}{m},
\end{eqnarray}

where $C$ and $c$ are positive numerical constants related to $s$.

By (<ref>), we have $\mathrm{dist}_{1}\left(\x_{\star},\x_{0}\right)\lesssim\frac{\sqrt{\lV\pmb{\omega}\rV_1}}{m^{1/2}}$. Besides, we can confirm that
$  \mathrm{dist}_{1}\left(\x_{\star},\x_{0}\right)\cdot\lV\x_{0}\rV_{2}\le\mathrm{dist}_{2}\left(\x_{\star},\x_{0}\right)$. Thus, we can get

\begin{eqnarray}\label{bound2}
\mathrm{dist}_{1}\left(\x_{\star},\x_{0}\right)\lesssim\min\left\{\frac{\sqrt{\lV\pmb{\omega}\rV_1}}{m^{1/2}},\frac{\lV\pmb{\omega}\rV_1}{\lV\x_{0}\rV_{2}\cdot m}\right\}.
\end{eqnarray}

Evidently, error bound (<ref>) is tighter than LS model in [19].

considered the Robust-PhaseLift model and also obtained the threshold $s^{*,2}\approx 0.1185$ when the signs of adversarial sparse outlier $\z$ are drawn from the Rademacher distribution and the support of $\z$ is fixed. Our theoretical results of model (<ref>) are not dependent on these assumptions.

Set $s\textgreater s^{*,2}+2\xi$ where $s^{*,2}\approx 0.1185$. If $\pmb{\omega}=\pmb{0}$ and $\mathcal{K}=\mathbb{R}^{n}$, for any $\x_0\in \mathbb{R}^{n}$, there exists  an adversarial
sparse outlier $\pmb{z}$ with $\Vert \pmb{z}\Vert_{0}=sm$, such that the solution of (<ref>) is not exactly the ground-truth $\x_0$ with probability exceeding $1-\mathcal{O}\left(e^{-cm\xi^{2}}\right)$.

§ A FRAMEWORK FOR ADVERSARIAL PHASE RETRIEVAL

§.§  Nonlinear Robust Outlier Bound Condition

For simplification, the corrupted measurements are written as

\begin{equation*}
\pmb{b}=\lv\A\x_{0}\rv^{k}+\pmb{\omega}+\pmb{z},\quad \|\pmb{z}\|_{0}\leq sm,\quad k=1,2.
\end{equation*}

In this section
we have considered a unified form for amplitude measurement and intensity measurement without distinction.
Due to the adversarial sparse outliers $\pmb{z}$'s dependence on the measurement system $(\pmb{b}, \pmb{A})$ and ground-truth $\x_0$,
as well as the the nonlinearity of operators $\lv\mA\x\rv$ and $\lv\mA\x\rv^{2}$,

we give the definition of nonlinear ROB condition.

For amplitude measurement ($k=1$) or intensity measurement ($k=2$), and adversarial corruption friction $s$, sampling matrix $\mA\in \mathbb{R}^{m\times n}$ is said to satisfy the nonlinear robust outlier bound condition,
if there exists a constant $\mathcal{C}\left(s\right)> 0$ depending on $s\in \left[0,1\right]$,
such that the following holds for all vectors $\pmb{x},\pmb{y}\in \mathcal{K}$,

\begin{eqnarray*}
\frac{1}{m}\min_{\left\{\mS \subset\left[m\right],  |\mS|\leq s m\right\} }
\left[\lV \lv\mA_{{\mS}^{c}} \x\rv^{k} -\lv\mA_{{\mS}^{c}} \y\rv^{k} \rV_1-\lV \lv\mA_{\mS} \x\rv^{k} -\lv\mA_{\mS} \y\rv^{k} \rV_1 \right]
\ge \mathcal{C}\left(s\right)\cdot\mathrm{dist}_{k}\left(\x,\y\right).
\end{eqnarray*}

Nonlinear ROB condition characterizes the worst-case scenario where $\lv\mA\x\rv^{k}-\lv\mA\y\rv^{k}$ are corrupted in the sense of the $\ell_{1}$-norm under the given adversarial corruption fraction $s$.

§.§ Adversarial Sparse Outlier Separation Condition

If the sampling matrix $\mA$ satisfies the nonlinear ROB condition, we then can give an upper bound to the distance between the model solution $\x_{\star}$ and the ground-truth
$\x_{0}$ by the subsequent adversarial sparse outlier separation condition.

For adversarial corruption fraction $s$, assume the sampling matrix $\mA$ satisfies the nonlinear ROB condition with coefficient $\mathcal{C}\left(s\right) >0$,

then the solution $\x_{\star}$ of nonlinear LAD models (<ref>) or (<ref>) satisfies

\begin{equation}
\mathrm{dist}_{k}\left(\x_{\star},\x_{0}\right)\le \widetilde{\mathcal{C}}\left(s \right)\frac{\lV\pmb{\omega}\rV_1}{m},
\end{equation}

where $\widetilde{\mathcal{C}}\left(s\right)=2/\mathcal{C}\left(s\right)$.

By definition of $\x_{\star}$ and $ \pmb{b}=\lv\mA\x_{0}\rv^{k}+\pmb{\omega}+\pmb{z}$, we have

\begin{eqnarray*}
\lV \lv\mA \x_{\star}\rv^{k} -\lv\mA \x_{0}\rv^{k} - \pmb{z} -\pmb{\omega } \rV_1 \leq \lV \pmb{z}+\pmb{\omega }  \rV_1.
\end{eqnarray*}

Since $\ell_{1}$-norm can be divided into  parts $\mathcal{S}$ and $\mathcal{S}^{c}$, we can get

\begin{eqnarray*}
\lV \lv\mA_{\mS} \x_{\star}\rv^{k} -\lv\mA_{\mS} \x_{0}\rv^{k} - \pmb{z} -\pmb{\omega}_{\mS} \rV_1
\lV \lv\mA_{{\mS}^{c}} \x_{\star}\rv^{k} -\lv\mA_{{\mS}^{c}} \x_{0}\rv^{k} -\pmb{\omega}_{{\mS}^{c}} \rV_1\
\leq \lV \pmb{z}+\pmb{\omega}_{\mS}  \rV_1+\lV\pmb{\omega}_{{\mS}^{c}}  \rV_1.
\end{eqnarray*}

The triangle inequality yields that

\begin{eqnarray*}
\lV \lv\mA_{\mS} \x_{\star}\rv^{k} -\lv\mA_{\mS} \x_{0}\rv^{k} - \pmb{z} -\pmb{\omega}_{\mS} \rV_1
&\geq& \lV \pmb{z}+\pmb{\omega}_{\mS} \rV_1-\lV \lv\mA_{\mS} \x_{\star}\rv^{k} -\lv\mA_{\mS} \x_{0}\rv^{k} \rV_1,\\
\lV \lv\mA_{{\mS}^{c}} \x_{\star}\rv^{k} -\lv\mA_{{\mS}^{c}} \x_{0}\rv^{k} -\pmb{\omega}_{{\mS}^{c}} \rV_1
&\geq& 	\lV \lv\mA_{{\mS}^{c}} \x_{\star}\rv^{k} -\lv\mA_{{\mS}^{c}} \x_{0}\rv ^{k}\rV_1 - \lV\pmb{\omega}_{{\mS}^{c}}\rV_1.
\end{eqnarray*}

Thus, we can further bound

\begin{equation*}
\lV \lv\mA_{{\mS}^{c}} \x_{\star}\rv^{k} -\lv\mA_{{\mS}^{c}} \x_{0}\rv^{k} \rV_1-\lV \lv\mA_{\mS} \x_{\star}\rv^{k} -\lv\mA_{\mS} \x_{0}\rv^{k} \rV_1
\leq  2\lV\pmb{\omega}_{{\mS}^{c}} \rV_1\leq 2\lV\pmb{\omega}\rV_1.
\end{equation*}

Since the set $\mS$ should encompass all the subsets of $\left[m\right]$ that satisfy $|\mS|\leq s m$, based on the nonlinear ROB condition, we have

\begin{eqnarray*}
\mathrm{dist}_{k}\left(\x_{\star},\x_{0}\right)\leq \frac{2}{\mathcal{C}\left(s\right)}\frac{\lV\pmb{\omega}\rV_1}{m}=\widetilde{\mathcal{C}}\left(s\right)\frac{\lV\pmb{\omega}\rV_1}{m}.
\end{eqnarray*}

§ ANALYSIS OF NONLINEAR ROB CONDITION

In this section, we will respectively prove that the sampling matrix $\mA$ satisfies nonlinear ROB condition for the two cases. We further give the sharp sparsity thresholds $s^*$ of adversarial outliers.

§.§ Nonlinear ROB Condition for Amplitude Measurement

When $\pmb{a}\sim\mathcal{N}\left(0,\pmb{I}_{n}\right)$, we can see that $X:=\langle\pmb{a},\x\rangle\sim \mathcal{N}\left(0,\lV\x\rV^{2}_{2}\right), Y:=\langle\pmb{a},\y\rangle\sim \mathcal{N}\left(0,\lV\y\rV^{2}_{2}\right)$ for fixed $\x, \y \in \mathbb{R}^{n}$.
Without losing generality, we assume
$\lV\x\rV_{2}=1$ and $ \lV\y\rV_{2}=\alpha\in\left[0,1\right]$, and denote the correlation coefficient between $X$ and $Y$ as $\rho$.

Then we have

\begin{eqnarray*}
\lV\lv\mA\x\rv-\lv\mA\y\rv\rV_{1}=\sum_{i=1}^{m}\big|\lv\langle\pmb{a}_{i},\x\rangle\rv-\lv\langle\pmb{a}_{i},\y\rangle\rv\big|=
\sum_{i=1}^{m}\big| \lv X_{i} \rv - \lv Y_{i} \rv \big|.
\end{eqnarray*}

We provide the following lemma to give the PDF of $\lv Z_{\rho,\alpha}\rv:=\big| \lv X \rv - \lv Y \rv \big|$, which serves as the primary statistical tool for our analysis. Since the subsequent analysis solely focuses on the PDF within the context of integration, we only consider the case $z\textgreater 0$.

We set two variables $X\sim \mathcal{N}\left(0,1\right),Y\sim \mathcal{N}\left(0,\alpha^{2}\right)$, $ 0\le \alpha \le 1$ and their correlation coefficient $\rho\in \left[-1,1 \right]$.

Then for $z\textgreater 0$, the PDF of $\lv Z_{\rho,\alpha}\rv  = \bigl| \lv X\rv-\lv Y\rv \bigr|$ is:

If $\lv\rho\rv\textless1,\alpha\neq0$, set $\varLambda_{\pm}=\alpha^{2}\pm2\rho\alpha+1$, then

[2-erf(1+ρα/α√(2_+(1-ρ^2)) z	)
-erf(-1+ρα/α√(2_+(1-ρ^2)) z+√(_+/2(1-ρ^2))z/α)]

-erf(-1-ρα/α√(2_-(1-ρ^2))z+√(_-/2(1-ρ^2))z/α)	].

If $\rho=\pm1$, then $ g_{\rho,\alpha}\left(z\right)=
\frac{1}{1-\alpha}\sqrt{\frac{2}{\pi}}\exp\big[{-\frac{z^{2}}{2\left(1-\alpha\right)^{2}}}\big]$.

If $\alpha=0$, then $g_{\rho,\alpha}\left(z\right)=\sqrt{\frac{2}{\pi}}\exp\big({-z^{2}/2}\big).$

We first consider when $\lv\rho\rv\textless1$ and $\alpha\neq0$.

By (3.1) in [32], the PDF of the bivariate folded normal distribution $(\lv X \rv , \lv Y\rv)$ is given by:

\begin{eqnarray*}
f_{\lv X\rv,\lv Y\rv}\left(x,y\right)
=\frac{\exp \left[-\frac{1}{2\left(1-\rho^{2}\right)}  \left(x^{2}-\frac{2\rho xy}{\alpha}+\frac{y^{2}}{\alpha^{2}} \right)\right]+\exp \left[-\frac{1}{2\left(1-\rho^{2}\right)}  \left(x^{2}+\frac{2\rho xy}{\alpha}+\frac{y^{2}}{\alpha^{2}} \right)\right]}{\pi\alpha\sqrt{1-\rho^{2}}}
\quad x,y\ge0.
\end{eqnarray*}

By integral transformation, the PDF of $Z_{\rho,\alpha}=\lv X\rv-\lv Y\rv$ obeys

\begin{eqnarray}\label{pdf(x-y)}
f_{\rho,\alpha}\left(z\right)=\mathbbm{1}_{z\in\left(-\infty,0\right)}\cdot\int_{0}^{+\infty}f_{\lv X\rv,\lv Y\rv}\left(x,x-z\right)dx+ \mathbbm{1}_{z\in\left[0,+\infty\right)}\cdot\int_{z}^{+\infty}f_{\lv X\rv,\lv Y\rv}\left(x,x-z\right)dx.
%= \int_{0}^{+\infty}f_{|X|,|Y|}(x,x-z)dx - \int_{0}^{z}f_{|X|,|Y|}(x,x-z)dx.
\end{eqnarray}

It can be derived from [16] that

\begin{eqnarray}\label{exp1}
\int_{0}^{+\infty}\exp\left(-\frac{x^{2}}{4\beta}-\gamma x\right)dx=\sqrt{\pi\beta}\exp(\beta \gamma^{2}) \left[1-\text{erf}(\gamma\sqrt{\beta})\right] \quad \beta\textgreater 0,
\end{eqnarray}

and similar calculation yields that

\begin{eqnarray}\label{exp2}
\int_{z}^{+\infty}\exp\left(-\frac{x^{2}}{4\beta}-\gamma x\right)dx=\sqrt{\pi\beta}\exp\left(\beta \gamma^{2}\right) \left[1-\text{erf}\left(\gamma\sqrt{\beta}+\frac{z}{2\sqrt{\beta}}\right)\right] \quad \beta\textgreater 0.
\end{eqnarray}

We will use (<ref>) and (<ref>) to calculate the PDF of $Z_{\rho,\alpha}$.
If $z\textless0$, thus
For convenience, we define

\begin{eqnarray*}
-\frac{1}{2\left(1-\rho^{2}\right)}\left[x^{2}\pm\frac{2\rho x\left(x-z\right)}{\alpha}+\frac{\left(x-z\right)^{2}}{\alpha^{2}}\right]
\end{eqnarray*}

Then we can get

\begin{eqnarray*}
\beta _{1(2)} = \frac{(1-\rho^{2})\alpha^{2}}{2\varLambda_{\pm}} > 0,\quad \gamma_{1(2)}=-\frac{1}{1-\rho^{2}}(\frac{z}{\alpha^{2}}\pm\frac{\rho z}{\alpha})\quad \text{and}\quad \delta=\frac{z^{2}}{2(1-\rho^{2})\alpha^{2}}.
\end{eqnarray*}

Moreover, it can be obtained through simple calculation that

\begin{eqnarray*}
\beta_{1}\gamma^{2}_{1}
%=\frac{(1-\rho^{2})\sigma^{2}}{2(\sigma^{2}+2\rho\sigma+1)}\left[\frac{1}{1-\rho^{2}}(\frac{z}{\sigma^{2}}+\frac{\rho z}{\sigma})\right]^{2}
=\frac{\left(1+\rho\alpha\right)^{2}z^{2}}{2\left(1-\rho^{2}\right)\varLambda_{+}\alpha^{2}}\quad \text{and} \quad
%	\end{eqnarray*}
%	and
%	\begin{eqnarray*}
\beta_{2}\gamma^{2}_{2}=\frac{\left(1-\rho\alpha\right)^{2}z^{2}}{2\left(1-\rho^{2}\right)\varLambda_{-}\alpha^{2}}.
\end{eqnarray*}

We now can evaluate the integral:

\begin{eqnarray*}
%&=& \frac{1}{\pi\sigma\sqrt{1-\rho^{2}}}\int_{0}^{+\infty}\exp(\alpha_{1})+\exp(\alpha_{2})dx\\
&=& \frac{\exp\left(-\delta \right)}{\pi\alpha\sqrt{1-\rho^{2}}}\int_{0}^{+\infty}\exp\left(-\frac{x^{2}}{4\beta_{1}}-\gamma_{1}x\right)+\exp\left(-\frac{x^{2}}{4\beta_{2}}-\gamma_{2}x\right)dx\\
&=& \frac{\sqrt{\beta_{1}}\exp\left(\beta_{1} \gamma_{1}^{2}-\delta\right)}{\alpha\sqrt{\pi\left(1-\rho^{2}\right)}} \left[1-\text{erf}\left(\gamma_{1}\sqrt{\beta_{1}}\right)\right]+ \frac{\sqrt{\beta_{2}}\exp\left(\beta_{2} \gamma_{2}
^{2}-\delta\right)}{\alpha\sqrt{\pi\left(1-\rho^{2}\right)}} \left[1-\text{erf}\left(\gamma_{2}\sqrt{\beta_{2}}\right)\right]\\
&=&\frac{\exp\left(-\frac{z^{2}}{2\varLambda_{+}}\right)}{\sqrt{2\pi \varLambda_{+}}}
\left[1-\text{erf}\left(-{\frac{1+\rho\alpha}{\alpha\sqrt{2\left(1-\rho^{2}\right)\varLambda_{+}} }z
}\right)\right] \\
\left[1-\text{erf}\left(-{\frac{1-\rho\alpha}{\alpha\sqrt{2\left(1-\rho^{2}\right)\varLambda_{-}} }z}\right)\right].
\end{eqnarray*}

If $z\ge0$, then $f_{\rho,\alpha}\left(z\right)=\int_{z}^{+\infty}f_{\lv X\rv,\lv Y\rv}\left(x,x-z\right)dx$. Similarly, we have

\begin{eqnarray*}
\left[1-\text{erf}\left(-{\frac{1+\rho\alpha}{\alpha\sqrt{2\left(1-\rho^{2}\right)\varLambda_{+} } }z}+\sqrt{\frac{\varLambda_{+}}{2\left(1-\rho^{2}\right)}}\frac{z}{\alpha}\right)\right]\\
\left[1-\text{erf}\left(-{\frac{1-\rho\alpha}{\alpha\sqrt{2\left(1-\rho^{2}\right)\varLambda_{-}} }z}+\sqrt{\frac{\varLambda_{-}}{2\left(1-\rho^{2}\right)}}\frac{z}{\alpha}\right)\right].
\end{eqnarray*}

Due to $g_{\rho,\alpha}\left(z\right) = f_{\rho,\alpha}\left(z\right) +f_{\rho,\alpha}\left(-z\right)$, we have obtained the expression.

When $\rho=\pm1$, then $ Z_{\rho,\alpha}=\lv X\rv-\lv Y\rv=\left(1-\alpha\right)\lv X\rv$. Thus
\frac{1}{1-\alpha}\sqrt{\frac{1}{2\pi}}\exp\left[-\frac{z^{2}}{\left(1-\alpha\right)^{2}}\right].$
Then $g_{\rho,\alpha}\left(z\right)=\frac{1}{1-\alpha}\sqrt{\frac{2}{\pi}}\exp\left[-\frac{z^{2}}{\left(1-\alpha\right)^{2}}\right]$.

When $\alpha=0$, then $Z_{\rho,\alpha}=\lv X\rv-\lv Y\rv=\lv X\rv$. Thus
and then $g_{\rho,\alpha}\left(z\right)=\sqrt{\frac{2}{\pi}}\exp\left(-z^{2}/2\right)$.

Furthermore, we set the Cumulative Distribution Function (CDF) of $\lv Z_{\rho,\alpha}\rv$ as

\begin{eqnarray*}
G_{\rho,\alpha}\left(t\right) = \int_{0}^{t} g_{\rho,\alpha}\left(z\right) dz.
\end{eqnarray*}

Due to symmetry, we can only consider $\rho\ge 0$. Thus, $\mathrm{dist}_{1}\left(\x,\y\right)=\sqrt{1+\alpha^{2}-2\alpha\rho}.$ To characterize the deviation between $\ell_1$-norm of largest $s$-fraction and smallest $(1-s)$-fraction of the random variable $\lv Z_{\rho,\alpha}\rv$,
we define the balance function

\begin{equation*}%\label{balance}
M\left(\rho,\alpha, s\right) = M_{1}\left(\rho,\alpha, s\right)-M_{2}\left(\rho,\alpha, s\right)\\
:=\frac{\left[ \int_0^{G_{\rho,\alpha}^{-1}\left(1-s\right)} - \int_{G_{\rho,\alpha}^{-1}\left(1-s\right)}^{+\infty} \right] z g_{\rho,\alpha}\left(z\right)dz}{\sqrt{1+\alpha^{2}-2\alpha\rho}}.
\end{equation*}

For fixed $\x,\y$ with corresponding parameters $\rho,\alpha$ and largest $\ell_{1}$-norm corruption set $\mathcal{S}$ with size $\lv\mathcal{S}\rv=sm$, in the limit of large samples (i.e. $m\to\infty$), we see that a form of strong law of large numbers yields that

\begin{eqnarray}
M\left(\rho,\alpha, s\right)=\frac{\mathbb{E}\left[\lV \lv\mA_{{\mS}^{c}} \x\rv -\lv\mA_{{\mS}^{c}} \y\rv \rV_1-\lV \lv\mA_{\mS} \x\rv -\lv\mA_{\mS} \y\rv \rV_1 \right]}{m\cdot\mathrm{dist}_{1}\left(\x,\y\right)}.
\end{eqnarray}

Nonlinear ROB condition is uniformly established for any $\x,\y\in\mathcal{K}\subset\mathbb{R}^{n}$,

we should  take into account the minimum value of function $M\left(\rho,\alpha, s\right)$ regarding parameters $\rho,\alpha\in\left[0,1\right]$.
It motivates us to analyze the minimum balance function $\mathcal{M}\left(s\right)$.

\begin{eqnarray}
\mathcal{M}\left(s\right)=\min_{\rho,\alpha \in[0,1]}\frac{\left[\int_{0 }^{G_{\rho,\alpha}^{-1}\left(1-s\right)}- \int_{G_{\rho,\alpha}^{-1}\left(1-s\right) }^{+\infty} \right]z g_{\rho,\alpha }\left(z\right)dz}{\sqrt{1+\alpha^{2}-2\alpha\rho}}.
\end{eqnarray}

We can use $\mathcal{M}\left(s\right)$
to establish the uniform lower bound of the nonlinear ROB condition.
If we set $(\rho,\alpha) = \argmin \mathcal{M}(s_{\rho,\alpha})$, then it goes that

∫_0 ^G_ρ,α^-1(1-s_ρ,α)z g_ρ,α(z)dz = ∫_G_ρ,α^-1(1-s_ρ,α) ^+∞ z g_ρ,α(z)dz.
We can get $s^{*,1} = \min\limits_{\rho,\alpha\in [0,1]} s_{\rho,\alpha} \approx 0.2043$ with the help of computer assistance computation, which implies $\mathcal{M}\left( s^{*,1} \right) =0$.
Theorem <ref> states that the lower bound of the nonlinear ROB condition is dominated by $\mathcal{M}\left(s\right)$
for a given adversarial corruption fraction $s$.

*(a) $\alpha, \rho \in [0,1]$.

*(b) $\alpha\in[0,0.8], \rho \in [0.2,0.8]$.

The threshold $s$ for any $\alpha, \rho \in [0,1]$.

$\mA\x=\{\langle\pmb{a}_{1},\x\rangle,\cdots,\langle\pmb{a}_{m},\x\rangle\}$ where $\pmb{a}_{i}\stackrel{i.i.d}{\sim}\mathcal{N}\left(0,\pmb{I}_{n}\right)$.
Assume that $0 \textless s \textless s^{*,1}\approx0.2043$ and $c_0$ is a positive numerical constant corresponding to $l_{0}$.

\begin{eqnarray*}
m \gtrsim \xi ^{-4}\cdot w^2\left(\text{cone}(\mathcal{K})\cap \mathbb{S}^{n-1}\right),
\end{eqnarray*}

then for any $s<s^{*,1}$,  $\mA$ satisfies the $s$-nonlinear ROB condition for all $\x,\y\in \mathcal{K}$:

\begin{equation}
\begin{split}
\frac{1}{m}\min_{\left\{\mS \subset\left[m\right],  |\mS|\leq s m\right\} }
\Bigl[\lV \lv\mA_{{\mS}^{c}} \x\rv -\lv\mA_{{\mS}^{c}} \y\rv \rV_1&-\lV \lv\mA_{\mS} \x\rv -\lv\mA_{\mS} \y\rv \rV_1 \Bigr]\\
&\ge\left[\mathcal{M}\left(s+\xi \right)-l_{0}\xi\right]\cdot\mathrm{dist}_{1}\left(\x,\y\right)
\end{split}
\end{equation}

with probability at least $1- \mathcal{O}\left(e^{-c_{0}m\xi^{2}}\right)$.

The condition $s\textless s^{*,1}$ is to ensure $\mathcal{M}\left(s+\xi \right)-l_{0}\xi\textgreater 0$. In other words, without this condition the above theorem still holds.

By setting $s=0$ and $s=1-\xi$ in the nonlinear ROB condition, we can obtain the stability of phase retrieval with upper and lower bounds. It can be considered as a random measurement version of stability in [2]. Specifically, we have the following corollary.

In the case $\mathcal{K}=\mathbb{R}^{n}$, if
$m \gtrsim \xi ^{-4}\cdot n$, then with probability at least $1- \mathcal{O}\left(e^{-c_{0}m\xi^{2}}\right)$, we have

\begin{eqnarray}\label{co1}
\left[\sqrt{\frac{2}{\pi}}\left(2-\sqrt{2}\right)-\tilde{l}\xi\right]%\mathcal{C}\left(0\right)
\cdot\mathrm{dist}_{1}\left(\x,\y\right)
\le\frac{1}{m}\lV \lv\mA \x\rv -\lv\mA \y\rv \rV_1
\le \left(  \sqrt{\frac{2}{\pi}}+   \tilde{l}\xi\   \right)\cdot\mathrm{dist}_{1}\left(\x,\y\right).
\end{eqnarray}

The lower bound  $\sqrt{\frac{2}{\pi}}\left(2-\sqrt{2}\right)$ and upper bound $\sqrt{\frac{2}{\pi}}$ here are $\mathcal{M}\left(0\right)$ and $-\mathcal{M}\left(1\right)$ given by Proposition <ref> in the subsequent subsection.

§.§ Proof of Theorem <ref> and Corollary <ref>

We divide the proof of Theorem <ref> into three steps.
The first step is to construct some properties of the minimum balance function $\mathcal{M}\left(s\right)$.
It is then stated that $\mA$ obeys the nonlinear ROB condition for fixed $\x,\y$. Finally, we use the standard covering-number based argument and Sudakov's minoration inequality to extend the result for all $\x,\y \in \mathcal{K}$.

Step 1: Properties of $\mathcal{M}\left(s\right)$.
We will prove that $\mathcal{M}\left(s\right)$ is a well-defined function and has a unique zero $s^{*,1}$.

The minimum balance function $\mathcal{M}\left(s\right)$ satisfies:

$\mathrm{(a)}$$\mathcal{M}\left(s\right)$ is strictly monotonically decreasing on interval $[0,1]$;

$\mathrm{(b)}$$\mathcal{M}\left(0\right)=\sqrt{\frac{2}{\pi}}\left(2-\sqrt{2}\right)$ and $\mathcal{M}\left(1\right)=-\sqrt{\frac{2}{\pi}}$;

$\mathrm{(c)}$$\mathcal{M}\left(s\right)$ has a unique zero $s^{*,1}$, that is $\mathcal{M}\left(s^{*,1}\right)= 0$.

For monotonicity, let $0\le s_{1} \textless s_{2} \le1$ and $\left(\rho_{1},\alpha_{1}\right)=\argmin\mathcal{M}\left(s_{1}\right)$, $\left(\rho_{2},\alpha_{2}\right)=\argmin\mathcal{M}\left(s_{2}\right)$.

By definition,

\begin{eqnarray*}
\mathcal{M}\left(s_{1}\right)=M\left(\rho_{1},\alpha_{1},s_{1}\right) \textgreater M\left(\rho_{1},\alpha_{1},s_{2}\right)\geq M\left(\rho_{2},\alpha_{2},s_{2}\right)=\mathcal{M}\left(s_{2}\right).
\end{eqnarray*}

It can be checked that $\lv \lv a \rv-\lv b \rv \rv =  \lv a+b \rv + \lv a-b \rv - \lv a \rv-\lv b \rv$, then we have

\begin{eqnarray*}
\lV\lv\mA\x\rv-\lv\mA\y\rv\rV_{1}&=&\lV\mA\left(\x+\y\right)\rV_{1}+\lV\mA\left(\x-\y\right)\rV_{1}-\lV\mA \x\rV_{1}-\lV\mA\y\rV_{1}\\
&=&\sum_{i=1}^{m}\left(\lv X_{i}+Y_{i}\rv+\lv X_{i}-Y_{i}\rv-\lv X_{i}\rv-\lv Y_{i}\rv\right).
\end{eqnarray*}

For $s=0$ or $1$, we need consider $\mathbb{E}\left(\bigl|\lv X\rv-\lv Y\rv\bigr |\right)$. Thus, let

\begin{eqnarray*}
\varphi \left(\rho,\alpha\right)&=& \frac{\int_0^{+\infty} z g_{\rho,\alpha}(z)dz}{\mathrm{dist}_{1}\left(\x,\y \right)} =\frac{\mathbb{E} \left(\bigl|\lv X \rv-\lv Y \rv\bigr|\right)}{ \mathrm{dist}_{1}\left(\x,\y \right) }
= \frac{\mathbb{E}\left(\lv X+Y \rv+\lv X-Y \rv-\lv X \rv-\lv Y \rv\right)}{ \mathrm{dist}_{1}\left(\x,\y\right) }\\
&=& \sqrt{\frac{2}{\pi}}\frac{\lV\x+\y\rV_{2}+\lV\x-\y\rV_{2}-\lV\x\rV_{2}-\lV\y\rV_{2}}{\mathrm{dist}_{1}\left(\x,\y\right)}\\
&=&\sqrt{\frac{2}{\pi}} \frac{\left(1+\alpha^{2}+2\alpha\rho\right)^{1/2}+\left(1+\alpha^{2}-2\alpha\rho\right)^{1/2}-1-\alpha}{\left(1+\alpha^{2}-2\alpha\rho\right)^{1/2}}.
\end{eqnarray*}

\begin{eqnarray*}
\frac{\partial \varphi \left(\rho,\alpha\right)}{\partial\rho}
%&=&\sqrt{\frac{2}{\pi}}\left[\partial \left(\frac{1+\alpha^{2}+2\alpha\rho}{1+\alpha^{2}-2\alpha\rho}\right)^{1/2}/\partial\rho\right]\\
\end{eqnarray*}

Therefore, for fixed $\alpha\in\left(0,1\right]$, $ \varphi\left(\rho,\alpha\right)$ is increasing with respect to $\rho$. Furthermore,

\begin{eqnarray*}
\frac{\partial \varphi \left(0,\alpha\right)}{\partial\alpha}=\sqrt{\frac{2}{\pi}}\frac{\alpha-1}{\left(1+\alpha^{2}\right)^{3/2}}\le0.
%&&\frac{\partial \varphi \left(1,\alpha\right)}{\partial\alpha}= - \sqrt{\frac{2}{\pi}} \frac{1}{\left(1+\alpha^{2}\right)^{3/2}\left(1-\alpha^{2}\right)^{1/2}}\le0.
\end{eqnarray*}

Then we can get

\begin{eqnarray*}
\mathcal{M}\left(0\right)&=&\min_{\rho,\alpha} \varphi \left(\rho,\alpha\right) = \min_{\alpha}\varphi\left(0,\alpha\right) =\varphi \left(0,1\right)=\sqrt{\frac{2}{\pi}}\left(2-\sqrt{2}\right),\\
\mathcal{M}\left(1\right)&=&-\max_{\rho,\alpha} \varphi \left(\rho,\alpha\right) = -\max_{\alpha}\varphi\left(1,\alpha\right) =
-\varphi \left(1,\alpha\right)=-\sqrt{\frac{2}{\pi}}.\\
\end{eqnarray*}

The continuity of $\mathcal{M}\left(s\right)$ is obvious. By Proposition <ref>.(a) and Proposition <ref>.(b), $\mathcal{M}\left(s\right)$ is bounded, thus it is well-defined on $\left[0,1\right]$. Then by monotonicity of $\mathcal{M}\left(s\right)$, the uniqueness of zero can be obtained.

Step 2: Proof for fixed vectors. In this step, we will establish nonlinear ROB condition for fixed $\x,\y$.

Fix $\x,\y\in \mathcal{K}$, let $\rho=\frac{\langle\x, \y\rangle}{\lV\x\rV_{2}\cdot\lV\y\rV_{2}}$ and $\alpha=\lV\y\rV_{2}/\lV\x\rV_{2}$.
For $0 \textless s\textless s^{*,1}$, there exists a positive numerical constant $c_{1}$ corresponding to $l_{1}$ such that with probability exceeding  $1-\mathcal{O}(e^{-c_{1}m\xi^{2}})$,

\begin{eqnarray}
\min_{\mS \subset[m],  |\mS|\leq s m}\frac{\lV\lv\mA_{{\mS}^{c}}\pmb{x}\rv-\lv\mA_{{\mS}^{c}}\pmb{y}\rv\rV_{1}}{\mathrm{dist}_{1}\left(\x,\y\right)}
&\geq& m\left[M_{1}(\rho,\alpha, s+\xi)-l_{1}\xi\right],\label{A1}\\
\max_{\mS \subset[m],  |\mS|\leq s m}\frac{\lV\lv\mA_{\mS}\pmb{x}\rv-\lv\mA_{\mS}\pmb{y}\rv\rV_{1}}{\mathrm{dist}_{1}\left(\x,\y\right)}
&\leq& m \left[M_{2}(\rho,\alpha, s+\xi)+l_{1}\xi \right].\label{A2}
\end{eqnarray}

Denote $h_{1}\left(x\right) = x \cdot \mathbbm{1}_{[0,t]}(x)$, and $\Gamma \left(t\right) = h_{1}\left(\frac{\lv Z_{\rho,\alpha}\rv}{\sqrt{1+\alpha^{2}-2\alpha\rho}}\right)$.

We first prove that for all $\rho,\alpha\in\left[0,1\right]$ and $t \in \mathbb{R}^{+}\cup \{+\infty\}$,
there exists $ K_{0}>0$ such that $	\lV\Gamma\left(t\right) \rV_{\psi_{2}} \leq K_{0}$.
Since $\Gamma \left(t\right) $ is bounded, thus for fixed $t$, $ \| \Gamma \left(t\right)  \|_{\psi_{2}}< \infty $.

When $t=+\infty $, we claim that $\Gamma \left(t\right) =\frac{\lv Z_{\rho,\alpha}\rv}{\sqrt{1+\alpha^{2}-2\alpha\rho}}$ is sub-Gaussian random variable. Actually, by the definition of $\lV\cdot\rV_{\psi_{2}}$

\begin{eqnarray*}
\lV\frac{\lv Z_{\rho,\alpha}\rv}{\sqrt{1+\alpha^{2}-2\alpha\rho}}\rV_{\psi_{2}}=\lV\frac{\lv \langle\pmb{a},\x\rangle\rv-\lv \langle\pmb{a},\y\rangle\rv}{\mathrm{dits}_{1}\left(\x,\y\right)}\rV_{\psi_{2}}
\le 	\lV\langle\pmb{a},\frac{\x-\y}{\lV\x-\y\rV_{2}}\rangle\rV_{\psi_{2}}=\lV X\rV_{\psi_{2}}< \infty,
\end{eqnarray*}

where $X\sim\mathcal{N}\left(0,1\right)$.
We then consider  the mapping

\begin{eqnarray*}
\mathcal{F}:\mathbb{R}\cup\{\infty \}&\longrightarrow&\mathbb{R^{+}}\cup\{+\infty \}\\
t&\longmapsto&	 \lV \Gamma \left(t\right) \rV_{\psi_{2}}.
\end{eqnarray*}

By the definition of sub-Gaussian norm, we verified that $\mathcal{F}$ is a continuous mapping.
Apart from this, the mapping

\begin{eqnarray*}
\mathcal{G}:S^{1}&\longrightarrow&\mathbb{R}\cup\{\infty \}\\
e^{i\theta}&\longmapsto&	 \frac{1+\tan\left(\theta/2\right)}{1-\tan\left(\theta/2\right)}:= t
\end{eqnarray*}

establishes the homeomorphism between $S^{1}$ and $\mathbb{R}\cup\{\infty \}$, that is $S^{1}\cong \mathbb{R}\cup\{\infty \}$.
We then direct our attention towards the composite mapping

\begin{eqnarray*}
\mathcal{F}\circ\mathcal{G}:S^{1}&\longrightarrow&\mathbb{R^{+}}\cup\{+\infty \}\\
e^{i\theta}&\longmapsto&	 \lV \Gamma\left(t\right)\rV_{\psi_{2}}.
\end{eqnarray*}

While $\mathcal{G}^{-1}\left(\mathbb{R^{+}}\cup\{+\infty \}\right)=[-\frac{\pi}{2},\frac{\pi}{2}]$,
then $\mathcal{F}\circ\mathcal{G}$ is a continuous mapping on compact set $[-\frac{\pi}{2},\frac{\pi}{2}]$.
Thereby $\mathcal{F}\circ\mathcal{G}$ is a bounded mapping, which means that there exists
$ K_{0} >0$, such that $\| \Gamma\left(t\right)\|_{\psi_{2}} \leq K_{0}$ uniformly.

Let $r\textgreater s\in (0,1)$ be a fixed constant and $t = G_{\rho,\alpha}^{-1}\left(1-r\right)$.
We consider the sampling set $\Gamma=\{\Gamma_{1}\left(t\right),\cdots,\Gamma_{m}\left(t\right)\}$ and get

\begin{eqnarray*}
\mathbb{E}\left[\Gamma \left(t\right)\right]=\frac{\int_{0 }^{t}z g_{\rho,\alpha }\left(z\right)dz}{\sqrt{1+\alpha^{2}-2\alpha\rho}}=M_{1}(\rho,\alpha,r).
\end{eqnarray*}

Thus by Hoeffding inequality in [36], we derive

\begin{eqnarray}\label{Y1}
\mathbb{P}\left(\lv {1\over m} \sum_{i=1}^m \Gamma_i\left(t\right) - \mathbb{E}\left[\Gamma \left(t\right)\right] \rv >\varepsilon_1\right) \leq 2e^{- c_{0}\,m\varepsilon_1^2/K_{0}^{2},}.
\end{eqnarray}

Based on the Dvoretzky-Kiefer-Wolfowitz type inequality in Lemma <ref>,
by setting $\epsilon = r-s \in (0, 1)$ and $\eta=1-s \in \left(0, 1\right)$, we have

\begin{eqnarray*}
t = G_{\rho,\alpha}^{-1}\left(1-r\right) \leq \widehat{G}_{\rho,\alpha}^{-1}\left(1-s\right)
\end{eqnarray*}

with probability exceeding $1-4e^{-2m\left(r-s\right)^{2}}$.
Since $\widehat{G}_{\rho,\alpha}(z)$ and $\widehat{G}_{\rho,\alpha}^{-1}\left(z\right)$ are monotonically increasing function, we can get

\begin{eqnarray*}
\widehat{G}_{\rho,\alpha}(t) \leq 1-s
\end{eqnarray*}

with probability  at least $1 - 4e^{-2m\left(r-s\right)^2}$.
Thus, we can know at most $(1-s)$-fraction of the samples lie in $[0, t]$ with probability  at least $1 - 4e^{-2m(r-s)^2}$,
and the samples lying in $[0, t]$ are smaller than those of the remaining samples.
Therefore, we have

\begin{eqnarray}\label{Y2}
\min_{\mS \subset[m],  |\mS|\leq s m}\frac{\lV\lv\mA_{{\mS}^{c}}\pmb{x}\rv-\lv\mA_{{\mS}^{c}}\pmb{y}\rv\rV_{1}}{\mathrm{dist}_{1}\left(\x,\y\right)}
\ge \sum_{i=1}^m \Gamma_i\left(t\right)
\end{eqnarray}

with probability  at least $1 - 4e^{-2m\left(r-s\right)^2}$ due to the left side of the above inequality represents the smallest $\left(1-s\right)m$ samples in the sampling set $\Gamma$.

Combining (<ref>) with (<ref>), we get

\begin{eqnarray*}
\frac{1}{m}\min_{\mS \subset[m],  |\mS|\leq s m}\frac{\lV\lv\mA_{{\mS}^{c}}\pmb{x}\rv-\lv\mA_{{\mS}^{c}}\pmb{y}\rv\rV_{1}}{\mathrm{dist}_{1}\left(\x,\y\right)}
\ge \frac{1}{m}\sum_{i=1}^m  \Gamma_i\left(t\right) \ge \mathbb{E}\left[\Gamma \left(t\right)\right] - \varepsilon_1 = M_{1}\left(\rho,\alpha,s+\epsilon\right)-\varepsilon_1
\end{eqnarray*}

with certain probability.
By setting $\epsilon =\xi$ and $\varepsilon_1= l_{1}\xi$,

we finally get (<ref>) with probability  exceeding $1 -\mathcal{O}\left(e^{-c_{1}m\xi^{2}}\right)$.

Similarly, we can establish (<ref>) if we
set $h_{2}\left(x\right) = x\cdot \mathbbm{1}_{\left[t,+\infty\right)}\left(x\right)$ and $\Gamma\left(t\right) =h_{2}\left(\frac{\lv Z_{\rho,\alpha}\rv}{\sqrt{1+\alpha^{2}-2\alpha\rho}}\right)$.

Step 3: Uniform  argument.
By Lemma <ref>,  for fixed $\x_{0},\y_{0}\in\mathcal{K}$ with parameters $\rho_{0}$ and $\alpha_{0}$, with probability at least $1 - \mathcal{O}\left(e^{- c_{1} m\xi^2}\right)$ we have that

\begin{eqnarray*}\label{A3}
\begin{split}
&\min_{\mS \subset[m],  |\mS|\leq s m} \lV\lv\mA_{{\mS}^{c}}\x_{0}\rv-\lv\mA_{{\mS}^{c}}\y_{0}\rv\rV_{1}-\lV\lv\mA_{{\mS}}\x_{0}\rv-\lv\mA_{{\mS}}\y_{0}\rv\rV_{1}\\
&= \min_{\mS \subset[m],  |\mS|\leq s m} \left[\sum_{i\in{\mS}^{c}} \bigl|\lv \langle\pmb{a}_{i}, \pmb{x}_{0}\rangle \rv-\lv\langle\pmb{a}_{i}, \pmb{y}_{0}\rangle \rv\bigr|-\sum_{i\in\mS} \bigl|\lv \langle\pmb{a}_{i}, \pmb{x}_{0}\rangle\rv-\lv \langle\pmb{a}_{i}, \pmb{y}_{0}\rangle \rv\bigr|\right]\\
&\ge m\left[M_{1}\left(\rho_{0},\alpha_{0},s+\xi\right)-M_{2}\left(\rho_{0},\alpha_{0},s+\xi\right)-2l_{1}\xi\right]\cdot\mathrm{dist}_{1}\left(\x_{0},\y_{0}\right)\\
&\ge m\left[\mathcal{M}\left(s+\xi\right)-2l_{1}\xi\right]\cdot\mathrm{dist}_{1}\left(\x_{0},\y_{0}\right).
\end{split}
\end{eqnarray*}

We divide the proof into three types of situations.

Case 1:  In this case we assume that $\lV\x-\y\rV_{2}\le\lV\x+\y\rV_{2}\le5\lV\x-\y\rV_{2}$.  We can let $\lV\x\rV_{2}\ge\lV\y\rV_{2}$, then by standardization, set $\x\in\mathcal{K}\cap\mathcal{S}^{n}$ and $\y\in \mathcal{K}\cap B_2^n$. Then we let $\mathcal{K}^{1}_{\delta },\mathcal{K}^{2}_{\delta }$ be the $\delta$-net of $\text{cone}(\mathcal{K})\cap \mathbb{S}^{n-1}$ and $\text{cone}(\mathcal{K})\cap B_2^n$.
Now for all $\x\in\mathcal{K}\cap\mathcal{S}^{n}$ and $\y\in \mathcal{K}\cap B_2^n$, there exist $\x_{0}\in\mathcal{K}^{1}_{\delta }$ and $\y_{0}\in\mathcal{K}^{2}_{\delta }$, such that $\lV\x-\x_{0}\rV_{2}\le\delta, \lV\y-\y_{0}\rV_{2}\le\delta$.

Set $\mS_{1}$ be the index set of the largest $s$-fraction of $\mS_{\pmb{x},\pmb{y}}=\{\lv\langle\pmb{a}_{i}, \pmb{x}\rangle\rv -\lv\langle\pmb{a}_{i}, \pmb{y}\rangle\rv | i\in[m] \}$ in absolute value.
Similarly, $\mS_{2}$ be the subset of $\mS_{\pmb{x}_{0},\pmb{y}_{0}}$,  which collects the index of the largest $s$-fraction of $\mS_{\pmb{x}_{0},\pmb{y}_{0}}$ in absolute value.
Then, we have

\begin{eqnarray*}
\begin{split}
\min_{\mS \subset[m],  |\mS|\leq s m}
=\sum_{i\in{\mS}_{1}^{c}} \bigl| \lv \langle\pmb{a}_{i}, \pmb{x}\rangle\rv -\lv\langle\pmb{a}_{i}, \pmb{y}\rangle \rv\bigr| \\
\ge&\sum_{i\in{\mS}_{1}^{c}} \bigl| \lv \langle\pmb{a}_{i}, \pmb{x}_{0}\rangle\rv -\lv\langle\pmb{a}_{i}, \pmb{y}_{0}\rangle \rv\bigr| -
\sum_{i\in{\mS}_{1}^{c}} \bigl|\lv \langle\pmb{a}_{i}, \pmb{x}\rangle\rv-\lv \langle\pmb{a}_{i}, \pmb{x}_{0}\rangle\rv -\lv\langle\pmb{a}_{i}, \pmb{y}\rangle\rv +\lv \langle\pmb{a}_{i}, \pmb{y}_{0}\rangle\rv \bigr| \\
\ge&\sum_{i\in{\mS}_{2}^{c}} \bigl|\lv \langle\pmb{a}_{i}, \pmb{x}_{0}\rangle\rv -\lv\langle\pmb{a}_{i}, \pmb{y}_{0}\rangle \rv\bigr|-
%\sum_{i\in{\mS}_{1}^{c}} \lv\lv \langle\pmb{a}_{i}, \pmb{x}\rangle\rv-\lv \langle\pmb{a}_{i}, \pmb{x}_{0}\rangle\rv -\lv\langle\pmb{a}_{i}, \pmb{y}\rangle\rv +\lv \langle\pmb{a}_{i}, \pmb{y}_{0}\rangle\rv\rv\\
\lV\lv \mA_{{\mS}_{1}^{c}}\x\rv-\lv \mA_{{\mS}_{1}^{c}}\x_{0}\rv -\lv\mA_{{\mS}_{1}^{c}}\y\rv +\lv\mA_{{\mS}_{1}^{c}}\y_{0}\rv\rV_{1}\\
%-\sum_{i\in{\mS}_{1}^{c}} \lv \langle\pmb{a}_{i}\pmb{a}^{*}_{i}, \pmb{u}\pmb{v}^{*}-\pmb{u}_{0}\pmb{v}_{0}^{*}\rangle\rv\\
=&	\min_{\mS \subset[m],  |\mS|\leq s m} \lV\lv\mA_{{\mS}^{c}}\x_{0}\rv-\lv\mA_{{\mS}^{c}}\y_{0}\rv\rV_{1}
-\lV\lv \mA_{{\mS}_{1}^{c}}\x\rv-\lv \mA_{{\mS}_{1}^{c}}\x_{0}\rv -\lv\mA_{{\mS}_{1}^{c}}\y\rv +\lv\mA_{{\mS}_{1}^{c}}\y_{0}\rv\rV_{1}.\\
%&-&\sum_{i\in{\mS}_{1}^{c}} \lv\lv \langle\pmb{a}_{i}, \pmb{x}\rangle\rv-\lv \langle\pmb{a}_{i}, \pmb{x}_{0}\rangle\rv -\lv\langle\pmb{a}_{i}, \pmb{y}\rangle\rv +\lv \langle\pmb{a}_{i}, \pmb{y}_{0}\rangle\rv\rv.
\end{split}
\end{eqnarray*}

Similarly, we can get

\begin{eqnarray*}
\begin{split}
&\max_{\mS \subset[m],  |\mS|\leq s m} \lV\lv\mA_{{\mS}}\x\rv-\lv\mA_{{\mS}}\y\rv\rV_{1}\\
&\le\max_{\mS \subset[m],  |\mS|\leq s m} \lV\lv\mA_{{\mS}}\x_{0}\rv-\lv\mA_{{\mS}}\y_{0}\rv\rV_{1}
+\lV\lv \mA_{{\mS}_{1}}\x\rv-\lv \mA_{{\mS}_{1}}\x_{0}\rv -\lv\mA_{{\mS}_{1}}\y\rv +\lv\mA_{{\mS}_{1}}\y_{0}\rv\rV_{1}.\\
%-\sum_{i\in{\mS}_{1}} \lv\lv \langle\pmb{a}_{i}, \pmb{x}\rangle\rv-\lv \langle\pmb{a}_{i}, \pmb{x}_{0}\rangle\rv -\lv\langle\pmb{a}_{i}, \pmb{y}\rangle\rv +\lv \langle\pmb{a}_{i}, \pmb{y}_{0}\rangle\rv\rv.
\end{split}
\end{eqnarray*}

We then present the following lemma.

For any $\pmb{z}_{1},\pmb{z}_{2}$ and
$\pmb{a}_{i}\stackrel{i.i.d}{\sim}\mathcal{N}\left(0,\pmb{I}_{n}\right)$, we have

\begin{eqnarray}
\mathbb{P}\left(\frac{1}{m}\lV\lv \mA\pmb{z}_{1}\rv-\lv \mA\pmb{z}_{2}\rv\rV_{1}\ge\sqrt{\frac{2}{\pi}}\left(1+\epsilon\right)\lV\pmb{z}_{1}-\pmb{z}_{2}\rV_{2}\right)\le2\exp\left(-c_{1}m\epsilon^{2}/K^{2}_{1}\right),
\end{eqnarray}

where $K_{1}=\sqrt{8/3}$ and $c_{1}$ is a positive numerical constant.

It can be seen that  $\big|\lv \langle\pmb{a},\pmb{z}_{1}\rangle\rv-\lv \langle\pmb{a},\pmb{z}_{2}\rangle\rv\big|\le\lv \langle\pmb{a},\pmb{z}_{1}- \pmb{z}_{2}\rangle)\rv$ and $\mathbb{E}\left[\lv \langle\pmb{a},\pmb{z}_{1}- \pmb{z}_{2}\rangle)\rv\right]=\sqrt{\frac{2}{\pi}}\lV\pmb{z}_{1}- \pmb{z}_{2}\rV_{2}$.
Furthermore, random variable $\lv \langle\pmb{a},\pmb{z}/\lV\pmb{z}\rV_{2}\rangle\rv$ has sub-Guassian norm $\sqrt{8/3}$. Then by Hoeffding inequality in [36], we have reached the conclusion.

Jointing the above two inequalities and Lemma <ref>, we obtain that

\begin{eqnarray*}
\begin{split}
&\min_{\mS \subset[m],|\mS|\leq s m} \lV\lv\mA_{{\mS}^{c}}\x\rv-\lv\mA_{{\mS}^{c}}\y\rv\rV_{1}-\lV\lv\mA_{{\mS}}\x\rv-\lv\mA_{{\mS}}\y\rv\rV_{1}\\
&\ge\min_{\mS \subset[m],|\mS|\leq s m}\lV\lv\mA_{{\mS}^{c}}\x_{0}\rv-\lv\mA_{{\mS}^{c}}\y_{0}\rv\rV_{1}-\lV\lv\mA_{{\mS}}\x_{0}\rv-\lv\mA_{{\mS}}\y_{0}\rv\rV_{1}			-\lV\lv\mA\x\rv-\lv\mA\x_{0}\rv-\lv\mA\y\rv+\lv\mA\y_{0}\rv\rV_{1}\\
&\ge m\left[\mathcal{M}\left(s+\xi\right)-2l_{1}\xi\right]\cdot\mathrm{dist}\left(\x_{0},\y_{0}\right)-
\lV\lv\mA\x\rv-\lv\mA\x_{0}\rv\rV_{1}-\lV\lv\mA\y\rv-\lv\mA\y_{0}\rv\rV_{1}\\
&\ge m\left[\mathcal{M}\left(s+\xi\right)-2l_{1}\xi\right]\cdot\left(\mathrm{dist}_{1}\left(\x,\y\right)-2\delta\right)-\sqrt{2/\pi}\left(1+\epsilon\right)\left(\lV\x-\x_{0}\rV_{2}+\lV\y-\y_{0}\rV_{2}\right)\\
&\ge m\left[\mathcal{M}\left(s+\xi\right)-2l_{1}\xi\right]\cdot\mathrm{dist}_{1}\left(\x,\y\right)-\left[2\sqrt{2/\pi}\left(1+\epsilon\right)+2\mathcal{M}\left(0\right)\right]m\delta\\
&\ge m\left[\mathcal{M}\left(s+\xi\right)-2l_{0}\xi\right]\cdot\mathrm{dist}_{1}\left(\x,\y\right).
\end{split}
\end{eqnarray*}

In the forth line we use Lemma <ref>  and the fact that $\lV\x_{0}-\y_{0}\rV_{2}\ge\lV\x-\y\rV_{2}-2\delta$.

We can set $l_{0}\textgreater l_{1}$ such that $\left[2\sqrt{2/\pi}\left(1+\epsilon\right)+2\mathcal{M}\left(0\right)\right]\delta+l_{1}\xi\cdot\mathrm{dist}_{1}\left(\x,\y\right)=l_{0}\xi\cdot\mathrm{dist}_{1}\left(\x,\y\right)$ (thus $\delta\ge\tilde{c}\xi$) in the last step as $\mathrm{dist}_{1}\left(\x,\y\right)=\lV\x-\y\rV_{2}\ge\lV\x+\y\rV_{2}/5\ge1/5$.

Case 2:  We assume that $5\lV\x-\y\rV_{2}\le\lV\x+\y\rV_{2}$.  Due to $\x,\y\in\mathcal{K}$, we have $\x-\y\in\mathcal{K}-\mathcal{K}$. By standardization, we let $\x-\y\in\left(\mathcal{K}-\mathcal{K}\right)\cap\mathcal{S}^{n}$. Then let $\mathcal{K}^{-}_{\delta }$ be the $\delta$-net of $\text{cone}\left(\mathcal{K}-\mathcal{K}\right)\cap \mathbb{S}^{n-1}$. Now for all $\pmb{u}:=\x-\y\in\left(\mathcal{K}-\mathcal{K}\right)\cap\mathcal{S}^{n}$, their exist $\pmb{u}_{0}:=\x_{0}-\y_{0}\in\mathcal{K}^{-}_{\delta}$, such that $\lV\pmb{u}-\pmb{u}_{0}\rV_{2}\le\delta$.

For $\rho=\langle\x/\lV\x\rV_{2},\y/\lV\y\rV_{2}\rangle$, set $\mathcal{K}^{\rho}_{\delta}$ be the $\delta$-net of $\rho\in\left[0,1\right]$. Thus $\mathcal{N}\left(\mathcal{K}^{\rho}_{\delta },\delta\right)\le\mathcal{N}\left(\mathcal{K}^{1}_{\delta },\delta\right)\times\mathcal{N}\left(\mathcal{K}^{2}_{\delta },\delta\right)$.
Due to $\lV\x+\y\rV_{2}\ge5\lV\x-\y\rV_{2}$, we have $\rho\textgreater0$. There exists $\rho_{0}\in\mathcal{K}^{\rho}_{\delta }$, such that $\lv\rho-\rho_{0}\rv\le\delta$, then for small enough $\delta$, we have both $\rho,\rho_{0}\textgreater0$. Then we can get

\begin{eqnarray*}
\begin{split}
\mathbb{E}\big|\lv\langle\pmb{a},\x\rangle\rv-\lv\langle\pmb{a},\x_{0}\rangle\rv-\lv\langle\pmb{a},\y\rangle\rv+\lv\langle\pmb{a},\y_{0}\rangle\rv\big|
\le\mathbb{E} \lv\langle \pmb{a},\pmb{u}-\pmb{u}_{0}\rangle\rv \le \sqrt{\frac{2}{\pi}}\delta.
\end{split}
\end{eqnarray*}

Due to Lemma <ref>, we have the following concentration inequality

\begin{eqnarray}
\mathbb{P}\left(\frac{1}{m}\lV\lv \mA\pmb{x}\rv-\lv \mA\pmb{y}\rv-\lv \mA\pmb{x}_{0}\rv+\lv \mA\pmb{y}_{0}\rv\rV_{1}\ge \sqrt{\frac{2}{\pi}}\delta\left(1+\epsilon\right)\right)\le2\exp\left(-c_{1}m\epsilon^{2}\right).
\end{eqnarray}

We then obtained that

\begin{eqnarray*}
\begin{split}
&\min_{\mS \subset[m],|\mS|\leq s m} \lV\lv\mA_{{\mS}^{c}}\x\rv-\lv\mA_{{\mS}^{c}}\y\rv\rV_{1}-\lV\lv\mA_{{\mS}}\x\rv-\lv\mA_{{\mS}}\y\rv\rV_{1}\\
&\ge m\left[\mathcal{M}\left(s+\xi\right)-2l_{1}\xi\right]\cdot\mathrm{dist}_{1}\left(\x_{0},\y_{0}\right)-
\lV\lv\mA\x\rv-\lv\mA\x_{0}\rv-\lv\mA\y\rv+\lv\mA\y_{0}\rv\rV_{1}\\
&\ge m\left[\mathcal{M}\left(s+\xi\right)-2l_{1}\xi\right]\cdot\left(\mathrm{dist}_{1}\left(\x,\y\right)-\delta\right)-\sqrt{\frac{2}{\pi}}\delta\left(1+\epsilon\right)m\cdot\mathrm{dist}_{1}\left(\x,\y\right)\\
&\ge m\left[\mathcal{M}\left(s+\xi\right)-2l_{1}\xi\right]\cdot\mathrm{dist}_{1}\left(\x,\y\right)-\left[\sqrt{\frac{2}{\pi}}\left(1+\epsilon\right)+\mathcal{M}\left(0\right)\right]m\delta\cdot\mathrm{dist}_{1}\left(\x,\y\right)		\\
&= m\left[\mathcal{M}\left(s+\xi\right)-2l_{0}\xi\right]\cdot\mathrm{dist}_{1}\left(\x,\y\right).
\end{split}
\end{eqnarray*}

Case 3:  We assume that $\lV\x+\y\rV_{2}\le\lV\x-\y\rV_{2}$.  Then $\x+\y\in\mathcal{K}+\mathcal{K}$, we let $\x+\y\in\left(\mathcal{K}+\mathcal{K}\right)\cap\mathcal{S}^{n}$. Then let $\mathcal{K}^{+}_{\delta }$ be the $\delta$-net of $\text{cone}\left(\mathcal{K}+\mathcal{K}\right)\cap \mathbb{S}^{n-1}$. The remain classification and arguments are similar to Case 1 and Case 2.

By properties $w\left(\mathcal{K}+\mathcal{K}\right)=2w\left(\mathcal{K}\right), w\left(\mathcal{K}-\mathcal{K}\right)=\frac{1}{2}w\left(\mathcal{K}\right)$, we have

\begin{equation*}
\begin{split}
&\max\{C_{1}w^2\left(\text{cone}(\mathcal{K})\cap B_2^n\right),C_{2}w^{2}\left(\text{cone}\left(\mathcal{K}-\mathcal{K}\right)\cap\mathbb{S}^{n-1}\right),C_{3}w^{2}\left(\text{cone}\left(\mathcal{K}+\mathcal{K}\right)\cap\mathbb{S}^{n-1}\right)\}\\
\end{split}
\end{equation*}

Then by Sudakov’s minoration inequality in (<ref>), for any $\delta\textgreater0$,
we can get

\begin{equation*}
\begin{split}
&\max\{\log\mathcal{N}\left(\mathcal{K}^{1}_{\delta },\delta\right),\log\mathcal{N}\left(\mathcal{K}^{2}_{\delta },\delta\right),\log\mathcal{N}\left(\mathcal{K}^{-}_{\delta },\delta\right),\log\mathcal{N}\left(\mathcal{K}^{+}
_{\delta },\delta\right)\}\\
&\le C_{4}w^{2}\left(\text{cone}\left(\mathcal{K}\right)\cap\mathbb{S}^{n-1}\right)/\delta^{2}.
\end{split}
\end{equation*}

Finally, we can finish the proof with probability at least

\begin{eqnarray*}
C_{5}\left(\mathcal{N}\left(\mathcal{K}^{1}_{\delta },\delta\right)\times\mathcal{N}\left(\mathcal{K}^{2}_{\delta },\delta\right)\times\mathcal{N}\left(\mathcal{K}^{-}_{\delta },\delta\right)\times\mathcal{N}\left(\mathcal{K}^{+}_{\delta },\delta\right)\right)\left(\mathcal{O}\left(e^{-cm\xi^{2}}\right)+2e^{-c_{1}m\delta^{2}}\right)\\
\end{eqnarray*}

as we have provided $m \gtrsim \xi ^{-4}\cdot w^{2}\left(\text{cone}(\mathcal{K})\cap\mathbb{S}^{n-1}\right)$.

We then present the proof of Corollary <ref>. We first set $s=0$, then we have

\begin{eqnarray*}
\frac{1}{m}\lV \lv\mA \x\rv -\lv\mA \y\rv \rV_1\ge \left[\mathcal{M}\left(\xi\right)-l_{0}\xi\right]	\cdot\mathrm{dist}_{1}\left(\x,\y\right).
\end{eqnarray*}

By Proposition <ref>,
we can assume $\mathcal{M}\left(s\right)$ has Lipschitz constant $L$.
Thus $\lv\mathcal{M}\left(0\right)-\mathcal{M}\left(\xi\right)\rv\le L\xi$ and we set $\tilde{l}=L+l_{0}$ to get the left-hand inequality of (<ref>).

We set $s=1-\xi$ to get

\begin{eqnarray*}
\frac{1}{m}\lV \lv\mA \x\rv -\lv\mA \y\rv \rV_1&\le& \left[-\mathcal{M}\left(1\right)+l_{0}\xi\right]\cdot\mathrm{dist}_{1}\left(\x,\y\right)+
\frac{2}{m}\min_{\left\{\mS \subset\left[m\right],  |\mS|\leq \left(1-\xi\right)m\right\} }
\lV \lv\mA_{{\mS}^{c}} \x\rv -\lv\mA_{{\mS}^{c}} \y\rv \rV_1\\
\frac{2}{m}\xi
\lV \lv\mA\x\rv -\lv\mA \y\rv \rV_1\\
4\xi\lV\x-\y\rV_{2}	\le	\left[\sqrt{\frac{2}{\pi}}+\left(l_{0}+4\right)\xi\right]\cdot\mathrm{dist}_{1}\left(\x,\y\right).
\end{eqnarray*}

In the last second inequality we use Lemma <ref>. Actually the right-hand inequality of (<ref>) can be obtained concisely using Lemma <ref>, but we omit it here.

§.§ Nonlinear ROB Condition for Intensity Measurement

It can be checked that

\begin{eqnarray*}
\frac{\lV\lv\mA\pmb{x}\rv^{2}-\lv\mA\pmb{y}\rv^{2}\rV_{1}}{\mathrm{dist}_{2}\left(\x,\y\right)}
&=& \sum_{i=1}^{m}\lvert \langle\pmb{a}_{i}, \frac{\x-\y}{\lV\x-\y\rV_{2}}\rangle \cdot\langle\pmb{a}_{i}, \frac{\x+\y}{\lV\x+\y\rV_{2}}\rangle \rvert\\
&=& \sum_{i=1}^{m}\lvert \langle\pmb{a}_{i}, \pmb{u}\rangle  \cdot\langle\pmb{a}_{i}, \pmb{v}\rangle \rvert :=\sum_{i=1}^{m}\lvert X\cdot Y\rvert,%:=\sum_{i=1}^{m}\xi_{i}.
\end{eqnarray*}

where we set $\pmb{u}=\frac{\x-\y}{\lV\x-\y\rV_{2}}\in\mathbb{S}^{n-1},\pmb{v}=\frac{\x+\y}{\lV\x+\y\rV_{2}}\in\mathbb{S}^{n-1}$ and $X=\langle\pmb{a}_{i}, \pmb{u}\rangle\sim \mathcal{N}\left(0,1\right), Y=\langle\pmb{a}_{i}, \pmb{v}\rangle\sim \mathcal{N}\left(0,1\right)$.
The correlation coefficient between random variables $X$ and $Y$ is

$\rho:=\langle\pmb{u}, \pmb{v}\rangle$,

then by Lemma 2 in [18], the PDF of $\left|Z_{\rho}\right|:=\left|X\cdot Y\right|$ is

\begin{equation} \label{|xy|}
f_{\rho}\left(z\right) = %f_{Z_{\rho}}\left(z\right)+f_{Z_{\rho}}\left(-z\right)
\begin{cases}
\frac{1}{\sqrt{2\pi z}}e^{-z/2} &\rho=\pm 1 \\
\frac{2}{\pi\sqrt{1-\rho^2}} \cosh \left(\frac{\rho z}{1-\rho^2}\right) K_0\left( \frac{z}{1-\rho^2} \right) &-1<\rho<1,
\end{cases}
\end{equation}

where $K_0(\cdot)$ denotes the modified Bessel function of the second kind of order zero. For completeness, we attach the proof of (<ref>) to Appendix <ref>.
Then we set the CDF of $|Z_{\rho}|$ as

\begin{eqnarray*}
F_{\rho}(t) = \int_{0}^{t} f_{\rho}(z) dz.
\end{eqnarray*}

And we define the balance function for $\lv Z_{\rho}\rv$:

\begin{eqnarray*}
J\left(\rho, s\right) = J_{1}\left(\rho, s\right)-J_{2}\left(\rho, s\right):=\left[ \int_0^{F_{\rho}^{-1}\left(1-s\right)} - \int_{F_{\rho}^{-1}\left(1-s\right)}^{+\infty} \right] z f_{\rho}(z)dz.
\end{eqnarray*}

We can only consider $\rho\ge 0$, thus the minimum balance function here is

\begin{eqnarray}
\mathcal{J}\left(s\right)=\min_{\rho \in\left[0,1\right]}\left[\int_{0 }^{F_{\rho}^{-1}\left(1-s\right)}- \int_{F_{\rho}^{-1}\left(1-s\right) }^{+\infty} \right]z f_{\rho }\left(z\right)dz.
\end{eqnarray}

Now we present the following theorem.

$\mA\x=\{\langle\pmb{a}_{1},\x\rangle,\cdots,\langle\pmb{a}_{m},\x\rangle\}$ where $\pmb{a}_{i}\stackrel{i.i.d}{\sim}\mathcal{N}\left(0,\pmb{I}_{n}\right)$.

Assume that $0 \textless s\textless s^{*,2}\approx0.1185$ and $c_0$ is a positive numerical constant corresponding to $l_{0}$.

\begin{eqnarray*}
m \gtrsim \xi ^{-4}\cdot w^2\left(\text{cone}\left(\mathcal{K}\right)\cap \mathbb{S}^{n-1}\right),
%\color{red}{ m \gtrsim [\xi %^{-2}\ln\xi^{-1}]\cdot\max\left\{w^{2}\left[\left(K+K\right)\cap\mathbb{S}^{n-1}\right],w^{2}\left[\left(K-K\right)\right]\cap\math%bb{S}^{n-1}\right\},}
\end{eqnarray*}

then for any $s<s^{*,2}$,  $\mA$ satisfies the $s$-nonlinear ROB condition for all $\x,\y\in \mathcal{K}$:

\begin{equation}
\begin{split}
\frac{1}{m}\min_{\left\{\mS \subset\left[m\right],  |\mS|\leq s m\right\} }
\Bigl[\lV \lv\mA_{{\mS}^{c}} \x\rv^{2} -\lv\mA_{{\mS}^{c}} \y\rv^{2} \rV_1&-\lV \lv\mA_{\mS} \x\rv^{2} -\lv\mA_{\mS} \y\rv^{2} \rV_1 \Bigr]\\
&\ge\left[\mathcal{J}\left(s+\xi \right)-l_{0}\xi\right]\cdot\mathrm{dist}_{2}\left(\x,\y\right)
\end{split}
\end{equation}

with probability at least $1- \mathcal{O}\left(e^{-c_{0}m\xi^{2}}\right)$.

The distinction between nonlinear ROB condition and ROB condition in intensity measurement, as discussed in [18], lies in the specific ranges of consideration. The former limits the consideration range to $\pmb{u}=\frac{\x-\y}{\lV\x-\y\rV_{2}},\pmb{v}=\frac{\x+\y}{\lV\x+\y\rV_{2}}\in\mathbb{S}^{n-1}$, while the latter considers the tangent space $T=\{ \x\y^{*}+\y\x^{*}:\x,\y\in\mathbb{R}^{n}\}$. However, both conditions ultimately lead to the same threshold value of 0.1185.

Similar to the Corollary <ref>, if we set $s=0$ and $s=1-\xi$ in the nonlinear ROB condition for intensity measurement respectively, wo have the following corollary.

When $\mathcal{K}=\mathbb{R}^{n}$ and $m \gtrsim \xi ^{-4}\cdot n$
with probability at least $1- \mathcal{O}\left(e^{-c_{0}m\xi^{2}}\right)$, we have

\begin{eqnarray*}
\left(\frac{2}{\pi}-\tilde{l}\xi\right)%\mathcal{C}\left(0\right)
\cdot\mathrm{dist}_{2}\left(\x,\y\right)
\le\frac{1}{m}\lV \lv\mA \x\rv^{2} -\lv\mA \y\rv^{2} \rV_1
\le \left(  1+   \tilde{l}\xi\   \right)\cdot\mathrm{dist}_{2}\left(\x,\y\right).
\end{eqnarray*}

Therefore, our nonlinear ROB condition can be seen as a version with outliers in the stability of phase retrieval in [14].

§.§ Proof of Theorem <ref> and Corollary <ref>

In a manner analogous to the demonstration of Theorem <ref>, the proof of Theorem 6 will be partitioned into three steps.

For simplicity and convenience of reading, we attach the proofs of Step 1 and Step 2 to Appendix <ref> and
due to the similarity between the proof of Corollary <ref> and Corollary <ref>, we omit it.

Step 1: Properties of $\mathcal{J}\left(s\right)$.
This step provides that $\mathcal{J}\left(s\right)$ is a well-defined function and has a unique zero $s^{*,2}\approx0.1185$.

The minimum balance function $\mathcal{J}\left(s\right)$ satisfies:

$\mathrm{(a)}$$\mathcal{J}\left(s\right)$ is a strictly monotonically decreasing continuous function on interval $\left[0,1\right]$;

$\mathrm{(b)}$$\mathcal{J}\left(s\right)$ has a unique zero $s^{*,2}$, that is $\mathcal{J}\left(s^{*,2}\right)= 0$.

Step 2: Fixed vectors description.

Fix $\x,\y\in \mathcal{K}$ and let $\rho=\langle\frac{\x-\y}{\lV\x-\y\rV_{2}},\frac{\x+\y}{\lV\x+\y\rV_{2}}\rangle$.
For $0 \textless s \textless s^{*,2}$, there exists a positive numerical constant $c_{1}$ corresponding to $l_{1}$ such that with probability at least $1-\mathcal{O}\left(e^{-c_{1}m\xi^{2}}\right)$,

\begin{eqnarray}
\min_{\mS \subset[m],  |\mS|\leq s m}\frac{\lV\lv\mA_{{\mS}^{c}}\pmb{x}\rv^{2}-\lv\mA_{{\mS}^{c}}\pmb{y}\rv^{2}\rV_{1}}{\mathrm{dist}_{2}\left(\x,\y\right)}
&\geq& m\left[J_{1}(\rho, s+\xi)-l_{1}\xi\right],\label{B5}\\
\max_{\mS \subset[m],  |\mS|\leq s m}\frac{\lV\lv\mA_{\mS}\pmb{x}\rv^{2}-\lv\mA_{\mS}\pmb{y}\rv^{2}\rV_{1}}{\mathrm{dist}_{2}\left(\x,\y\right)}
&\leq& m \left[J_{2}(\rho, s+\xi)+l_{1}\xi \right].\label{B6}
\end{eqnarray}

Step 3: Uniform  argument.
By Lemma <ref>, we have that for fixed $\x_{0},\y_{0}\in \mathcal{K}$ with $\rho_{0}=\langle \frac{\x_{0}-\y_{0}}{\lV\x_{0}-\y_{0}\rV_{2}},\frac{\x_{0}+\y_{0}}{\lV\x_{0}+\y_{0}\rV_{2}} \rangle:=\langle \pmb{u}_{0},\pmb{v}_{0}\rangle$, with probability at least $1 - \mathcal{O}\left(e^{- c_{1} m\xi^2}\right)$,

\begin{equation*}\label{B1}
\begin{split}
&\min_{\mS \subset[m],  |\mS|\leq s m} \frac{\lV\lv\mA_{{\mS}^{c}}\x_{0}\rv^{2}-\lv\mA_{{\mS}^{c}}\y_{0}\rv^{2}\rV_{1}-\lV\lv\mA_{{\mS}}\x_{0}\rv^{2}-\lv\mA_{{\mS}}\y_{0}\rv^{2}\rV_{1}}{\mathrm{dist}_{2}\left(\x_{0},\y_{0}\right)}\\
&= \min_{\mS \subset[m],  |\mS|\leq s m} \left[\sum_{i\in{\mS}^{c}} \lv \langle\pmb{a}_{i}, \pmb{u}_{0}\rangle \cdot\langle\pmb{a}_{i}, \pmb{v}_{0}\rangle \rv-\sum_{i\in\mS} \lv \langle\pmb{a}_{i}, \pmb{u}_{0}\rangle \cdot\langle\pmb{a}_{i}, \pmb{v}_{0}\rangle \rv\right]\\
&\ge m\left[J_{1}\left(\rho_{0},s+\xi\right)-J_{2}\left(\rho_{0},s+\xi\right)-2l_{1}\xi\right]\\
&\ge m\left[\mathcal{J}\left(s+\xi\right)-2l_{1}\xi\right].
\end{split}
\end{equation*}

As we can see $\pmb{u}_{0}\in \left(\mathcal{K}-\mathcal{K}\right)\cap\mathbb{S}^{n-1}$ and $\pmb{v}_{0}\in \left(\mathcal{K}+\mathcal{K}\right)\cap\mathbb{S}^{n-1}$.
Let $\mathcal{K}^{-}_{\delta },\mathcal{K}^{+}_{\delta }$ be the $\delta$-net of $\text{cone}\left(\mathcal{K}-\mathcal{K}\right)\cap\mathbb{S}^{n-1}$ and $\text{cone}\left(\mathcal{K}+\mathcal{K}\right)\cap\mathbb{S}^{n-1}$.

Now for all $\pmb{u}\in\left(\mathcal{K}-\mathcal{K}\right)\cap\mathcal{S}^{n},\pmb{v}\in \left(\mathcal{K}+\mathcal{K}\right)\cap \mathcal{S}^{n}$, there exist $\pmb{u}_{0}\in\mathcal{K}^{-}_{\delta },\pmb{v}_{0}\in\mathcal{K}^{+}_{\delta }$, such that $\lV\pmb{u}-\pmb{u}_{0}\rV_{2}\le\delta, \lV\pmb{v}-\pmb{v}_{0}\rV_{2}\le\delta$. Then set $\mS_{1}$ be the index set of the largest $s$-fraction of $\mS_{\pmb{u},\pmb{v}}=\{\langle\pmb{a}_{i}, \pmb{u}\rangle \cdot\langle\pmb{a}, \pmb{v}\rangle  | i\in[m]
\}$ in absolute value.
Similarly, $\mS_{2}$ be the subset of $\mS_{\pmb{u}_{0},\pmb{v}_{0}}$, collecting the index of the largest $s$-fraction of $\mS_{\pmb{u}_{0},\pmb{v}_{0}}$ in absolute
Then we have

\begin{equation*}
\begin{split}
\min_{\mS \subset[m],  |\mS|\leq s m}
=\sum_{i\in{\mS}_{1}^{c}} \lv \langle\pmb{a}_{i}, \pmb{u}\rangle \cdot\langle\pmb{a}_{i}, \pmb{v}\rangle \rv\\
%	&\ge&\sum_{i\in{\mS}_{1}^{c}} \lv \langle\pmb{a}_{i}, \pmb{u}_{0}\rangle \cdot\langle\pmb{a}_{i}, \pmb{v}_{0}\rangle \rv-
%	\sum_{i\in{\mS}_{1}^{c}} \lv \langle\pmb{a}_{i}, \pmb{u}\rangle \cdot\langle\pmb{a}_{i}, \pmb{v}\rangle- \langle\pmb{a}_{i}, \pmb{u}_{0}\rangle \cdot\langle\pmb{a}_{i},
%	\pmb{v}_{0}\rangle\rv\\
&\ge\sum_{i\in{\mS}_{2}^{c}} \lv \langle\pmb{a}_{i}, \pmb{u}_{0}\rangle \cdot\langle\pmb{a}_{i}, \pmb{v}_{0}\rangle \rv-
\sum_{i\in{\mS}_{1}^{c}} \lv \langle\pmb{a}_{i}, \pmb{u}\rangle \cdot\langle\pmb{a}_{i}, \pmb{v}\rangle- \langle\pmb{a}_{i}, \pmb{u}_{0}\rangle \cdot\langle\pmb{a}_{i},
\pmb{v}_{0}\rangle\rv\\
-\sum_{i\in{\mS}_{1}^{c}} \lv \langle\pmb{a}_{i}\pmb{a}^{*}_{i}, \pmb{u}\pmb{v}^{*}-\pmb{u}_{0}\pmb{v}_{0}^{*}\rangle\rv\\
&=	\min_{\mS \subset[m],  |\mS|\leq s m} \frac{\lV\lv\mA_{{\mS}^{c}}\x_{0}\rv^{2}-\lv\mA_{{\mS}^{c}}\y_{0}\rv^{2}\rV_{1}}{\mathrm{dist}_{2}\left(\x_{0},\y_{0}\right)}
-\sum_{i\in{\mS}_{1}^{c}} \lv \langle\pmb{a}_{i}\pmb{a}^{*}_{i}, \pmb{u}\pmb{v}^{*}-\pmb{u}_{0}\pmb{v}_{0}^{*}\rangle\rv.
\end{split}
\end{equation*}

Similarly, we can get

\begin{equation*}
\begin{split}
&\max_{\mS \subset[m],  |\mS|\leq s m} \frac{\lV\lv\mA_{{\mS}}\x\rv^{2}-\lv\mA_{{\mS}}\y\rv^{2}\rV_{1}}{\mathrm{dist}_{2}\left(\x,\y\right)}\\
&\le\max_{\mS \subset[m],  |\mS|\leq s m} \frac{\lV\lv\mA_{{\mS}}\x_{0}\rv^{2}-\lv\mA_{{\mS}}\y_{0}\rv^{2}\rV_{1}}{\mathrm{dist}_{2}\left(\x_{0},\y_{0}\right)}
-\sum_{i\in{\mS}_{1}} \lv \langle\pmb{a}_{i}\pmb{a}^{*}_{i}, \pmb{u}\pmb{v}^{*}-\pmb{u}_{0}\pmb{v}_{0}^{*}\rangle\rv.
\end{split}
\end{equation*}

Before presenting our final conclusion, we provide the following lemma.

For any $\pmb{u},\pmb{v}\in\mathbb{S}^{n-1}$ and $\pmb{a}_{i}\stackrel{i.i.d}{\sim}\mathcal{N}\left(0,\pmb{I}_{n}\right)$, we have

\begin{eqnarray}
\mathbb{P}\left(\frac{1}{m}\sum_{i=1}^{m}\lv \langle\pmb{a}_{i}\pmb{a}^{*}_{i}, \pmb{u}\pmb{v}^{*}\rangle\rv\ge1+\epsilon\right)\le2\exp\left[-c_{1}
\end{eqnarray}

where $K_{1}=\sqrt{8/3}$ and $c_{1}$ is a positive numerical constant.

It can be seen that $U:=\langle\pmb{a}, \pmb{u}\rangle\sim\mathcal{N}\left(0,1\right),V:=\langle\pmb{a}, \pmb{u}\rangle\sim\mathcal{N}\left(0,1\right)$.
Furthermore, $\| U\cdot V\|_{\psi_1}\le  \| U\|^{2}_{\psi_2} =\| V\|^{2}_{\psi_2} =8/3$
and by the proof Proposition <ref>.(a) in Appendix <ref>, $\mathbb{E}|U\cdot V|\le 1$. Thus, by Bernstein inequality in [36], we have reached the conclusion as
$\langle\pmb{a}\pmb{a}^{*}, \pmb{u}\pmb{v}^{*}\rangle=\langle\pmb{a}, \pmb{u}\rangle\langle\pmb{a}, \pmb{v}\rangle=U\cdot V$.

From the above two inequalities and Lemma <ref>, a unified form can be obtained that

\begin{equation*}
\begin{split}
&\min_{\mS \subset[m],|\mS|\leq s m} \frac{\lV\lv\mA_{{\mS}^{c}}\x\rv^{2}-\lv\mA_{{\mS}^{c}}\y\rv^{2}\rV_{1}-\lV\lv\mA_{{\mS}}\x\rv^{2}-\lv\mA_{{\mS}}\y\rv^{2}\rV_{1}}
&\ge\min_{\mS \subset[m],|\mS|\leq s m} \frac{\lV\lv\mA_{{\mS}^{c}}\x_{0}\rv^{2}-\lv\mA_{{\mS}^{c}}\y_{0}\rv^{2}\rV_{1}-\lV\lv\mA_{{\mS}}\x_{0}\rv^{2}-\lv\mA_{{\mS}}
\y_{0}\rv^{2}\rV_{1}}{\mathrm{dist}_{2}\left(\x_{0},\y_{0}\right)}
-\sum_{i=1}^{m} \lv \langle\pmb{a}_{i}\pmb{a}^{*}_{i}, \pmb{u}\pmb{v}^{*}-\pmb{u}_{0}\pmb{v}_{0}^{*}\rangle\rv\\
%&=&\min_{\mS \subset[m],|\mS|\leq s m} \frac{\lV\lv\mA_{{\mS}^{c}}\x_{0}\rv^{2}-\lv\mA_{{\mS}^{c}}\y_{0}\rv^{2}\rV_{1}-\lV\lv\mA_{{\mS}}\x_{0}\rv^{2}-\lv\mA_{{\mS}}\y_{0}\rv^{2}\rV_{1}}{\mathrm{dist}\left(\x_{0},\y_{0}\right)^{2}}
%&\ge&m\left[\mathcal{J}\left(s+\xi\right)-2l\xi\right]-\left(1+\delta \right)\lV\pmb{u}\pmb{v}^{*}-\pmb{u}_{0}\pmb{v}_{0}^{*}\rV_{1}\\
%	&\ge&m\left[\mathcal{J}\left(s+\xi\right)-2l_{1}\xi\right]-
%	\sum_{i=1}^{m} \lv \langle\pmb{a}_{i}\pmb{a}^{*}_{i}, \left(\pmb{u}-\pmb{u}_{0}\right)\pmb{v}^{*}-\pmb{u}_{0}
%	\left(\pmb{v}-\pmb{v}_{0}\right)^{*}\rangle\rv\\
&\ge m\left[\mathcal{J}\left(s+\xi\right)-2l_{1}\xi\right]-
\sum_{i=1}^{m} \left[\lv \langle\pmb{a}_{i}\pmb{a}^{*}_{i}, \left(\pmb{u}-\pmb{u}_{0}\right)\pmb{v}^{*}\rangle\rv+\lv \langle\pmb{a}_{i}\pmb{a}^{*}_{i}, \pmb{u}_{0}
\left(\pmb{v}-\pmb{v}_{0}\right)^{*}\rangle\rv\right]\\
&\ge m\left[\mathcal{J}\left(s+\xi\right)-2l_{1}\xi\right]-2\delta\left(1+\epsilon\right)=m\left[\mathcal{J}\left(s+\xi\right)-2l_{0}\xi\right].
\end{split}
\end{equation*}

Here, in the penultimate inequality, we use Lemma <ref> for $\lV\pmb{u}-\pmb{u}_{0}\rV\le\delta,\lV\pmb{v}-\pmb{v}_{0}\rV\le \delta$ and in the last inequality we set $l_{0}\xi=l_{1}\xi+\delta\left(1+\epsilon\right)$.

Finally, we  can finish the proof with probability at least

\begin{eqnarray*}
\begin{split}
%&\ge&1-C\left(\exp\left[ w^{2}\left(\text{cone}\left(\mathcal{K}-\mathcal{K}\right)\cap\mathbb{S}^{n-1}\right)/\delta^{2}\right]+\exp\left[w^{2}\left(\text{cone}\left(\mathcal{K}+\mathcal{K}\right)\cap\mathbb{S}^{n-1}\right)/\delta^{2}\right]\right)\cdot\mathcal{O}\left(e^{-c_{2}m\xi^{2}}\right)\\
\ge&1-C_{0} \exp\left[w^{2}\left(\text{cone}\left(\mathcal{K}\right)\cap\mathbb{S}^{n-1}\right)/\xi^{2}\right]\cdot \mathcal{O}\left(e^{-c_{2}m\xi^{2}}\right)
\end{split}
\end{eqnarray*}

provided $m\gtrsim \xi ^{-4}\cdot w^{2}\left(\text{cone}(\mathcal{K})\cap\mathbb{S}^{n-1}\right)$.

§ PROOF OF MAIN RESULTS

§.§ Recovery Guarantee for Amplitude Measurement

The proof of Theorem <ref> is based on the adversarial sparse outlier separation condition and the nonlinear ROB  condition for amplitude measurement.

By Lemma <ref> and Theorem <ref>, with probability exceeding $1-\mathcal{O}\left(e^{-cm\xi^{2}}\right)$,

\begin{eqnarray*}
\mathrm{dist}_{1}\left(\x_{\star},\x_{0}\right)\leq \frac{2}{\mathcal{M}\left(s+\xi\right)-l_{0}\xi}\frac{\lV\pmb{\omega}\rV_1}{m}.
\end{eqnarray*}

Since $\mathcal{M}\left(s\right)$ is monotonically decreasing, we have $\mathcal{M}\left(s+\xi\right)\textgreater \mathcal{M}\left(s^{*,1}-\xi\right)\textgreater 0$. Based on the proof of Theorem <ref>, the constant $l_{0}$ can be chosen small enough such that $ \mathcal{M}\left(s^{*,1}-\xi\right)\ge 2l_{0}\xi$, thus $\mathcal{M}\left(s+\xi\right)-l_{0}\xi\ge l_{0}\xi\textgreater 0$. This leads to our conclusion if we set $\widetilde{\mathcal{C}}\left(s\right)=4/\mathcal{M}\left(s^{*,1}-\xi\right)$ and provide $m \gtrsim \xi ^{-4}\cdot w^2\left(\text{cone}\left(\mathcal{K}\right)\cap \mathbb{S}^{n-1}\right)$.

The demonstration of Theorem <ref> primarily necessitates the construction of counterexamples, we now provide specific construction methods.

When $\pmb{\omega}=0$ and $\x\in \mathbb{R}^{n}$, we consider the loss function

Thus $\mathcal{L}_1\left(\x_{0}\right)=\lV\pmb{z}\rV_{1}$.

Firstly, we present the following lemma, which is a variant of Lemma <ref>.

Fix $\x,\y\in \mathbb{R}^{n}$ and let $\rho=\frac{\langle\x, \y\rangle}{\lV\x\rV_{2}\cdot\lV\y\rV_{2}}$, $\alpha=\lV\y\rV_{2}/\lV\x\rV_{2}$.
For $s \textgreater s^{*,1}$, there exists a positive numerical constant $c$ corresponding to $\tilde{l}$  such that with probability exceeding  $1-\mathcal{O}\left(e^{-cm\xi^{2}}\right)$, we have

\begin{equation}
\begin{split}
\min_{\mS \subset[m],  |\mS|\leq s m}\lV\lv\mA_{{\mS}^{c}}\pmb{x}\rv-\lv\mA_{{\mS}^{c}}\pmb{y}\rv\rV_{1}&-\lV\lv\mA_{\mS}\pmb{x}\rv-\lv\mA_{\mS}\pmb{y}\rv\rV_{1}\\
&\le m\left[M\left(\rho,\alpha, s-\xi\right)+\tilde{l}\xi/2\right]\cdot\mathrm{dist}_{1}\left(\x,\y\right).
\end{split}
\end{equation}

Secondly, let $\left(\tilde{\rho}_{1},\tilde{\alpha}\right)=\argmin M\left(\rho,\alpha,s^{*,1}\right)$,

that is $M\left(\tilde{\rho}_{1},\tilde{\alpha},s^{*,1}\right)=\mathcal{M}\left(s^{*,1}\right)=0$. Without loss of generality, let $\lV\x_{0}\rV_{2}=1$, then set

\begin{eqnarray}
\x_{\star}=\tilde{\rho}_{1}\tilde{\alpha}\x_{0}+\sqrt{1-\left(\tilde{\rho}_{1}\right)^{2}} \tilde{\alpha}\x_{0}^{\perp},
\end{eqnarray}

where $\lV\x_{0}^{\perp}\rv_{2}=1$. Thus, $\lV\x_{\star}\rV_{2}=\tilde{\alpha}$ and $\frac{\langle\x_{\star},\x_{0}\rangle}{\lV\x_{\star}\rV_{2}\cdot\lV\x_{0}\rV_{2}}=\tilde{\rho}_{1}$.

Thridly, we construct $\pmb{z}$. Let $\mS_{0}$ be the support of the largest $sm$ absolute value of entries in $\lv\mA\pmb{x}_{\star}\rv-\lv\mA\pmb{x}_{0}\rv$.
We establish the adversarial sparse outlier:

\begin{eqnarray}
\pmb{z} =  \lv\mA_{\mS_{0}}\pmb{x}_{\star}\rv-\lv\mA_{\mS_{0}}\pmb{x}_{0}\rv.
\end{eqnarray}

Thus, $\mathcal{L}_1\left(\x_{0}\right)=\lV\lv\mA_{\mS_{0}}\pmb{x}_{\star}\rv-\lv\mA_{\mS_{0}}\pmb{x}_{0}\rv\rV_{1}$ and

Finally, as $s-2\xi\textgreater s^{1,*}$, there exists $\tilde{l}\textgreater0$ such that

$$M\left(\tilde{\rho}_{1},\tilde{\alpha}, s-\xi\right)\textless M\left(\tilde{\rho}_{1},\tilde{\alpha}, s^{*,1}+\xi\right)=-\tilde{l}\xi.$$

By Lemma <ref>

, we have

\begin{equation*}
\begin{split}
\mathcal{L}_1\left(\x_{\star}\right)-\mathcal{L}_1\left(\x_{0}\right)&=
\lV\lv\mA_{\mS_{0}^{c}}\x_{\star}\rv-\lv\mA_{\mS_{0}^{c}}\x_{0}\rv\rV_{1}-
\lV\lv\mA_{\mS_{0}}\x_{\star}\rv-\lv\mA_{\mS_{0}}\x_{0}\rv\rV_{1}\\
&=\min_{\mS \subset[m],  |\mS|\leq s m}
\lV\lv\mA_{{\mS}^{c}}\x_{\star}\rv-\lv\mA_{{\mS}^{c}}\x_{0}\rv\rV_{1}-
\lV\lv\mA_{{\mS}}\x_{\star}\rv-\lv\mA_{{\mS}}\x_{0}\rv\rV_{1}\\
%&\leq&m\left[M_{1}\left(\tilde{\rho}_{1},\tilde{\alpha}, s-\xi\right)-M_{2}\left(\tilde{\rho}_{1},\tilde{\alpha}, s-\xi\right)+\tilde{l}\xi/2\right]\cdot \mathrm{dist}_{1}\left(\x_{\star},\x_{0}\right)\\
&\le m\left[M\left(\tilde{\rho}_{1},\tilde{\alpha}, s^{*,1}+\xi\right)+\tilde{l}\xi/2\right]\cdot \mathrm{dist}_{1}\left(\x_{\star},\x_{0}\right) \\
\end{split}
\end{equation*}

with probability exceeding  $1-\mathcal{O}\left(e^{-cm\xi^{2}}\right)$.

§.§ Recovery Guarantee for Intensity Measurement

The proofs of Theorem <ref> and Theorem <ref> are similar to the amplitude case.

By Lemma <ref> and Theorem <ref>, with probability exceeding $1-\mathcal{O}\left(e^{-cm\xi^{2}}\right)$,

\begin{eqnarray*}
\mathrm{dist}_{2}\left(\x_{\star},\x_{0}\right)\leq \frac{2}{\mathcal{J}(s+\xi)-l_{0}\xi}\frac{\lV\pmb{\omega}\rV_1}{m}.
\end{eqnarray*}

$\mathcal{J}\left(s\right)$ is monotonically decreasing, then we have $\mathcal{J}\left(s+\xi\right)\textgreater \mathcal{J}\left(s^{*,2}-\xi\right)\textgreater 0$.
The constant $l_{0}$ can be chosen small enough to make $ \mathcal{J}\left(s^{*,2}-\xi\right)\ge 2l_{0}\xi$, thus $\mathcal{J}\left(s+\xi\right)-l_{0}\xi\ge l_{0}\xi\textgreater 0$.
If $m \gtrsim \xi ^{-4}\cdot w^2\left(\text{cone}\left(\mathcal{K}\right)\cap \mathbb{S}^{n-1}\right)$ and $\widetilde{\mathcal{C}}\left(s\right)=4/\mathcal{J}\left(s^{*,2}-\xi\right)$, we then can finish the proof.

Let $\mathcal{L}_2\left(\x\right)=\lV\lv\mA\x\rv-\lv\mA\x_{0}\rv^{2}-\pmb{z}\rV_{1}$.
And set $\tilde{\rho}_{2}=\argmin J\left(\rho,s^{*,2}\right)$, thus $J\left(\tilde{\rho}_{2},s^{*,2}\right)=\mathcal{J}\left(s^{*,2}\right)=0$.
Then let $\x_{\star}$ be the vector that satisfies $\tilde{\rho}_{2}=\langle\frac{\x_{0}-\x_{\star}}{\lV\x_{0}-\x_{\star}\rV_{2}},\frac{\x_{0}+\x_{\star}}{\lV\x_{0}+\x_{\star}\rV_{2}}\rangle$.
Set $\mS_{0}$ be the support of the largest $sm$ absolute value of entries in $\lv\mA\pmb{x}_{\star}\rv^{2}-\lv\mA\pmb{x}_{0}\rv^{2}$.
Then the adversarial sparse outlier we construct here is

\begin{eqnarray}
\pmb{z} =  \lv\mA_{\mS_{0}}\pmb{x}_{\star}\rv^{2}-\lv\mA_{\mS_{0}}\pmb{x}_{0}\rv^{2}.
\end{eqnarray}

We next provide the following lemma, which is similar to Lemma <ref>.

Fix $\x,\y\in \mathbb{R}^{n}$ and let $\rho=\langle\frac{\x-\y}{\lV\x-\y\rV_{2}},\frac{\x+\y}{\lV\x+\y\rV_{2}}\rangle$.
For $s \textgreater s^{*,2}$, there exists a positive numerical constant $c$ corresponding to $\tilde{l}$ such that with probability at least $1-\mathcal{O}\left(e^{-cm\xi^{2}}\right)$,

\begin{equation*}
\begin{split}
\min_{\mS \subset[m],  |\mS|\leq s m}\lV\lv\mA_{{\mS}^{c}}\pmb{x}\rv^{2}-\lv\mA_{{\mS}^{c}}\pmb{y}\rv^{2}\rV_{1}&-\lV\lv\mA_{\mS}\pmb{x}\rv^{2}-\lv\mA_{\mS}\pmb{y}\rv^{2}\rV_{1}\\
&\leq m\left[J\left(\rho, s-\xi\right)+\tilde{l}\xi/2\right]\cdot\mathrm{dist}_{2}\left(\x,\y\right).
\end{split}
\end{equation*}

Finally, there exists $\tilde{l} \textgreater0$ such that $J\left(\tilde{\rho}_{2},s-\xi\right)\textless J\left(\tilde{\rho}_{2},s^{*,2}+\xi\right)=-l\xi$,

thus by Lemma <ref> , we have

\begin{equation*}
\begin{split}
\mathcal{L}_{2}\left(\x_{\star}\right)-\mathcal{L}_{2}\left(\x_{0}\right)&=
\lV\lv\mA_{\mS_{0}^{c}}\x_{\star}\rv^{2}-\lv\mA_{\mS_{0}^{c}}\x_{0}\rv^{2}\rV_{1}-
\lV\lv\mA_{\mS_{0}}\x_{\star}\rv^{2}-\lv\mA_{\mS_{0}}\x_{0}\rv^{2}\rV_{1}\\
&=\min_{\mS \subset[m],  |\mS|\leq s m}
\lV\lv\mA_{{\mS}^{c}}\x_{\star}\rv^{2}-\lv\mA_{{\mS}^{c}}\x_{0}\rv^{2}\rV_{1}-
\lV\lv\mA_{{\mS}}\x_{\star}\rv^{2}-\lv\mA_{{\mS}}\x_{0}\rv^{2}\rV_{1}\\
%&\le m\left[J_{1}\left(\tilde{\rho}_{2}, s-\xi\right)-J_{2}\left(\tilde{\rho}_{2}, s-\xi\right)+\tilde{l}\xi/2\right]\cdot\mathrm{dist}^{2}\left(\x_{\star},\x_{0}\right)\\
&\le m\left[J\left(\tilde{\rho}_{2}, s^{*,2}+\xi\right)+l\xi/2\right]\cdot\mathrm{dist}_{2}\left(\x_{\star},\x_{0}\right) \\
\end{split}
\end{equation*}

with probability exceeding $1-\mathcal{O}\left(e^{-cm\xi^{2}}\right)$.

§ NUMERICAL EXPERIMENTS FOR SHARP THRESHOLDS

In this section, we conduct experiments to study the fraction of sparse outliers that the two nonlinear LAD model can tolerate even when the sample size is very large.
For simplicity, we do not take into account the dense noise, i.e., $\pmb{\omega} = \pmb{0}$. We let the ground-truth $\pmb{x}_0 \in \mathbb{R}^{5}$ be a standard Gaussian vector and the adversarial sparse outliers are selected following from the counterexamples in the proof of Theorem <ref> and Theorem <ref>. We choose the sample size $m = 500n$ and the entries of the sample vectors $\{\pmb{a}_i\}_i$ are i.i.d. drawn from $\mathcal{N}\left(0, \pmb{I}_{n}\right)$. We plot the relative error $\frac{\| \x-\x_0\|_2}{\|\x\|_2}$ with the fraction of sparse noise ranging from $0$ to $1$ in Figure <ref>. We can observe that it can tolerate no more than an $s^{*,1}\approx 0.2043$ fraction of corruptions in amplitude-based LAD and $s^{*,2}\approx 0.1185$ in intensity-based LAD. It also is clear that amplitude-based LAD is more robust than  intensity-based LAD.
These meet our results in the preceding article.

*(b) The recovery threshold for nonlinear LAD based on amplitude measurement.

*(a) The recovery threshold for nonlinear LAD based on intensity measurement.

The threshold $s$ for amplitude-based and intensity-based nonlinear LAD model.

§ APPENDIX

§ DVORETZKY-KIEFER-WOLFOWITZ TYPE INEQUALITY

The following lemma is a corollary of the standard Dvoretzky-Kiefer-Wolfowitz inequality, similar proof can be found in [21, 40].

Let $\Gamma=\{ \xi_1, \dots, \xi_m\}$ be i.i.d. sampled from any continuous distribution function $F$ on $\mathbb{R}$. Then for any $\eta, \epsilon \in [0, 1]$, the following holds with probability at least $1 - 4e^{-2m\epsilon^2}$,

\begin{eqnarray*}
F^{-1}\left(\eta- \epsilon\right) < \widehat{F}^{-1}(\eta) < F^{-1}\left(\eta+ \epsilon\right).
\end{eqnarray*}

Here, $\widehat{F}$ is the associated empirical distribution function defined by $\widehat{F}\left(x\right) = {1\over m} \sum_{i=1}^m\mathbbm{1}_{\xi_i \leq x}$.

Standard Dvoretzky-Kiefer-Wolfowitz inequality [26] stated that

\begin{eqnarray*}
\mathbb{P}\left(\sqrt{m}\sup_{x}\lv\widehat{F}\left(x\right)-F\left(x\right)\rv\ge\lambda\right)\le2\exp\left(-2\lambda^{2}\right).
\end{eqnarray*}

Set $x=F^{-1}\left(\eta- \epsilon\right)$ and $\lambda=\epsilon\sqrt{m}$, then

\begin{eqnarray*}
\mathbb{P}\left(\lv\widehat{F}\left(t\right)-\left(\eta-\epsilon\right)\rv\ge\epsilon\right)\le2\exp\left(-2m\epsilon^{2}\right).
\end{eqnarray*}

Then we have

\begin{eqnarray*}
\mathbb{P}\left(\widehat{F}\left(t\right)\le\eta\right)\ge1-2\exp\left(-2m\epsilon^{2}\right).
\end{eqnarray*}

Monotonicity of  $\widehat{F}\left(x\right) $ then implies the left-side inequality. The right-side inequality follows similarly.

§ PDF OF $\LV Z_{\RHO}\RV=\LV X\CDOT Y\RV$

We first consider the PDF of $Z_{\rho}=X\cdot Y$.

We define the parametric integral as follows:

\begin{eqnarray*}
I_{\alpha,\beta}\left(t\right)=\int_{-\infty}^{\infty}\frac{e^{{\rm i}xt}}{\sqrt{\left(x-{\rm i}\alpha\right)\left(x+{\rm i}\beta\right)}} dx,
\end{eqnarray*}

where ${\rm i}=\sqrt{-1}, a>0,b>0 $ and $-\infty <t<\infty$ are fixed real numbers. Setting $x=y+\frac{{\rm i}}{2}\left(\alpha-\beta\right)$ in $I_{\alpha,\beta}\left(t\right)$, we then obtain

\begin{eqnarray*}
I_{\alpha,\beta}\left(t\right)&=&e^{\frac{\beta-\alpha}{2}t}\int_{-\infty}^{\infty}\frac{e^{{\rm i}ty}}{\sqrt{y^{2}+(\frac{\beta+\alpha}{2})^{2}}}dy\\
=2e^{\frac{\beta-\alpha}{2}t}K_{0}\left(\frac{\beta+\alpha}{2}\lv t\rv\right),\\
\end{eqnarray*}

where the  last step stems from the definition of Bessel function of the second kind of order zero $K_{0}\left(x\right)$. Meanwhile, from [8], the characteristic function of $Z_{\rho}=X\cdot Y$ is

\begin{eqnarray*}
\mathbb{E}e^{{\rm i}tZ}=\frac{1}{\sqrt{\left(1-{\rm i}\left(1+\rho\right)t\right)\left(1+{\rm i}\left(1+\rho\right)t\right)}}.
\end{eqnarray*}

Hence, by the inversion theorem, the PDF of $Z_{\rho}$ can be expressed as

\begin{eqnarray*}\label{rv2}
&=&\frac{1}{2\pi}\int_{-\infty}^{\infty}\frac{e^{-{\rm i}tz}}{\sqrt{\left(1-{\rm i}\left(1+\rho\right)t\right)\left(1+{\rm i}\left(1+\rho\right)t\right)}}dt\\
&=&\frac{1}{2\pi\sqrt{1-\rho^{2}}}\int_{-\infty}^{\infty}\frac{e^{-{\rm i}tz}}{\sqrt{\left(t-\frac{1}{{\rm i}\left(1+\rho\right)}\right)\left(t+\frac{1}{{\rm i}\left(1+\rho\right)}\right)}}dt
=\frac{1}{\pi\sqrt{1-\rho^2}}e^{ \frac{\rho z}{1-\rho^2}}K_0\left( \frac{\lv z\rv}{1-\rho^2} \right).
\end{eqnarray*}

Actually when $\rho \to \pm 1$, the variable $Z_{\rho}= X\cdot Y$ converges in distribution to chi-square random variable $\chi^2\left(1\right)$ or $-\chi^2\left(1\right)$.
Finally, due to $f_{\rho}\left(z\right)=f_{Z_{\rho}}\left(z\right)+f_{Z_{\rho}}\left(-z\right)$ we finish the proof.

§ PARTIAL PROOFS OF NONLINEAR ROB CONDITION

§.§ Proof of Proposition <ref>

The expectation of $\lv Z_{\rho}\rv$ derived from [18] is

\begin{eqnarray*}
\mathbb{E}\left[\lv Z_{\rho}\rv\right]=\frac{2}{\pi}\left[\sqrt{1-\rho^{2}}+\rho\arcsin(\rho)\right].
\end{eqnarray*}

By definition, $\mathcal{J}\left(0\right)=\min\limits_{\rho \in[0,1]}\mathbb{E}\left[\lv Z_{\rho}\rv \right]$ and $\mathcal{J}\left(1\right)=-\max\limits_{\rho \in[0,1]}\mathbb{E}\left[\lv Z_{\rho}\rv\right]$.

\begin{eqnarray*}
\phi \left(\rho\right)=\sqrt{1-\rho^{2}}+\rho\arcsin\left(\rho\right).
\end{eqnarray*}

Then, by calculation $ \frac{\partial \phi}{\partial\rho} =  \arcsin\left(\rho\right) \geq 0.$
Thus we can get

\begin{eqnarray*}
\mathcal{J}\left(0\right)=\frac{2}{\pi}\phi \left(0\right)=\frac{2}{\pi}\quad\text{and}\quad\mathcal{J}\left(1\right)=-\frac{2}{\pi}\phi \left(1\right)=-1.
\end{eqnarray*}

The continuity of $\mathcal{J}\left(s\right)$ is obvious. For monotonicity, let $0\le s_{1} \textless s_{2} \le1$ and $\rho_{1} = \arg\min \mathcal{J}\left(s_{1}\right)$, $\rho_{2} = \arg\min \mathcal{J}\left(s_{2}\right)$.
By definition,

\begin{eqnarray*}
\mathcal{J}\left(s_{1}\right)=J\left(\rho_{1},s_{1}\right)\textgreater J\left(\rho_{1},s_{2}\right)\ge J\left(\rho_{2},s_{2}\right)=\mathcal{J}\left(s_{2}\right).
\end{eqnarray*}

As $\mathcal{J}\left(0\right)$ and $ \mathcal{J}\left(1\right)$ are finite, $\mathcal{J}\left(s\right)$ is a well-defined function.

The uniqueness of zero can be derived by Proposition <ref>.(a).
The calculation of $s^{*,2}$ has been given in [18].
Though our minimum balance function $\mathcal{J}\left(s\right)$ is different from that in [18], the difference is only the coefficient of $\rho$, which does not affect the value of $s^{*,2}$.

§.§ Proof of Lemma <ref>

Let $h_{1}\left(x\right) = x \cdot \mathbbm{1}_{[0,t]}\left(x\right)$, and $\Gamma \left(t\right) = h_{1}\left(\lvert Z_{\rho}\rvert\right)$.
Similar to Step 2 in Theorem <ref>, we can derive that for all $\rho\in\left[0,1\right]$ and $t\in \mathbb{R}^{+}\cup \{+\infty\}$,
there exists $ K_{0}>0$ such that $	\lV\Gamma\left(t\right) \rV_{\psi_{1}} \leq K_{0}$. Let $r\textgreater s\in (0,1)$ be a fixed constant and $t = F_{\rho}^{-1}\left(1-r\right)$.
We consider the sampling set $\Gamma=\{\Gamma_{1}\left(t\right),\cdots,\Gamma_{m}\left(t\right)\}$ and get

\begin{eqnarray*}
\mathbb{E}\left[\Gamma \left(t\right)\right]=\int_{0 }^{t}
zf_{\rho }\left(z\right)dz=J_{1}\left(\rho,r\right).
\end{eqnarray*}

Thus by Bernstein inequality in [36], we have

\begin{eqnarray}\label{X1}
\mathbb{P}\left(\lv {1\over m} \sum_{i=1}^m \Gamma_i\left(t\right) - \mathbb{E}\left(\Gamma \left[t\right)\right] \rv >\varepsilon_1\right) \leq 2e^{-c_{0}m\min\left\{\varepsilon_1^2/K_{0}^{2},\varepsilon_1/K_{0}\right\}}.
\end{eqnarray}

Based on Dvoretzky-Kiefer-Wolfowitz type inequality in Lemma <ref> and similar to the argument in Step 2 of Theorem <ref>, we can get

\begin{eqnarray}\label{X2}
\min_{\mS \subset[m],  |\mS|\leq s m}\frac{\lV\lv\mA_{{\mS}^{c}}\pmb{x}\rv^{2}-\lv\mA_{{\mS}^{c}}\pmb{y}\rv^{2}\rV_{1}}{\mathrm{dist}_{2}\left(\x,\y\right)}
\ge \sum_{i=1}^m \Gamma_i\left(t\right)
\end{eqnarray}

with probability  exceeding $1 - 4e^{-2m\left(r-s\right)^2}$.
Combining (<ref>) with (<ref>), we get

\begin{eqnarray*}
\frac{1}{m}\min_{\mS \subset[m],  |\mS|\leq s m}\frac{\lV\lv\mA_{{\mS}^{c}}\pmb{x}\rv^{2}-\lv\mA_{{\mS}^{c}}\pmb{y}\rv^{2}\rV_{1}}{\mathrm{dist}_{2}\left(\x,\y\right)}
\ge \frac{1}{m}\sum_{i=1}^m  \Gamma_i\left(t\right) \ge \mathbb{E}\left[\Gamma \left(t\right)\right] - \varepsilon_1 = J_{1}\left(\rho,s+\epsilon\right)-\varepsilon_1
\end{eqnarray*}

with certain probability.
By setting $\epsilon =\xi$ and $\varepsilon_1= l_{1}\xi$ for small enough $l_{1}$ such that $\varepsilon_1^{2}/K_{0}^{2}\le\varepsilon_1/K_{0}$, we finally get (<ref>) with probability  at least $1 -\mathcal{O}(e^{-c_{1}m\xi^{2}})$.
Similarly, we can establish (<ref>) if we
set $h_{2}\left(x\right) = x\cdot \mathbbm{1}_{\left[t,+\infty\right)}\left(x\right)$ and $\Gamma \left(t\right)=h_{2}\left(\lv Z_{\rho}\rv\right)$.

[1]
Radu Balan, Bernhard G Bodmann, Peter G Casazza, and Dan Edidin.
Painless reconstruction from magnitudes of frame coefficients.
Journal of Fourier Analysis and Applications, 15(4):488–501, 2009.

[2]
Afonso S Bandeira, Jameson Cahill, Dustin G Mixon, and Aaron A Nelson.
Saving phase: Injectivity and stability for phase retrieval.
Applied and Computational Harmonic Analysis, 37(1):106–125, 2014.

[3]
Emmanuel J Candès, Xiaodong Li, and Mahdi Soltanolkotabi.
Phase retrieval via Wirtinger flow: Theory and algorithms.
IEEE Transactions on Information Theory, 61(4):1985–2007, 2015.

[4]
Emmanuel J Candès, Thomas Strohmer, and Vladislav Voroninski.
Phaselift: Exact and stable signal recovery from magnitude measurements via convex programming.
Communications on Pure and Applied Mathematics, 66(8):1241–1274, 2013.

[5]
Anwei Chai, Miguel Moscoso, and George Papanicolaou.
Array imaging using intensity-only measurements.
Inverse Problems, 27(1):015005, 2010.

[6]
Yudong Chen, Constantine Caramanis, and Shie Mannor.
Robust sparse regression under adversarial corruption.
In International Conference on Machine Learning, pages 774–782. PMLR, 2013.

[7]
Yuxin Chen and Emmanuel J Candès.
Solving random quadratic systems of equations is nearly as easy as solving linear systems.
Communications on Pure and Applied Mathematics, 70(5):822–883, 2017.

[8]
Cecil C Craig.
On the frequency function of xy.
The Annals of Mathematical Statistics, 7(1):1–15, 1936.

[9]
Fernando De La Torre and Michael J Black.
A framework for robust subspace learning.
International Journal of Computer Vision, 54:117–142, 2003.

[10]
Ilias Diakonikolas, Daniel Kane, Ankit Pensia, and Thanasis Pittas.
Nearly-linear time and streaming algorithms for outlier-robust pca.
In International Conference on Machine Learning, pages 7886–7921. PMLR, 2023.

[11]
Ilias Diakonikolas, Weihao Kong, and Alistair Stewart.
Efficient algorithms and lower bounds for robust linear regression.
In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2745–2754. SIAM, 2019.

[12]
John C Duchi and Feng Ruan.
Solving (most) of a set of quadratic equalities: Composite optimization for robust phase retrieval.
Information and Inference: A Journal of the IMA, 8(3):471–529, 2019.

[13]
Cynthia Dwork, Frank McSherry, and Kunal Talwar.
The price of privacy and the limits of LP decoding.
In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 85–94, 2007.

[14]
Yonina C Eldar and Shahar Mendelson.
Phase retrieval: Stability and recovery guarantees.
Applied and Computational Harmonic Analysis, 36(3):473–494, 2014.

[15]
C Fienup and J Dainty.
Phase retrieval and image reconstruction for astronomy.
Image Recovery: Theory and Application, 231:275, 1987.

[16]
Izrail Solomonovich Gradshteyn and Iosif Moiseevich Ryzhik.
Table of Integrals, Series, and Products.
Academic Press, 2014.

[17]
Paul Hand.
Phaselift is robust to a constant fraction of arbitrary errors.
Applied and Computational Harmonic Analysis, 42(3):550–562, 2017.

[18]
Gao Huang, Song Li, and Hang Xu.
Robust outlier bound condition to phase retrieval with adversarial sparse outliers.
arXiv preprint arXiv:2311.13219, 2023.

[19]
Meng Huang and Zhiqiang Xu.
Performance bounds of the intensity-based estimators for noisy phase retrieval.
Applied and Computational Harmonic Analysis, 68:101584, 2024.

[20]
Armin Kappeler, Sushobhan Ghosh, Jason Holloway, Oliver Cossairt, and Aggelos Katsaggelos.
Ptychnet: Cnn based fourier ptychography.
In 2017 IEEE International Conference on Image Processing (ICIP), pages 1712–1716. IEEE, 2017.

[21]
Sushrut Karmalkar and Eric Price.
Compressed sensing with adversarial sparse noise via $\ell_{1}$ regression.
In Symposium on Simplicity in Algorithms, 2019.

[22]
Adam Klivans, Pravesh K Kothari, and Raghu Meka.
Efficient algorithms for outlier-robust regression.
In Conference On Learning Theory, pages 1420–1430. PMLR, 2018.

[23]
Liyuan Li, Weimin Huang, Irene Yu-Hua Gu, and Qi Tian.
Statistical modeling of complex backgrounds for foreground object detection.
IEEE Transactions on Image Processing, 13(11):1459–1472, 2004.

[24]
Xiaodong Li.
Compressed sensing and matrix completion with constant proportion of corruptions.
Constructive Approximation, 37:73–99, 2013.

[25]
Yuanxin Li, Yue Sun, and Yuejie Chi.
Low-rank positive semidefinite matrix recovery from corrupted rank-one measurements.
IEEE Transactions on Signal Processing, 65(2):397–408, 2016.

[26]
Pascal Massart.
The tight constant in the dvoretzky-kiefer-wolfowitz inequality.
The Annals of Probability, pages 1269–1283, 1990.

[27]
Christopher Metzler, Phillip Schniter, Ashok Veeraraghavan, and Richard Baraniuk.
prdeep: Robust phase retrieval with a flexible deep network.
In International Conference on Machine Learning, pages 3501–3510. PMLR, 2018.

[28]
Jianwei Miao, Pambos Charalambous, Janos Kirz, and David Sayre.
Extending the methodology of X-ray crystallography to allow imaging of micrometre-sized non-crystalline specimens.
Nature, 400(6742):342–344, 1999.

[29]
Jianwei Miao, Tetsuya Ishikawa, Qun Shen, and Thomas Earnest.
Extending X-ray crystallography to allow the imaging of noncrystalline materials, cells, and single protein complexes.
Annual Review of Physical Chemistry, 59:387–410, 2008.

[30]
Rick P Millane.
Phase retrieval in crystallography and optics.
Journal of the Optical Society of America A, 7(3):394–411, 1990.

[31]
Daniel L Pimentel-Alarcón, Aritra Biswas, and Claudia R Solís-Lemus.
Adversarial principal component analysis.
In 2017 IEEE International Symposium on Information Theory (ISIT), pages 2363–2367. IEEE, 2017.

[32]
Stelios Psarakis and John Panaretos.
On some bivariate extensions of the folded normal and the folded-t distributions.
Journal of Applied Statistical Science, 10(2):119–136, 2001.

[33]
Yoav Shechtman, Yonina C Eldar, Oren Cohen, Henry Nicholas Chapman, Jianwei Miao, and Mordechai Segev.
Phase retrieval with application to optical imaging: A contemporary overview.
IEEE Signal Processing Magazine, 32(3):87–109, 2015.

[34]
Mahdi Soltanolkotabi.
Structured signal recovery from quadratic measurements: Breaking sample complexity barriers via nonconvex optimization.
IEEE Transactions on Information Theory, 65(4):2374–2400, 2019.

[35]
Michel Talagrand.
The Generic Chaining: Upper and Lower Bounds of Stochastic Processes.
Springer Science and Business Media, 2005.

[36]
Roman Vershynin.
High-Dimensional Probability: An Introduction with Applications in Data Science, volume 47.
Cambridge University Press, 2018.

[37]
Adriaan Walther.
The question of phase retrieval in optics.
Optica Acta: International Journal of Optics, 10(1):41–49, 1963.

[38]
Gang Wang, Georgios B Giannakis, and Yonina C Eldar.
Solving systems of random quadratic equations via truncated amplitude flow.
IEEE Transactions on Information Theory, 64(2):773–794, 2017.

[39]
Daniel S Weller, Ayelet Pnueli, Gilad Divon, Ori Radzyner, Yonina C Eldar, and Jeffrey A Fessler.
Undersampled phase retrieval with outliers.
IEEE Transactions on Computational Imaging, 1(4):247–258, 2015.

[40]
Hang Xu, Song Li, and Junhong Lin.
Low rank matrix recovery with adversarial sparse noise.
Inverse Problems, 38(3):035001, 2022.

[41]
Li-Hao Yeh, Jonathan Dong, Jingshan Zhong, Lei Tian, Michael Chen, Gongguo Tang, Mahdi Soltanolkotabi, and Laura Waller.
Experimental robustness of fourier ptychography phase retrieval algorithms.
Optics Express, 23(26):33214–33240, 2015.

[42]
Huishuai Zhang, Yuejie Chi, and Yingbin Liang.
Median-truncated nonconvex approach for phase retrieval with outliers.
IEEE Transactions on Information Theory, 64(11):7287–7310, 2018.

[43]
Huishuai Zhang, Yi Zhou, Yingbin Liang, and Yuejie Chi.
A nonconvex approach for phase retrieval: Reshaped wirtinger flow and incremental algorithms.
Journal of Machine Learning Research, 18, 2017.

[44]
Shuheng Zhou, John Lafferty, and Larry Wasserman.
Compressed and privacy-sensitive sparse regression.
IEEE Transactions on Information Theory, 55(2):846–866, 2009.

[1]
Radu Balan, Bernhard G Bodmann, Peter G Casazza, and Dan Edidin.
Painless reconstruction from magnitudes of frame coefficients.
Journal of Fourier Analysis and Applications, 15(4):488–501, 2009.

[2]
Afonso S Bandeira, Jameson Cahill, Dustin G Mixon, and Aaron A Nelson.
Saving phase: Injectivity and stability for phase retrieval.
Applied and Computational Harmonic Analysis, 37(1):106–125, 2014.

[3]
Emmanuel J Candès, Xiaodong Li, and Mahdi Soltanolkotabi.
Phase retrieval via Wirtinger flow: Theory and algorithms.
IEEE Transactions on Information Theory, 61(4):1985–2007, 2015.

[4]
Emmanuel J Candès, Thomas Strohmer, and Vladislav Voroninski.
Phaselift: Exact and stable signal recovery from magnitude measurements via convex programming.
Communications on Pure and Applied Mathematics, 66(8):1241–1274, 2013.

[5]
Anwei Chai, Miguel Moscoso, and George Papanicolaou.
Array imaging using intensity-only measurements.
Inverse Problems, 27(1):015005, 2010.

[6]
Yudong Chen, Constantine Caramanis, and Shie Mannor.
Robust sparse regression under adversarial corruption.
In International Conference on Machine Learning, pages 774–782. PMLR, 2013.

[7]
Yuxin Chen and Emmanuel J Candès.
Solving random quadratic systems of equations is nearly as easy as solving linear systems.
Communications on Pure and Applied Mathematics, 70(5):822–883, 2017.

[8]
Cecil C Craig.
On the frequency function of xy.
The Annals of Mathematical Statistics, 7(1):1–15, 1936.

[9]
Fernando De La Torre and Michael J Black.
A framework for robust subspace learning.
International Journal of Computer Vision, 54:117–142, 2003.

[10]
Ilias Diakonikolas, Daniel Kane, Ankit Pensia, and Thanasis Pittas.
Nearly-linear time and streaming algorithms for outlier-robust pca.
In International Conference on Machine Learning, pages 7886–7921. PMLR, 2023.

[11]
Ilias Diakonikolas, Weihao Kong, and Alistair Stewart.
Efficient algorithms and lower bounds for robust linear regression.
In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2745–2754. SIAM, 2019.

[12]
John C Duchi and Feng Ruan.
Solving (most) of a set of quadratic equalities: Composite optimization for robust phase retrieval.
Information and Inference: A Journal of the IMA, 8(3):471–529, 2019.

[13]
Cynthia Dwork, Frank McSherry, and Kunal Talwar.
The price of privacy and the limits of LP decoding.
In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 85–94, 2007.

[14]
Yonina C Eldar and Shahar Mendelson.
Phase retrieval: Stability and recovery guarantees.
Applied and Computational Harmonic Analysis, 36(3):473–494, 2014.

[15]
C Fienup and J Dainty.
Phase retrieval and image reconstruction for astronomy.
Image Recovery: Theory and Application, 231:275, 1987.

[16]
Izrail Solomonovich Gradshteyn and Iosif Moiseevich Ryzhik.
Table of Integrals, Series, and Products.
Academic Press, 2014.

[17]
Paul Hand.
Phaselift is robust to a constant fraction of arbitrary errors.
Applied and Computational Harmonic Analysis, 42(3):550–562, 2017.

[18]
Gao Huang, Song Li, and Hang Xu.
Robust outlier bound condition to phase retrieval with adversarial sparse outliers.
arXiv preprint arXiv:2311.13219, 2023.

[19]
Meng Huang and Zhiqiang Xu.
Performance bounds of the intensity-based estimators for noisy phase retrieval.
Applied and Computational Harmonic Analysis, 68:101584, 2024.

[20]
Armin Kappeler, Sushobhan Ghosh, Jason Holloway, Oliver Cossairt, and Aggelos Katsaggelos.
Ptychnet: Cnn based fourier ptychography.
In 2017 IEEE International Conference on Image Processing (ICIP), pages 1712–1716. IEEE, 2017.

[21]
Sushrut Karmalkar and Eric Price.
Compressed sensing with adversarial sparse noise via $\ell_{1}$ regression.
In Symposium on Simplicity in Algorithms, 2019.

[22]
Adam Klivans, Pravesh K Kothari, and Raghu Meka.
Efficient algorithms for outlier-robust regression.
In Conference On Learning Theory, pages 1420–1430. PMLR, 2018.

[23]
Liyuan Li, Weimin Huang, Irene Yu-Hua Gu, and Qi Tian.
Statistical modeling of complex backgrounds for foreground object detection.
IEEE Transactions on Image Processing, 13(11):1459–1472, 2004.

[24]
Xiaodong Li.
Compressed sensing and matrix completion with constant proportion of corruptions.
Constructive Approximation, 37:73–99, 2013.

[25]
Yuanxin Li, Yue Sun, and Yuejie Chi.
Low-rank positive semidefinite matrix recovery from corrupted rank-one measurements.
IEEE Transactions on Signal Processing, 65(2):397–408, 2016.

[26]
Pascal Massart.
The tight constant in the dvoretzky-kiefer-wolfowitz inequality.
The Annals of Probability, pages 1269–1283, 1990.

[27]
Christopher Metzler, Phillip Schniter, Ashok Veeraraghavan, and Richard Baraniuk.
prdeep: Robust phase retrieval with a flexible deep network.
In International Conference on Machine Learning, pages 3501–3510. PMLR, 2018.

[28]
Jianwei Miao, Pambos Charalambous, Janos Kirz, and David Sayre.
Extending the methodology of X-ray crystallography to allow imaging of micrometre-sized non-crystalline specimens.
Nature, 400(6742):342–344, 1999.

[29]
Jianwei Miao, Tetsuya Ishikawa, Qun Shen, and Thomas Earnest.
Extending X-ray crystallography to allow the imaging of noncrystalline materials, cells, and single protein complexes.
Annual Review of Physical Chemistry, 59:387–410, 2008.

[30]
Rick P Millane.
Phase retrieval in crystallography and optics.
Journal of the Optical Society of America A, 7(3):394–411, 1990.

[31]
Daniel L Pimentel-Alarcón, Aritra Biswas, and Claudia R Solís-Lemus.
Adversarial principal component analysis.
In 2017 IEEE International Symposium on Information Theory (ISIT), pages 2363–2367. IEEE, 2017.

[32]
Stelios Psarakis and John Panaretos.
On some bivariate extensions of the folded normal and the folded-t distributions.
Journal of Applied Statistical Science, 10(2):119–136, 2001.

[33]
Yoav Shechtman, Yonina C Eldar, Oren Cohen, Henry Nicholas Chapman, Jianwei Miao, and Mordechai Segev.
Phase retrieval with application to optical imaging: A contemporary overview.
IEEE Signal Processing Magazine, 32(3):87–109, 2015.

[34]
Mahdi Soltanolkotabi.
Structured signal recovery from quadratic measurements: Breaking sample complexity barriers via nonconvex optimization.
IEEE Transactions on Information Theory, 65(4):2374–2400, 2019.

[35]
Michel Talagrand.
The Generic Chaining: Upper and Lower Bounds of Stochastic Processes.
Springer Science and Business Media, 2005.

[36]
Roman Vershynin.
High-Dimensional Probability: An Introduction with Applications in Data Science, volume 47.
Cambridge University Press, 2018.

[37]
Adriaan Walther.
The question of phase retrieval in optics.
Optica Acta: International Journal of Optics, 10(1):41–49, 1963.

[38]
Gang Wang, Georgios B Giannakis, and Yonina C Eldar.
Solving systems of random quadratic equations via truncated amplitude flow.
IEEE Transactions on Information Theory, 64(2):773–794, 2017.

[39]
Daniel S Weller, Ayelet Pnueli, Gilad Divon, Ori Radzyner, Yonina C Eldar, and Jeffrey A Fessler.
Undersampled phase retrieval with outliers.
IEEE Transactions on Computational Imaging, 1(4):247–258, 2015.

[40]
Hang Xu, Song Li, and Junhong Lin.
Low rank matrix recovery with adversarial sparse noise.
Inverse Problems, 38(3):035001, 2022.

[41]
Li-Hao Yeh, Jonathan Dong, Jingshan Zhong, Lei Tian, Michael Chen, Gongguo Tang, Mahdi Soltanolkotabi, and Laura Waller.
Experimental robustness of fourier ptychography phase retrieval algorithms.
Optics Express, 23(26):33214–33240, 2015.

[42]
Huishuai Zhang, Yuejie Chi, and Yingbin Liang.
Median-truncated nonconvex approach for phase retrieval with outliers.
IEEE Transactions on Information Theory, 64(11):7287–7310, 2018.

[43]
Huishuai Zhang, Yi Zhou, Yingbin Liang, and Yuejie Chi.
A nonconvex approach for phase retrieval: Reshaped wirtinger flow and incremental algorithms.
Journal of Machine Learning Research, 18, 2017.

[44]
Shuheng Zhou, John Lafferty, and Larry Wasserman.
Compressed and privacy-sensitive sparse regression.
IEEE Transactions on Information Theory, 55(2):846–866, 2009.