 slightly worse than the sample complexity $O(d)$ for the problem itself to be well-posed. In contrast, even for sub-Gaussian noise we have $||\eta||\asymp \sqrt{n}$ (see Theorem 3.1.1 in \cite{vershynin2018high}), thus the bound $O\big(\frac{||\eta||}{\sqrt{n}}\big)$ reads as a constant error. In general, random noise is more likely to have small "spikiness", thus the bound $O\big(||\eta||_\infty\sqrt{\frac{d}{n}}\big)$ is tighter (Remark \ref{remark2}).
	
	
\subsection{NGPR with Heavy-tailed Random Noise}
	
	
	Contradictory to the sub-Gaussian or sub-exponential assumption, heavy-tailed behaviour is ubiquitous in many real data, e.g., economics data \cite{ibragimov2015heavy}, biomedical data \cite{woolson2011statistical,biswas2007statistical}, noise in signal processing or statistical estimation \cite{swami2002some,kruczek2020detect,fan2021shrinkage,wang2021robust}, machine learning \cite{wang2020differentially,wei2019statistical}. Generally speaking, frequent outliers in heavy-tailed data break the robustness of reconstruction process and fail the theoretical guarantee under sub-Gaussian data. To address the issue, many techniques in statistical estimation have been developed, especially in mean estimation, including median of means \cite{nemirovskij1983problem,hsu2016loss} and Catoni's mean estimator via robust empirical loss \cite{catoni2012challenging,brownlees2015empirical}, also see the survey \cite{lugosi2019mean}. Particularly, a shrinkage principle for low-rank trace regression was recently developed in \cite{fan2021shrinkage}, which was then applied in corrupted generalized linear regression \cite{zhu2021taming}, matrix and tensor completion \cite{shen2022computationally}, one-bit estimation \cite{chen2022high}, vector autoregressive model \cite{wang2021robust}. 
	
	
	
	
	In this Subsection, we consider {NGPR} under heavy-tailed random noise with bounded $l$-th moment. Compared with property (\ref{2.3b}), (\ref{2.5b}) of light-tailed distribution, it models much severer random noise. Obviously, due to lack of effective estimation on $||\eta||,||\eta||_\infty$, the general bound $O\big(\frac{||\eta||}{\sqrt{n}}\big)$ and $O\big(||\eta||_\infty\sqrt{\frac{d}{n}}\big)$ do not produce any meaningful result. 
	
	
	 To enhance robustness, we truncate overlarge responses to robustify the quadratic loss. Note that compared with previous works \cite{fan2021shrinkage,goldstein2018structured,zhu2021taming,shen2022computationally,chen2022high,wang2021robust} that revolve around high-dimensional structured signal recovery and convex programming, our problem setting is new and significantly different. To be specific, the objective is non-convex and $x_0$ is unstructured. 
	 
	 
	 The truncated response $\widetilde{y}_k$ with threshold $\tau>0$ is given by 
    $$\widetilde{y}_k = \mathrm{sign}(y_k) \min\big\{|y_k|,\tau\big\}.$$
	We then propose the estimator $\widehat{x}_{ht}$ by minimizing the robust empirical $\ell_2$ risk
	\begin{equation}
	    \label{3.16}
	    \widehat{x}_{ht} = \mathop{\arg\min}_x \sum_{k=1}^n \big(\widetilde{y}_k - x^*A_kx\big)^2.
	\end{equation}
  A worst-case estimation performance of $\widehat{x}_{ht}$ is established in Theorem \ref{theorem5}.
	
	
 
	
\begin{theorem}
    \label{theorem5}
    Consider {NGPR} with i.i.d. random noise satisfying $\mathbbm{E}|\eta_k|^l \leq M$ for certain $M>0$. Assume $||x_0|| \leq C_0 \big\{n(\log n)^{1-l}\big\}^{\frac{1}{4l}}$, and we choose $\tau = C_1\big(M^2n \log n \big)^{1/(2l)}$ with sufficiently large $C_1$. Then we can find $C_2,C_3,C_4>0$, such that when $n\geq C_2d$,  
    \begin{equation}
        \label{3.17}
        ||\widehat{x}_{ht}\widehat{x}_{ht}^* - x_0x_0^*||_F \leq C_3 \sqrt{\frac{d(\log n)^2}{n}} \big(n \log n \big)^{1/(2l)}
    \end{equation}
    holds with probability at least $1-8n^{-8} -5\exp \big(-C_4 d\big)$.
\end{theorem}
	
	
\noindent{\it Proof.} We start from the optimality of (\ref{3.16}) $$\sum_{k=1}^n \big(\widetilde{y}_k - \widehat{x}^*_{ht}A_k \widehat{x}^*_{ht}\big)^2 \leq \sum_{k=1}^n\big(\widetilde{y}_k - x_0^*A_kx_0\big)^2.$$	Plug in (\ref{1.1}), by some algebra we obtain
	\begin{equation}
	    \label{3.18}
	    \sum_{k=1}^n \Big(x_0^*A_kx_0 -\widehat{x}^*_{ht}A_k \widehat{x}_{ht}\Big)^2 \leq 2 \sum_{k=1}^n \Big(\widetilde{y}_k - y_k + \eta_k\Big) \Big(\widehat{x}^*_{ht}A_k\widehat{x}_{ht} - x_0^*A_kx_0\Big).
	\end{equation}
    By Theorem \ref{theorem1} there exist $C_2,C_3,C_4$ such that when $n \geq C_2 d$, we have 
	\begin{equation}
	    \label{3.19}
	    \mathbbm{P}\Big(\sum_{k=1}^n \Big(x_0^*A_kx_0 -\widehat{x}^*_{ht}A_k \widehat{x}_{ht}\Big)^2\geq C_3 n d(\widehat{x}_{ht},x_0)^2\Big) \geq 1-\exp (-C_4n).
	\end{equation}
	For the right hand side of (\ref{3.18}) we first decompose it as $ 2({T_1} + {T_2})$ where
	\begin{subequations}
\begin{align}
{T_1}& = \sum_{k=1}^n \Big(\widetilde{y}_k - y_k + \eta_k\Big) \Big(\widehat{x}^*_{ht}A_k\widehat{x}_{ht} - x_0^*A_kx_0\Big) \mathbbm{1}\Big(|\eta_k|\geq \frac{1}{2}\tau\Big);\label{3.20a} \\
{T_2}& = \sum_{k=1}^n \Big(\widetilde{y}_k - y_k + \eta_k\Big) \Big(\widehat{x}^*_{ht}A_k\widehat{x}_{ht} - x_0^*A_kx_0\Big) \mathbbm{1}\Big(|\eta_k|< \frac{1}{2}\tau\Big).\label{3.20b}
\end{align}
\label{3.20}
\end{subequations}
Note that $x_0^*A_kx_0 = \big<A_k,x_0x_0^*\big>$, $||x_0x_0^*||_F = ||x_0||^2 \leq C_0^2 \big\{n(\log n)^{1-l} \big\}^{\frac{1}{2l}}$, some calculations and (\ref{2.4}) verify  $$||x_0^*A_kx_0||_{\psi_2} \leq C_5||\mathscr{M}||_{\psi_2} n^{\frac{1}{2l}}\big(\log n\big)^{\frac{1-l}{2l}}.$$ 
By (\ref{2.3a}) for some $C_{6,0}>0$ we have $\mathbbm{P}\big(|x_0^*A_kx_0|\geq t\big)\leq 2\exp\big(-\frac{t^2}{C_{6,0}^2||x_0^*A_kx_