 \delta $ and $\|x\| \leq (a + \phi_d) \|{x_{\star}}\|$. We then note that for 
	$\xi$ and $\zeta$ as defined in \eqref{eq:zeta_xi_def} we have:
	\[
	\begin{aligned}
	|2^d x^{\rm T} \tilde{h}_x|^2 &\leq (|\xi| + |\zeta|)^2 (a + \phi_d)^2 \|{x_{\star}}\|^4 \\
	&\leq \big(\frac{\delta}{\pi} + 3 d^3 \delta + \rho_d \big)^2 (a + \phi_d)^2 \|{x_{\star}}\|^4 \\ 

	&\leq \big( \frac{\pi^3 d^3}{2} a+ \rho_d \big)^2 (a + \phi)^2 \|{x_{\star}}\|^4 \\
	&\leq ( 2 \pi^3 d^3 a + \rho_d^2 ) (a + \phi_d)^2 \|{x_{\star}}\|^4 \\

	&\leq 20 \pi d^3 a + \rho_d^2 \phi_d^2		
	\end{aligned}
	\]
	where the second inequality is due to \eqref{eq:xilrgtheta} and \eqref{eq:zetalrgtheta}, the rest  from $d \geq 2$, $ \rho_d \leq \phi_d \leq 1$ and  $2 \pi^3 d^3 a \leq 1$.
	Finally using $(\phi_d - a) \|{x_{\star}}\|\leq \|x\|$, we can then conclude that:
	\[
	f_E(x) - \frac{\|{x_{\star}}\|^4}{2^{2d+2}}  \geq \frac{1}{2^{2d+2}} \big[ (\phi_d - a)^4 - 2 (20 \pi d^3 a + \rho_d^2 \phi_d^2) \big] \|{x_{\star}}\|^4.
	\]  
\end{proof}
\section{Introduction}

In this paper we study the problem of estimating a spike vector ${{y_\star}} \in \mathbb{R}^n$ from data $Y$ consisting of a rank-1 matrix perturbed with random noise. In particular, the following random models for $Y$ will be considered.
\begin{itemize}
	\item The \textbf{Spiked Wishart Model} in which $Y \in \mathbb{R}^{N \times n}$ is given by:
	\begin{equation}\label{eq:wishart_Y}
	Y = u \, {{y_\star}}^{\rm T} + \sigma \mathcal{Z},
	\end{equation}
	where $\sigma > 0$, $u \sim \mathcal{N}(0,I_n)$ and $\mathcal{Z}$ are independent
	and $\mathcal{Z}_{ij}$ are i.i.d. from $\mathcal{N}(0,1)$.
	
	\item The \textbf{Spiked Wigner Model} in which $Y  \in \mathbb{R}^{n \times n}$ is given by:
	\begin{equation}\label{eq:wigner_Y}
	Y = {{y_\star}} {{y_\star}}^{\rm T} + \nu \mathcal{H} 
	\end{equation}
	where $\nu > 0$, $\mathcal{H} \in \mathbb{R}^{n \times n}$ 
	is drawn from a \textit{Gaussian Orthogonal Ensemble} GOE$(n)$, 
	i.e. $\mathcal{H}_{ii} \sim \mathcal{N}(0, 2/n)$ for all $1 \leq i \leq n$ and $\mathcal{H}_{ij} = \mathcal{H}_{ji} \sim \mathcal{N}(0,1/n)$ for $1 \leq j < i \leq n$.
\end{itemize}
Spiked random matrices have been extensively studied in recent years as they serve as a mathematical model for many statistical inverse problems such as PCA \citep{johnstone2001distribution,amini2008high, deshpande2014sparse, vu2012minimax}, synchronization over graphs \citep{abbe2014decoding,bandeira2015non,javanmard2016phase} and community detection  \citep{mcsherry2001spectral,deshpande2016asymptotic,moore2017computer}. They are, moreover, connected to the rank-1 case of other linear inverse problems such as matrix sensing and matrix completion under RIP-like assumptions on the measurements operator \cite{bhojanapalli2016global,zhang2018much}. 

\begin{comment}
\red{[Can you do without this text in red?]In the noiseless case ($\mathcal{Z} = 0$ or $\mathcal{H} = 0$) the spike ${{y_\star}}$ can be exactly recovered (up to scaling) from the leading right singular vector of the matrix $Y$.  In the noisy case, classical results in random matrix theory have then studied the spectral properties of the matrices $Y$ in the  $N,n \to \infty$ regime, identifying phase transition with respect to the signal-to-noise ratio above which ${{y_\star}}$ correlates with the top singular vector of $Y$, and below which the two vectors are instead asymptotically orthogonal \cite{baik2006eigenvalues,feral2007largest}. These critical values have been shown to furthermore correspond to information-theoretical limits for the detection problem (distinguishing between the case ${{y_\star}}=0$ and ${{y_\star}} \neq 0$) \cite{onatski2013asymptotic,ke2016detecting,perry2016optimality, banks2018information}. It follows that} in \red{these}
\end{comment}
In the high-dimensional/low signal-to-noise ratio 
regimes, it is fundamental to leverage additional prior information on the low-rank component in order to obtain consistent estimates of ${{y_\star}}$. 
Recent works, however,  have discovered that some priors give rise to gaps between what is statistically-theoretically optimal and can be achieved with unbounded computational resources, and what instead can be achieved with polynomial-time algorithms. A prominent example is represented by 
the Sparse PCA problem in which the vector ${{y_\star}}$ in \eqref{eq:wishart_Y} is taken to be sparse (see next section and \cite{bandeira2018notes,kunisky2019notes} for surveys of recent approaches).  

In this paper we study the spiked random matrix models  \eqref{eq:wishart_Y} and \eqref{eq:wigner_Y}, where 
the prior information on the planted signal ${{y_\star}}$ 
comes from a learned generative network. 
In particular, we assume that a generative neural network $G: \mathbb{R}^k \to \mathbb{R}^n$ with $k < n$, has been trained on a data set of spikes, and the unknown spike ${{y_\star}} \in \mathbb{R}^n$ lies on the range of $G$, i.e. we can write ${{y_\star}} = G({x_{\star}})$ for some ${x_{\star}} \in \mathbb{R}^k$.
As a mathematical model for the trained $G$, we consider  
a $d$-layer feed forward network of the form:
\begin{equation}\label{eq:Gx}
G(x) = \text{relu}(W_d \dots \text{relu}(W_2 \text{relu}(W_1 x)) \dots)
\end{equation}
with weight matrices $W_i \in \mathbb{R}^{n_i \times n_{i-1}}$ and $\text{relu}(x) = \max(x,0)$  is applied entrywise. We furthermore assume that the network is expansive, i.e. $n = n_d > n_{d-1} > \dots > n_0 = k$, and the weights have Gaussian entries. This  modeling assumption was introduced in \cite{HV17}, and additionally it and its variants were used in \cite{HHHV18,oscar2018phase,ma2018invertibility,hand2019global,song2019surfing}. See  Section \ref{sec:informal} for justifications of this model. 

Generative priors have been shown to close a computational-to-statistical gap in the Compressive Phase Retrieval problem.
With a sparsity prior the information-theoretically optimal sample complexity is proportional to the sparsity level $s$ of the signal, on the other hand the best known algorithms (convex methods \cite{hand2016compressed,li2013sparse,ohlsson2011compressive}, iterative thresholding \cite{cai2016optimal, wang2017sparse, yuan2019phase}, etc.) require a sample complexity proportional to $s^2$ for stable recovery, a barrier which might not be resolvable by polynomial-time algorithms \cite{barbier2019optimal}.
Under the generative