#  Impact of granular inclusions on the phase behavior of colloidal gels

Yankai Li  School of Engineering, The University of Edinburgh, King’s
Buildings, Edinburgh EH9 3FG, United Kingdom  John R. Royer  SUPA, School of
Physics and Astronomy, The University of Edinburgh, King’s Buildings,
Edinburgh EH9 3FD, United Kingdom  Jin Sun  School of Engineering, The
University of Edinburgh, King’s Buildings, Edinburgh EH9 3FG, United Kingdom
Christopher Ness  School of Engineering, The University of Edinburgh, King’s
Buildings, Edinburgh EH9 3FG, United Kingdom

###### Abstract

Colloidal gels formed from small attractive particles are commonly used in
formulations to keep larger components in suspension. However, despite
extensive work characterizing unfilled gels, little is known about how larger
inclusions alter the phase behavior and microstructure of the colloidal
system. Here we use numerical simulations to examine how larger ‘granular’
particles can alter the gel transition phase boundaries. We find two distinct
regimes depending on both the filler size and native gel structure: a
‘passive’ regime where the filler fits into already-present voids, giving
little change in the transition, and an ‘active’ regime where the filler no
longer fits in these voids and instead perturbs the native structure. In this
second regime the phase boundary is controlled by an effective colloidal
volume fraction given by the available free volume.

##  I Introduction

Dispersions of attractive colloids can form solid-like gels characterized by a
system-spanning network of arrested particles [1, 2, 3]. These colloidal gels
are ubiquitous, encountered in disparate industries ranging from food and
personal care products to building materials and catholyte slurries [4, 5, 6,
7]. While there has been considerable progress in understanding the formation,
structure and rheology of ‘model’ colloidal gels formed from (nearly)
uniformly sized spheres [8, 9, 10], most practical gels are more complex. In
particular, colloidal gels frequently serve as a carrier for larger, non-
Brownian ‘granular’ components (typical size
$\gtrsim$10\text{\,}\mathrm{\SIUnitSymbolMicro m}$$). In such composites, the
gel often acts as a rheology modifier to prevent sedimentation. In some
applications the gel network itself may be desired, for example catholyte
slurries for battery manufacturing rely on a conductive carbon black gel to
provide connectivity between the active Li-ion ‘grains’.

It is thus critical to understand how granular inclusions alter the colloidal
gel phase. Recent work examining the influence of inclusions on gel rheology
suggests they have a significant impact [11, 12], even introducing new
phenomena such as rheological bi-stability in these filled systems [13]. This
previous work has largely focused on systems deep into the gel state, so it
remains unclear how granular inclusions alter the gel transition and phase
behavior.

For uniformly-sized colloidal spheres, the gelation phase boundaries depend on
the colloid concentration and attraction strength, and there has been
extensive work mapping these boundaries in a variety of systems [14, 15, 16,
17, 18, 19, 20, 21, 22, 23]. In depletion gels there is good agreement between
gelation and the gas-liquid spinodal boundary [24], though there remains some
debate concerning the generality of this agreement and the relative roles of
percolation and clustering at the gel transition [21, 22, 23, 25].

The inclusion of larger grains introduces additional control parameters which
can potentially alter these phase boundaries. For simple ‘hard’ grains
interacting solely through their excluded volume, their influence will be set
by the filler concentration and the size ratio $r_{L}/r_{S}$ between the large
($L$) grains and the smaller ($S$) colloids. These granular inclusions reduce
the free volume available to the colloids relative to the total volume, but
the interplay between the inclusions and gel structure is non-trivial, as
colloidal gels can be heterogeneous on length scales $\gg r_{S}$ [26, 27, 3].

Here we characterise the influence of hard granular inclusions on the
colloidal gel phase boundaries using numerical simulations, where the particle
sizes, interactions and volume fractions can all be precisely varied. We find
that the relative sizes of the inclusions and the void spaces present in the
unfilled gels is the key parameter governing the phase behavior of the filled
systems.

##  II Results and Discussion

Figure 1:  Isostaticity percolation and its relation to the mechanical
response. (A) Procedure for determining $L_{\rm iso}$. Left to right:
Isostatic colloids with $N\geq 6$ contacts are isolated and contacting
clusters identified. The isostatic length is computed from the span of the
largest cluster, $L_{\rm iso}\equiv(L_{x}+L_{y}+L_{z})/3L$. (B) Time evolution
of $L_{\text{iso}}$ for an unfilled system ($\phi_{S}=0.2$, $\phi_{L}=0$) at
varying attraction $\epsilon/kT$. (C) Steady-state
$L^{\text{ss}}_{\text{iso}}$ (black, left axis) and viscoelastic moduli
$G^{\prime}$ and $G^{\prime\prime}$ (red filled and open symbols,
respectively, right axis) verses $\epsilon/kT$. Green arrow highlights the
coincidence between the crossover $G^{\prime}=G^{\prime\prime}$ and
$L_{\text{iso}}^{\text{ss}}\simeq 1$. Inset: rendering of a steady-state
($t/\tau_{B}\gg 1)$ gel state for $\epsilon/kT=5.6$ with $\phi_{S}=0.2$,
$\phi_{L}=0$. (D) and (E) reproduce (B) and (C), respectively, for a filled
system with $\phi_{S}=0.20$, $\phi_{L}=0.3$. Inset in (E) shows a rendering
with granular inclusions (yellow) at $\epsilon/kT=5.6$. Error bars in (B-E)
indicate the standard deviation from 6 realisations.

We perform Langevin Dynamics using LAMMPS [28], simulating the behavior of
$10^{4}$ colloidal spheres (bidisperse with radii $r_{S}$ and $1.4r_{S}$) and
a varying number of larger grains (monodisperse with radius $r_{L}$ varied
between $8r_{S}-24r_{S}$). These simulations, detailed below in Methods,
incorporate random Brownian forces, Stokes drag and inter-particle
interactions, where we prescribe short range attraction between the small
colloids and hard-sphere-like contact repulsion for interactions involving the
larger grains. The system initially equilibrates without the colloidal
attraction, then an interaction potential with depth $\epsilon/kT$ is turned
on and the system evolved for up to $10^{3}\tau_{B}$ to reach a steady state,
with $\tau_{B}=6\pi\eta r_{S}^{3}/kT$ the Brownian diffusion time. To map the
phase behavior of these systems, we vary $\epsilon/kT$ along with colloidal
and granular volume fractions, $\phi_{S}=V_{s}/V$ and $\phi_{L}=V_{L}/V$.
These volume fractions are defined by the volume occupied by the colloids
(grains),$V_{s}$ ($V_{L}$), relative to the total volume of the cubic
simulation box, $V=L^{3}$, so that increasing $\phi_{L}$ at fixed $\phi_{S}$
decreases the free volume available to the colloids.

### Isostaticity percolation and mechanical response

To explore how large granular inclusions alter the colloidal microstructure,
we characterize networks of isostatic particles, defined as colloids with
$\geq 6$ contacts. This follows from the Maxwell criteria for stability in a
system with pairwise central forces, requiring that constraints balance the
degrees of freedom [29]. While this isostaticity criterion is typically
considered globally in the context of granular packings [30], it has been
suggested that networks of locally isostatic particles control the rigidity of
colloidal gels [9, 31]. Specifically, recent experimental work suggests the
gel transition coincides with the formation of a percolating network of
isostatic particles [32].

We define contacts among attractive colloids as pairs (radii $r_{i}$ and
$r_{j}$) within a separation $0.03(r_{i}+r_{j})$ (see Methods). To
characterise the distance from isostaticity percolation, we first remove
colloids with $<6$ contacts and then identify clusters of isostatic particles.
The isostatic length, $L_{\text{iso}}$, gives the mean length of the largest
isostatic cluster in all three spatial dimensions relative to the box size
(Fig. 1A), so that $L_{\text{iso}}=1$ corresponds to isotropic isostaticity
percolation.

In pure colloidal suspensions ($\phi_{L}=0$), the colloids are initially well-
dispersed with $L_{\text{iso}}\approx 0$. Turning on the attraction $\epsilon$
at time $t=0$ causes clusters to form and grow, reflected in an increase in
$L_{\text{iso}}(t)$ with time (Fig. 1B). As time progresses this initial
growth slows and the isostatic length approaches a plateau at some steady-
state value $L^{\text{ss}}_{\text{iso}}$ at long times ($t\gtrsim
10^{3}\tau_{B}$). The growth of $L_{\text{iso}}(t)$ depends on the attraction
strength, with strongly attractive colloids rapidly reaching isostaticity
percolation at $L^{\text{ss}}_{\text{iso}}=1$ while with weaker attraction
$L_{\text{iso}}$ instead appears to plateau at some steady-state value
$L^{\text{ss}}_{\text{iso}}<1$, short of the percolation threshold.

We apply small amplitude oscillatory shear $\gamma(t)=\gamma_{0}\sin\omega t$
to extract the viscoelastic moduli $G^{\prime}$ and $G^{\prime\prime}$ for
these steady-state structures (see Methods). We find a transition from liquid-
like states ($G^{\prime}<G^{\prime\prime}$) to solid-like states
($G^{\prime}>G^{\prime\prime}$) as the attraction strength $\epsilon$ is
increased (Fig. 1C), indicating the emergence of a solid-like gel. The
crossover point where $G^{\prime}=G^{\prime\prime}$ occurs as
$L_{\text{iso}}^{\text{ss}}$ approaches unity at interaction energy
$\epsilon^{*}$, indicating that the gel transition coincides with isostaticity
percolation in agreement with Ref [32]. We verified this agreement holds for
$\phi_{S}\leq 0.4$.

### Role of granular inclusions

The addition of granular inclusions gives qualitatively similar behavior in
both the evolution of $L_{\text{iso}}$ with time and the mechanical response
of the steady state structures, Figs. 1D, E. We again find good agreement
between isostaticity percolation ($L_{\text{iso}}^{\text{ss}}\simeq 1$) and
the emergence of mechanical rigidity ($G^{\prime}=G^{\prime\prime}$),
indicated by green arrows in Figs. 1C and E. Comparing these transition points
for filled ($r_{L}=8r_{S}$, $\phi_{L}=0.3$) and unfilled systems both at
$\phi_{S}=0.2$, we find that the inclusions aid gelation with a reduced
$\epsilon^{*}$ in the filled system.

To understand this shift in the gelation point, we examine how granular
inclusions alter the structure and distribution of the isostatic colloidal
particles. In a pure colloidal system below the gel transition,
$\epsilon=\text{5.1}kT=0.94\epsilon^{*}$ and $\phi_{S}=0.2$, there are
numerous disjoint clusters of isostatic particles (Fig. 2A) and the system
remains well below the isostatic percolation threshold. The inclusion of the
larger grains increases the number of isostatic colloidal particles, enabling
them to instead form a large connected network which percolates across the
sample for $\phi_{L}=0.4$ (Fig. 2B).

For fixed $\phi_{S}=0.2$, we find that $L_{\text{iso}}^{\text{ss}}$ increases
dramatically with increasing $\phi_{L}$ (Fig. 2C). Defining
$\epsilon^{*}_{0}\equiv\epsilon^{*}(\phi_{L}=0)$ the critical interaction
energy in the unfilled system, granular inclusions can take a system initially
quite far from the gelation point ($\epsilon=0.89\epsilon^{*}_{0}$ and
$L_{\text{iso}}^{\text{ss}}\approx 0$) nearly up to the transition point
$L_{\text{iso}}^{\text{ss}}\lesssim 1$ as $\phi_{L}$ increases up to
$\phi_{L}=0.4$. Increasing the interaction energy
$\epsilon/\epsilon^{*}_{0}\to 1$, the volume of granular filler needed to
drive isostaticity percolation decreases, so that the gelation boundary
$\epsilon^{*}$ where $L_{\text{iso}}^{\text{ss}}\to 1$ continuously shifts to
lower values with increasing $\phi_{L}$.

Since the free volume available to the colloids decreases with increasing
$\phi_{L}$, one might expect this increase in the number of isostatic
particles, and hence an increase in $L_{\text{iso}}^{\text{ss}}$ in the filled
system. Furthermore, the gel phase boundary for unfilled systems,
$\epsilon^{*}_{0}(\phi_{S})$, is a decreasing function of $\phi_{S}$, at least
at low to moderate concentrations [14, 15, 16, 17, 18, 19, 20, 21, 22, 23].
This suggests the possibility of capturing the shifting gel point with
granular inclusions simply in terms of the reduced free volume available to
the colloids. In this picture, one would expect the filler to have more
pronounced effect at lower colloid concentrations, where the curve
$\epsilon^{*}_{0}(\phi_{S})$ is steepest. However, simulations with
$\phi_{S}=0.1$ instead show the opposite, with the inclusion of large grains
giving only a modest increase in $L_{\text{iso}}^{\text{ss}}$ (Fig. 2D) and
minor shifts in the gelation phase boundary.

Figure 2:  Contrasting effects of granular inclusions. Snapshots of steady-
state ($t=10^{3}\tau_{B}$) configurations, with $\phi_{S}=0.2$ and
$\epsilon=0.94\epsilon^{*}_{0}$ for (A) $\phi_{L}=0$ and; (B) $\phi_{L}=0.4$.
Only isostatic colloids are rendered, with the largest cluster shown in red.
Larger grains also shown (grey) in (B). (C,D);
$L_{\text{iso}}^{\text{ss}}(\phi_{L})$ at varying $\epsilon$ for (C)
$\phi_{S}=0.2$ and (D) $\phi_{S}=0.1$. Values for $\epsilon$ given relative to
the gelation point in the unfilled system, $\epsilon_{0}^{*}$, with
$\epsilon_{0}^{*}=5.4kT$ for $\phi_{S}=0.2$ and $\epsilon_{0}^{*}=6.3kT$ for
$\phi_{S}=0.1$. Dashed squares a) and b) indicate states rendered in (A) and
(B), respectively.
Figure 3:  Void-volumes in filled and unfilled systems near the gel boundary.
Normalized colloidal void size distribution $P(r_{v})$ for (A) $\phi_{S}=0.2$
($\epsilon=5.3kT\approx 0.98\epsilon_{0}$) and (B) $\phi_{S}=0.1$
($\epsilon=6.3kT\approx\epsilon_{0}^{*}$) at varying $\phi_{L}$. The large
particle size is $r_{L}=8r_{S}$ (highlighted by black dashed vertical lines),
with the exception of the red filled symbols in (B) where $r_{L}=16r_{S}$
(highlighted by the red dashed vertical line). (C)
$L_{\text{iso}}^{\text{ss}}(\phi_{L})$ for $\epsilon=5.8kT$ (red circles) and
$5.5kT$ (blue triangles), with open symbols for $r_{L}=8r_{S}$ and filled
symbols for $r_{L}=16r_{S}$. Schematic cartoon in (D) presents a simplified
picture to understand the influence (or lack thereof) of the granular filler
on the gel structure, with large grains either fitting into ‘natural’ voids in
the gel, leaving the colloidal microstructure unaffected (black arrow), or
forcing larger voids, which in turn distorts and compresses the colloidal
phase (red arrows).

### Fillers and voids

To understand the reduced filler impact at low $\phi_{S}$, we look at how the
microstructure of the colloidal phase varies with concentration. Specifically,
we focus on the size distribution of the empty voids between the colloids at
(or close to) the gel transition [33]. We compute this distribution by
dividing the simulation volume into cubic cells (length $r_{S}$) and then
finding the largest possible sphere (radius $r_{v}$) centered in each cell
that avoids intersecting a colloidal particle (so that larger grains are
treated as empty voids). Normalised histograms of these local void radii give
the void size distribution $P(r_{v})$.

For an unfilled colloidal system with $\phi_{S}=0.2$ close to the gel
transition ($\epsilon=5.3kT\approx 0.98\epsilon^{*}_{0}$), this distribution
is nearly flat up to $r_{v}\approx 3r_{S}$ and then falls off rapidly as
$r_{v}$ increases further (Fig. 3A) with voids larger than $r_{v}\approx
6r_{S}$ exceedingly rare. While precisely characterizing the rare-event tails
in $P(r_{v})$ would require significant computational effort, we can define an
effective maximum void size $P(r_{v}^{\text{max}})=10^{-4}$, as voids larger
then this are effectively absent in our observed configurations. Adding larger
granular inclusions, with $r_{L}=8r_{S}>r_{v}^{\text{max}}$, perturbs the
colloidal microstructure and shifts the shoulder in $P(r_{v})$ to higher radii
$\approx r_{L}$, reflecting the voids created by the large grains.

Figure 4: Isostatic percolation boundaries $\epsilon^{*}$ varying $\phi_{S}$
and $\phi_{L}$. Inset: Critical attractive energy $\epsilon^{*}(\phi_{S})$ for
varying $\phi_{L}$ (indicated in main panel legend) for $r_{L}=8r_{S}$. Main
panel: Open symbols show same data as inset, now plotted against
$\phi_{\text{eff}}=\phi_{S}/(1-\phi_{L})$. Solid symbols show results for
larger grains and smaller $\phi_{S}$, with $r_{L}=16r_{S}$ for $\phi_{S}=0.1$
and $r_{L}=24r_{S}$ for $\phi_{S}=0.07$ so that $r_{L}>r_{v}^{\text{max}}$ in
both cases. Error bars on $\epsilon^{*}$ computed using error bars on
$L_{\text{iso}}^{\text{ss}}$ to obtain upper and lower bounds for the point
the isostatic length exceeds our threshold
$L_{\text{iso}}^{\text{ss}}=L_{\text{iso}}^{*}=0.99$ and are shown only in the
inset for clarity.

However, reducing the colloid concentration to $\phi_{S}=0.1$ gives a
significantly wider distribution of void sizes in the unfilled system, with
the shoulder in $P(r_{v})$ now around $r_{v}=8r_{S}$ and
$r_{v}^{\text{max}}\approx 12r_{S}$ (Fig. 3B). This indicates there are ‘pre-
existing’ voids which can accommodate the larger $r_{L}=8r_{S}$ grains without
forcing a significant change in the colloidal microstructure. Indeed, in
contrast to the large shift seen for $\phi_{S}=0.2$, here increasing
$\phi_{L}$ has only a minor impact on the shape of $P(r_{v})$. This suggests a
picture where dilute gels with $r_{v}>r_{L}$ can effectively form around the
immobile granular inclusions, forming a network of colloid-colloid contacts
that is essentially indistinguishable from the unfilled case. With no change
in this network, $L_{\text{iso}}$ is unaffected by the granular inclusions and
there is little shift in the gel phase boundary. We would thus expect that
increasing $r_{L}$ above the characteristic void size would result in a more
pronounced filler-effect on $L_{\text{iso}}^{\text{ss}}$ and the gelation
point in these more dilute gels.

We find this is indeed the case when $r_{L}$ is increases from $8r_{S}$ to
$16r_{S}$. These larger grains now notably shift $P(r_{v})$ to higher values
(compare open and filled symbols in Fig. 3B), and also now find a clear
increase in $L_{\text{iso}}^{\text{ss}}(\phi_{L})$ (Fig. 3C), similar to the
impact of the $r_{L}=8r_{S}$ grains in the $\phi_{S}=0.2$ system with smaller
voids. This supports a simplified picture of the interplay between the
granular inclusions and attractive colloids (Fig. 3D); grains with
$r_{L}<r_{v}$ have little impact on the gel structure or transition point as
they easily fit into the gel voids, while grains with $r_{L}>r_{v}$ distort
and compress colloidal structures, increasing $L_{\text{iso}}^{\text{ss}}$ and
reducing the attraction needed to form the gel.

### Phase Diagram

Having detailed the influence of granular inclusions at two specific
$\phi_{S}$, we now map out the gel phase boundaries over a range of $\phi_{S}$
and $\phi_{L}$. Having demonstrated good agreement between the rigidity onset
and isostaticity percolation, we use $L_{\text{iso}}^{\text{ss}}$ to classify
states. Carrying out a series of simulations at varying $\epsilon$ for given
$\phi_{S}$ and $\phi_{L}$, we define the transition point $\epsilon^{*}$ as
the point $L_{\text{iso}}^{\text{ss}}=L_{\text{iso}}^{*}=0.99$ using linear
interpolation between the finite $\epsilon$ steps. The need for a threshold
$L_{\text{iso}}^{*}\lesssim 1$ reflects ambiguities in counting bonds which
cross our periodic boundaries. We verified our results are not sensitive to
the precise threshold, with values $0.99\leq L_{\text{iso}}^{*}\leq 0.999$
giving nearly indistinguishable phase boundaries.

For the range of $\phi_{S}$ explored here (up to $\phi_{S}=0.4$), we find the
isostatic percolation boundary $\epsilon^{*}(\phi_{S})$ monotonically
decreases with increasing $\phi_{S}$ (Fig. 4 inset). For fixed $r_{L}=8r_{S}$,
increasing $\phi_{L}$ at fixed $\phi_{S}$ generally shifts this boundary to
lower attraction strength.

Instead plotting these isostatic percolation boundaries as a function of an
effective volume fraction $\phi_{\text{eff}}\equiv\phi_{S}/(1-\phi_{L})$,
giving the volume fraction of the small colloids relative to the free volume
excluding the large grains $(1-\phi_{L})V$, we find reasonable collapse for
$\phi_{\text{eff}}\gtrsim 0.2$ (Fig. 4 main panel). This suggests that the
filler-induced shifts in the phase boundary can be understood solely through
the reduction in free volume available to small colloids, so that adding
larger grains is effectively equivalent to shrinking the box volume. However,
for $\phi_{S}\lesssim 0.1$ we find this collapse breaks down, with points at
higher $\phi_{L}$ lying clearly above the $\phi_{L}=0$ boundary. This is
consistent with the behavior seen in Fig. 2D, where the granular inclusions
only have a minor effect on $L_{\text{iso}}$ for $\phi_{S}=0.1$ compared to
the significant enhancement seen at a higher $\phi_{S}=0.2$.

Increasing the size of the large particles to ensure
$r_{L}>r_{v}^{\text{max}}$, in this case setting $r_{L}=16r_{S}$ for
$\phi_{S}=0.1$ and $r_{L}=24r_{S}$ for $\phi_{S}=0.07$, we find that this
collapse can be recovered (filled symbols in Fig. 4). We thus see that when
the granular inclusions are significantly larger than the typical voids in the
unfilled gel, so that they force a notable change in the gel microstructure,
the influence of the voids can be captured by the effective free volume
available to the small colloids. With smaller grains this effect is
diminished, with the phase boundary instead largely independent of the filler
concentration.

##  III Conclusions

Using Langevin dynamics simulations, we have mapped out the influence of
larger granular inclusions on isostaticity percolation and the gel transition
in suspensions of smaller attractive colloids. Varying the volume fractions of
both species, we demonstrated two distinct regimes: (i) a ‘passive void-
filling’ regime, where the granular inclusions can fit into already-present
voids within the gel, so that the microstructure is effectively unchanged and
the gel transition governed almost solely by $\phi_{S}$ and (ii) an ‘active
void-enhancing’ regime where the granular inclusions perturb the gel structure
by forcing larger voids and the gel transition governed by an effective volume
fraction $\phi_{\text{eff}}={\phi_{S}}/(1-\phi_{L})$. These two limiting
regimes are differentiated by the size ratio of the larger grains $r_{L}$ and
shape of the gel void size distribution $P(r_{v})$, so that anticipating the
impact of the granular filler requires detailed characterization of the
unfilled gel structure.

There is relatively little experimental work examining the phase behavior of
filled colloidal gels, though a recent study using a battery electrode slurry
(a carbon black gel with $\approx$10\text{\,}\mathrm{\SIUnitSymbolMicro m}$$
granular inclusions) found little change with addition of the granular
particles [7]. Given the very low gel point (occurring at $\phi_{S}\approx
0.02$), it is plausible that the carbon black gel contains sufficiently large
voids to place this system in regime (i), though detailed characterisation of
the gel structure would be required to confirm this. Our results should be
particularly relevant to battery slurry formulation and electrode fabrication,
where particle connectivity is key for performance [6], providing a road map
to match the native gel structure and filler properties to tune the electrode
microstructure.

##  IV Methods

We simulate the trajectories of $10^{4}$ colloidal and a smaller number of
granular spheres in a periodic box (volume $V$) according to the Langevin
equation, which for particle $i$ reads
$m_{i}d\textbf{U}_{i}/dt=\textbf{F}_{i}^{H}+\textbf{F}_{i}^{B}+\textbf{F}_{i}^{P}\text{,}$
with $m_{i}$ and $\textbf{U}_{i}$ the particle mass and velocity respectively.
The hydrodynamic force $\textbf{F}_{i}^{H}=-6\pi\eta
r_{i}(\textbf{U}_{i}-\textbf{U}^{\infty}_{i}),$ captures Stokes drag on a
sphere with radius $r_{i}$, with $\textbf{U}^{\infty}_{i}$ the background
fluid velocity (generally set to 0 except under oscillatory shear).

Brownian forces are generated as $\textbf{F}_{i}^{B}=\sqrt{12\pi\eta
r_{i}kT/\Delta t}\textbf{R},$ where $\Delta t$ is the timestep, $kT$ the
thermal energy and the elements of the vector R are drawn from a Gaussian
distribution with zero-mean and no time correlation. The characteristic
diffusive timescale for a particle with radius $r_{i}$ is thus $6\pi\eta
r_{i}^{3}/kT$. To avoid crystallisation in the small colloids, we use a binary
size mixture with radii $r_{S}$ and $1.4r_{S}$, while the larger grains are
monodisperse with radius $r_{L}$ varying from $8r_{S}$ to $24r_{S}$. Since the
diffusion time scales as $r_{i}^{3}$, for the larger grains it is $>500$ times
longer than the colloidal timescale $\tau_{B}=6\pi\eta r_{S}^{3}/kT$, so that
even though Brownian forces are applied uniformly to all particles the larger
grains are effectively non-Brownian.

Colloids (labeled $i$ and $j$) at a distance $r$ and surface-to-surface
separation $\delta_{ij}=r-(r_{i}+r_{j})$ interact via a Morse potential,
giving a force
$\textbf{F}_{ij}^{p}=\epsilon\kappa_{ij}e^{-\kappa_{ij}\delta_{ij}}(e^{-\kappa_{ij}\delta_{ij}}-1)\textbf{n}_{ij}\text{}$
with $\textbf{n}_{ij}$ the center-to-center unit vector. This potential gives
finite-ranged attraction, and repulsion for overlapping particles
($\delta_{ij}<0$). The interaction length scale is set as
$\kappa_{ij}^{-1}=(r_{i}+r_{j})/200$ to give short-ranged attraction. We
evaluate the force when $\delta_{ij}<0.03(r_{i}+r_{j})$ (following
conventional practice, see e.g. [34]), beyond which the attractive force is
$<1\%$ of its maximum value. We defined contacts using the same threshold of
$\delta_{ij}$, having verified that a more stringent criteria does not affect
any of the conclusions we draw. The depth of the attractive potential
$\epsilon$ is varied between $kT$ and $20kT$, with a variable step size to
refine our estimates of the gelation point. Colloid-granular and granular-
granular contact forces are modeled as linear springs
$\textbf{F}_{ij}^{p}=-k_{n}\delta_{ij}\textbf{n}_{ij},$ with a stiffness
$k_{n}$ set sufficiently large to approximate hard-sphere interactions (i.e.
$k_{n}r_{i}^{2}\gg\epsilon$, $kT$). The timestep $\Delta t$ is set to
$10^{-4}$, substantially smaller than $\tau_{B}$ and $\sqrt{m/k_{n}}$.

We characterise the mechanical response of steady-state structures by applying
an oscillatory shear
$\textbf{U}^{\infty}_{i}(t,y_{i})=y_{i}\gamma_{0}\sin\omega t$ and turning off
the Brownian forces. The bulk shear stress is computed as
$\sigma_{ij}=V^{-1}\sum r_{ij}F^{\text{tot}}_{ij}$ (with the sum being over
all interacting pairs), and the viscoelastic moduli $G^{\prime}$ and
$G^{\prime\prime}$ computed from the Fourier transform of $\sigma_{xy}$
averaged over 50 shear cycles. All results for both the elastic moduli and
$L_{\text{iso}}$ are averages from 6 independent realisations with randomized
granular and colloidal initial positions.

##  V Acknowledgments

YL is funded by the China Scholarship Council (CSC) and by the University of
Edinburgh through a School of Engineering studentship. C.N. acknowledges
support from the Royal Academy of Engineering under the Research Fellowship
scheme. The work was supported by the UK Engineering and Physical Sciences
Research Council under grant EP/N025318/1. For the purpose of open access, the
authors have applied a Creative Commons Attribution (CC BY) licence to any
Author Accepted Manuscript version arising from this submission. YL, JR, JS
and CN planned the research; YL carried out the research; YL, JR and CN wrote
the manuscript. The data used to generate the figures in this article is
available via Edinburgh DataStore at XXX.

## References

  * Trappe and Sandkühler [2004] V. Trappe and P. Sandkühler, Current Opinion in Colloid and Interface Science 8, 494 (2004).
  * Zaccarelli [2007] E. Zaccarelli, Journal of Physics: Condensed Matter 19, 323101 (2007).
  * Royall  _et al._ [2021] C. P. Royall, M. A. Faers, S. L. Fussell, and J. E. Hallett, Journal of Physics: Condensed Matter 33, 453002 (2021).
  * Cho  _et al._ [2013] K. Y. Cho, Y. I. Kwon, J. R. Youn, and Y. S. Song, Materials Research Bulletin 48, 2922 (2013).
  * Wei  _et al._ [2015] T.-S. Wei, F. Y. Fan, A. Helal, K. C. Smith, G. H. McKinley, Y.-M. Chiang, and J. A. Lewis, Advanced Energy Materials 5, 1500535 (2015).
  * Hawley and Li [2019] W. B. Hawley and J. Li, Journal of Energy Storage 25, 100862 (2019).
  * Morelly  _et al._ [2017] S. L. Morelly, M. H. Tang, and N. J. Alvarez, Polymers 9, 461 (2017).
  * Trappe  _et al._ [2001] V. Trappe, V. Prasad, L. Cipelletti, P. N. Segre, and D. A. Weitz, Nature 411, 772 (2001).
  * Hsiao  _et al._ [2012] L. C. Hsiao, R. S. Newman, S. C. Glotzer, and M. J. Solomon, Proceedings of the National Academy of Sciences 109, 16029 (2012).
  * Wang  _et al._ [2019a] G. Wang, A. M. Fiore, and J. W. Swan, Journal of Rheology 63, 229 (2019a).
  * Ferreiro-Córdova  _et al._ [2022] C. Ferreiro-Córdova, G. Foffi, O. Pitois, C. Guidolin, M. Schneider, and A. Salonen, Soft Matter 18, 2842 (2022).
  * Ferreiro-Cordova  _et al._ [2020] C. Ferreiro-Cordova, E. Del Gado, G. Foffi, and M. Bouzid, Soft Matter 16, 4414 (2020).
  * Jiang  _et al._ [2022] Y. Jiang, S. Makino, J. R. Royer, and W. C. Poon, Physical Review Letters 128, 248002 (2022).
  * Grant and Russel [1993] M. C. Grant and W. B. Russel, Physical Review E 47, 2606 (1993).
  * Verduin and Dhont [1995] H. Verduin and J. K. Dhont, Journal of Colloid and Interface Science 172, 425 (1995).
  * Poon  _et al._ [1995] W. C. K. Poon, A. D. Pirie, and P. N. Pusey, Faraday Discuss. 101, 65 (1995).
  * Segrè  _et al._ [2001] P. N. Segrè, V. Prasad, A. B. Schofield, and D. A. Weitz, Physical Review Letters 86, 6042 (2001).
  * Shah  _et al._ [2003] S. A. Shah, Y.-L. Chen, K. S. Schweizer, and C. F. Zukoski, Journal of Chemical Physics 119, 8747 (2003).
  * Sedgwick  _et al._ [2005] H. Sedgwick, K. Kroy, A. Salonen, M. B. Robertson, S. U. Egelhaaf, and W. C. K. Poon, The European Physical Journal E 16, 77 (2005).
  * Lu  _et al._ [2008] P. J. Lu, E. Zaccarelli, F. Ciulla, A. B. Schofield, F. Sciortino, and D. A. Weitz, Nature 453, 499 (2008).
  * Eberle  _et al._ [2011] A. P. Eberle, N. J. Wagner, and R. Castaneda-Priego, Physical Review Letters 106, 105704 (2011).
  * Helgeson  _et al._ [2014] M. E. Helgeson, Y. Gao, S. E. Moran, J. Lee, M. Godfrin, A. Tripathi, A. Bose, and P. S. Doyle, Soft Matter 10, 3122 (2014).
  * Whitaker  _et al._ [2019] K. A. Whitaker, Z. Varga, L. C. Hsiao, M. J. Solomon, J. W. Swan, and E. M. Furst, Nature Communications 10, 2237 (2019).
  * Tuinier and Lekkerkerker [2011] R. Tuinier and H. N. Lekkerkerker,  _Colloids and the Depletion Interaction_ (Springer Netherlands, 2011).
  * Zhang  _et al._ [2019] S. Zhang, L. Zhang, M. Bouzid, D. Z. Rocklin, E. Del Gado, and X. Mao, Physical Review Letters 123, 058001 (2019).
  * Fierro  _et al._ [2008] A. Fierro, E. D. Gado, A. de Candia, and A. Coniglio, Journal of Statistical Mechanics: Theory and Experiment 2008, L04002 (2008).
  * Zaccone  _et al._ [2009] A. Zaccone, H. Wu, and E. Del Gado, Physical Review Letters 103, 208301 (2009).
  * Thompson  _et al._ [2022] A. P. Thompson, H. M. Aktulga, R. Berger, D. S. Bolintineanu, W. M. Brown, P. S. Crozier, P. J. in ’t Veld, A. Kohlmeyer, S. G. Moore, T. D. Nguyen, R. Shan, M. J. Stevens, J. Tranchida, C. Trott, and S. J. Plimpton, Computer Physics Communications 271, 108171 (2022).
  * Maxwell [1864] J. C. Maxwell, The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science 27, 294 (1864).
  * van Hecke [2009] M. van Hecke, Journal of Physics: Condensed Matter 22, 033101 (2009).
  * Wang  _et al._ [2019b] G. Wang, A. M. Fiore, and J. W. Swan, Journal of Rheology 63, 229 (2019b).
  * Tsurusawa  _et al._ [2019] H. Tsurusawa, M. Leocmach, J. Russo, and H. Tanaka, Science Advances 5, eaav6090 (2019).
  * Koumakis  _et al._ [2015] N. Koumakis, E. Moghimi, R. Besseling, W. C. Poon, J. F. Brady, and G. Petekidis, Soft Matter 11, 4640 (2015).
  * Sciortino  _et al._ [2004] F. Sciortino, S. Mossa, E. Zaccarelli, and P. Tartaglia, Physical review letters 93, 055701 (2004).


v^{\star}+\frac{x}{\sqrt{n}}\right)\Big{\|}_{2}^{2}\varphi_{n}(\mathrm{d}x)$
$\displaystyle=\alpha^{2}\bigg{(}1+O\bigg{(}\frac{1}{\alpha}\sqrt{\frac{k\log
n}{n}}\bigg{)}\bigg{)};$ $\displaystyle\alpha
v^{\star\top}\int\mathsf{ST}_{\tau_{t}}\left(\alpha
v^{\star}+\frac{x}{\sqrt{n}}\right)\varphi_{n}(\mathrm{d}x)$
$\displaystyle=\alpha^{2}\bigg{(}1+O\bigg{(}\frac{1}{\alpha}\sqrt{\frac{k\log
n}{n}}\bigg{)}\bigg{)}.$

This implies (334), thus completing the proof of (331). Consequently, we
complete the inductive step.

It remains to verify the base case for (278), which is postponed to Section
F.4.3.

####  F.4.2 Bounding $\alpha_{t+1}-\alpha_{t+1}^{\star}$

Another condition claimed in Theorem 5 is the bound (41b) on the difference
between $\alpha_{t+1}$ and $\alpha_{t+1}^{\star}$, which we study in this
subsection. In order to understand the dynamics of $\alpha_{t}$, it remains to
understand the property of the function $f(\cdot)$ defined in (37). A little
algebra yields

$\displaystyle\frac{\mathrm{d}f(\alpha)}{\partial{\alpha}}=\frac{\lambda
v^{\star\top}\displaystyle\int
v^{\star}\circ\operatorname{\mathds{1}}\left(\Big{|}\alpha
v^{\star}+\frac{x}{\sqrt{n}}\Big{|}>\tau_{t}1\right)\varphi_{n}(\mathrm{d}x)}{\left(\displaystyle\int\Big{\|}\mathsf{ST}_{\tau_{t}}\left(\alpha
v^{\star}+\frac{x}{\sqrt{n}}\right)\Big{\|}_{2}^{2}\varphi_{n}(\mathrm{d}x)\right)^{1/2}}-\frac{\lambda\left(v^{\star\top}\displaystyle\int\mathsf{ST}_{\tau_{t}}\left(\alpha
v^{\star}+\frac{x}{\sqrt{n}}\right)\varphi_{n}(\mathrm{d}x)\right)^{2}}{\left(\displaystyle\int\Big{\|}\mathsf{ST}_{\tau_{t}}\left(\alpha
v^{\star}+\frac{x}{\sqrt{n}}\right)\Big{\|}_{2}^{2}\varphi_{n}(\mathrm{d}x)\right)^{3/2}}\geq
0,$

where the last inequality follows from the elementary relation
$\mathbb{E}[X^{2}]\cdot\mathbb{E}[Y^{2}]\geq\big{(}\mathbb{E}[XY]\big{)}^{2}$.

In addition, we make the observation that every
$\alpha=\lambda+O\Big{(}\sqrt{\frac{t\log^{3}n+k\log n}{n}}\Big{)}$ obeys

$\displaystyle\frac{\mathrm{d}f(\alpha)}{\partial{\alpha}}$
$\displaystyle\leq\frac{\lambda\left(\displaystyle\int\Big{\|}\mathsf{ST}_{\tau_{t}}\left(\alpha
v^{\star}+\frac{x}{\sqrt{n}}\right)\Big{\|}_{2}^{2}\varphi_{n}(\mathrm{d}x)\right)-\lambda\left(v^{\star\top}\displaystyle\int\mathsf{ST}_{\tau_{t}}\left(\alpha
v^{\star}+\frac{x}{\sqrt{n}}\right)\varphi_{n}(\mathrm{d}x)\right)^{2}}{\left(\displaystyle\int\Big{\|}\mathsf{ST}_{\tau_{t}}\left(\alpha
v^{\star}+\frac{x}{\sqrt{n}}\right)\Big{\|}_{2}^{2}\varphi_{n}(\mathrm{d}x)\right)^{3/2}}$
$\displaystyle\leq\frac{\lambda\left(\lambda^{2}+O\Big{(}\lambda\sqrt{\frac{k\log
n+t\log^{3}n}{n}}\Big{)}\right)-\lambda\left(\lambda-O\Big{(}\lambda\sqrt{\frac{k\log
n+t\log^{3}n}{n}}\Big{)}\right)^{2}}{\left(\lambda^{2}-O\Big{(}\lambda\sqrt{\frac{k\log
n+t\log^{3}n}{n}}\Big{)}\right)^{3/2}}$
$\displaystyle\lesssim\sqrt{\frac{k\log
n+t\log^{3}n}{n\lambda^{2}}}\leq\frac{1}{2},$

where the second line follows from (F.4.1) and (F.4.1), and the last line is
valid under the assumptions (324).

Based on the above properties, we further claim that $f(\alpha)=\alpha$ has
one solution — denoted by $\alpha^{\star}$ — within the range
$[\lambda/10,\lambda]$. In order to see this, recall that in (334), we have
shown that for any given $\alpha\asymp\lambda$,

$\displaystyle f(\alpha)=\frac{\lambda
v^{\star\top}\displaystyle\int\mathsf{ST}_{\tau_{t}}\left(\alpha
v^{\star}+\frac{x}{\sqrt{n}}\right)\varphi_{n}(\mathrm{d}x)}{\sqrt{\displaystyle\int\Big{\|}\mathsf{ST}_{\tau_{t}}\left(\alpha
v^{\star}+\frac{x}{\sqrt{n}}\right)\Big{\|}_{2}^{2}\varphi_{n}(\mathrm{d}x)}}=\bigg{(}1+O\bigg{(}\sqrt{\frac{k\log
n+t\log^{3}n}{n\lambda^{2}}}\bigg{)}\bigg{)}\lambda,$ (338)

where we invoke the assumption that $\frac{k\log n}{n\lambda^{2}}\ll 1$. In
particular, by taking $\alpha=\frac{1}{10}\lambda$, we can deduce that

$\displaystyle
f\Big{(}\frac{1}{10}\lambda\Big{)}=\big{(}1+o(1)\big{)}\lambda>\frac{1}{10}\lambda.$

In addition, it is easily seen that

$\displaystyle
f(\lambda)\leq\frac{\lambda\|v^{\star}\|_{2}\sqrt{\displaystyle\int\Big{\|}\mathsf{ST}_{\tau_{t}}\left(\alpha
v^{\star}+\frac{x}{\sqrt{n}}\right)\Big{\|}_{2}^{2}\varphi_{n}(\mathrm{d}x)}}{\sqrt{\displaystyle\int\Big{\|}\mathsf{ST}_{\tau_{t}}\left(\alpha
v^{\star}+\frac{x}{\sqrt{n}}\right)\Big{\|}_{2}^{2}\varphi_{n}(\mathrm{d}x)}}=\lambda.$

Given that $\frac{\mathrm{d}f(\alpha)}{\partial{\alpha}}\in[0,1/2]$ for any
$\alpha\in[\lambda/10,\lambda]$, we conclude that there exists a unique point
within $[\lambda/10,\lambda]$ obeying $f({\alpha})=\alpha$.

Hence, for any $t$ such that
$\alpha_{t}=\lambda+O\Big{(}\sqrt{\frac{t\log^{3}n+k\log n}{n}}\Big{)}$
obeying

$\displaystyle\big{|}\alpha_{t}-\alpha_{t}^{\star}\big{|}\leq
C_{6}\sqrt{\frac{k\log n+t\log^{3}n}{n}}$

for some large enough constant $C_{6}>0$, one can invoke
$\alpha^{\star}_{t+1}=f(\alpha^{\star}_{t})$ to deduce that

$\displaystyle\big{|}\alpha_{t+1}-\alpha_{t+1}^{\star}\big{|}$
$\displaystyle\leq\big{|}f(\alpha_{t})-f(\alpha_{t}^{\star})\big{|}+C_{7}\sqrt{\frac{k\log
n+t\log^{3}n}{n}}$
$\displaystyle\leq\frac{1}{2}\big{|}\alpha_{t}-\alpha_{t}^{\star}\big{|}+C_{7}\sqrt{\frac{k\log
n+t\log^{3}n}{n}}\leq C_{6}\sqrt{\frac{k\log n+t\log^{3}n}{n}}$

provided that $C_{6}>2C_{7}$, where we recall that each $\alpha_{t}$ satisfies
(331) shortly after initialization. Invoking the above relation recursively
leads to

$\displaystyle\big{|}\alpha_{t+1}-\alpha_{t+1}^{\star}\big{|}\lesssim\sqrt{\frac{k\log
n+t\log^{3}n}{n}},$

thus establishing the advertised bound (41b).

####  F.4.3 Initial condition for (278) with two initialization paradigms

In order to conclude the proof, we still need to verify whether the induction
hypotheses (278) hold at the initial stage of the algorithm. In what follows,
we shall look at two types of initialization schemes separately.

  * •

Suppose now that we have access to an initialization point $x_{1}$ independent
of $W$ such that $\langle v^{\star},\,\eta_{1}(x_{1})\rangle\asymp 1$, as
assumed in Theorem 5. In this case, one can see that

$\displaystyle x_{2}=M\eta_{1}(x_{1})$ $\displaystyle=\big{(}\lambda
v^{\star}v^{\star\top}+W\big{)}\eta_{1}(x_{1})=\lambda\langle
v^{\star},\,\eta_{1}(x_{1})\rangle\cdot v^{\star}+W\eta_{1}(x_{1})$
$\displaystyle=\alpha_{2}v^{\star}+\phi_{1}+\xi_{1},$

where

$\displaystyle\alpha_{2}$ $\displaystyle\coloneqq\lambda\langle
v^{\star},\,\eta_{1}(x_{1})\rangle\asymp\lambda,$ $\displaystyle\phi_{1}$
$\displaystyle\coloneqq W\eta_{1}(x_{1})+\zeta_{1},$
$\displaystyle-\xi_{1}=\zeta_{1}$
$\displaystyle\coloneqq\Big{(}\frac{\sqrt{2}}{2}-1\Big{)}\Big{(}\eta_{1}(x_{1})^{\top}W\eta_{1}(x_{1})\Big{)}\eta_{1}(x_{1}).$

As discussed in Lemma 2 and in (114), we have
$\phi_{1}\sim\mathcal{N}(0,\frac{1}{n}I_{n})$ and
$\eta_{1}(x_{1})^{\top}W\eta_{1}(x_{1})\sim\mathcal{N}(0,\frac{2}{n})$, where
we have used the fact that $\|\eta_{1}(x_{1})\|_{2}=1$. Therefore, it holds
that $\|\xi_{1}\|_{2}\leq\sqrt{\frac{\log n}{n}}$ with probability at least
$1-O(n^{-11})$. As a result, we have established the induction hypotheses
(278) for $t=2$, as required by Theorem 5.

  * •

Another type of initialization schemes considered in this paper is (267),
which concerns Corollary 4. By definition, index $\hat{s}$ is selected by
maximizing the diagonal entries of $M$, resulting in statistical dependence
between $x_{1}$ and $W$. As a consequence, Theorem 2 is not directly
applicable. To cope with the statistical dependency, let us generate an AMP
sequence starting from $e_{s}$ for each given $s\in\mathcal{S}_{0}$. For each
of these AMP sequences, it turns out that the initial condition for (278) when
$t=3$ is satisfied, which is formulated in the result below. The proof of this
lemma can be found in Section F.7.

######  Lemma 15.

Consider the AMP procedure initialized with $\eta_{0}(x_{0})=0$ and
$x_{1}=e_{s}$ for any given $s\in\mathcal{S}_{0}$ (cf. (268)). With
probability at least $1-O(n^{-11})$, the iterate $x_{3}$ admits the following
decomposition:

$\displaystyle
x_{3}=\alpha_{3}v^{\star}+\beta_{2}^{1}\phi_{1}+\beta_{2}^{2}\phi_{2}+\xi_{2},$

where $\phi_{1}$ and $\phi_{2}$ are i.i.d. drawn from
$\mathcal{N}\big{(}0,\frac{1}{n}I_{n}\big{)}$, and

$\displaystyle\alpha_{3}=\lambda
v^{\star\top}\eta_{2}(x_{2})\asymp\lambda~{}~{}\text{ and
}~{}~{}\|\xi_{2}\|_{2}\lesssim\sqrt{\frac{\log n}{n}}.$ (339)

Taking a simple union bound over all $s\in\mathcal{S}_{0}$, we conclude that
with probability at least $1-O(n^{-10})$, the initial condition (278) is
satisfied for $t=3$ if AMP is initialized at $e_{s}$ for any
$s\in\mathcal{S}_{0}$, thus making Theorem 5) applicable. Further, Proposition
1 guarantees that $\mathbb{P}(\hat{s}\in\mathcal{S}_{0})\geq 1-O(n^{-11}).$
Putting these together, we can guarantee that the AMP initialized at
$e_{\hat{s}}$ yields the required decomposition with probability at least
$1-O(n^{-10})$, as claimed in Corollary 4.

In summary, putting the above two initial conditions together with the
previous inductive steps finishes the proof of Theorem 5 and Corollary 4.

####  F.4.4 Implications for $\ell_{2}$ estimation accuracy

Our theory reveals the $\ell_{2}$ estimation accuracy of AMP, which we briefly
discuss in this subsection. Consider the estimator
$\frac{1}{\lambda}\mathsf{ST}_{\tau_{t}}\left(x_{t}\right)$ and look at its
$\ell_{2}$ estimation error. The triangle inequality directly implies

$\displaystyle\left\|\mathsf{ST}_{\tau_{t}}\left(x_{t}\right)-\lambda
v^{\star}\right\|_{2}$
$\displaystyle\leq\left\|\mathsf{ST}_{\tau_{t}}\left(x_{t}\right)-\mathsf{ST}_{\tau_{t}}\left(v_{t}\right)\right\|_{2}+\left\|\mathsf{ST}_{\tau_{t}}\left(v_{t}\right)-\alpha_{t}v^{\star}\right\|_{2}+\left\|\alpha_{t}v^{\star}-\lambda
v^{\star}\right\|_{2}$
$\displaystyle\leq\|\xi_{t-1}\|_{2}+\left\|\mathsf{ST}_{\tau_{t}}\left(v_{t}\right)-\alpha_{t}v^{\star}\right\|_{2}+|\alpha_{t}-\lambda|$
$\displaystyle\leq\left\|\mathsf{ST}_{\tau_{t}}\left(v_{t}\right)-\alpha_{t}v^{\star}\right\|_{2}+O\left(\sqrt{\frac{k\log
n+t\log^{3}n}{n}}\right)$

with probability at least $1-O(n^{-11})$, where the last step follows from
Theorem 5 and inequality (331).

Now consider the Lipschitz function
$f(x)\coloneqq\|\mathsf{ST}_{\tau_{t}}(\alpha_{t}v^{\star}+x)-\alpha_{t}v^{\star}\|_{2},~{}x\in{}^{n}$.
Inequality (105) yields

$\displaystyle\Big{\|}\mathsf{ST}_{\tau_{t}}\Big{(}\alpha_{t}v^{\star}+\sum_{j=1}^{t-1}\beta_{t-1}^{j}\phi_{j}\Big{)}-\alpha_{t}v^{\star}\Big{\|}_{2}-\mathbb{E}_{g\sim\mathcal{N}(0,\frac{1}{n}I_{n})}\Big{[}\left\|\mathsf{ST}_{\tau_{t}}\big{(}\alpha_{t}v^{\star}+g\big{)}-\alpha_{t}v^{\star}\right\|_{2}\Big{]}\lesssim\sqrt{\frac{t\log
n}{n}}$

holds with probability at least $1-O(n^{-11})$. In addition, in view of
(F.4.1) (taking $\alpha=\alpha_{t}$), we can deduce

$\displaystyle\mathbb{E}_{g\sim\mathcal{N}(0,\frac{1}{n}I_{n})}\Big{[}\left\|\mathsf{ST}_{\tau_{t}}\big{(}\alpha_{t}v^{\star}+g\big{)}-\alpha_{t}v^{\star}\right\|_{2}\Big{]}\lesssim\sqrt{\frac{k\log
n}{n}}.$

Putting these pieces together ensures that, with probability at least
$1-O(n^{-11})$,

$\displaystyle\Big{\|}\frac{1}{\lambda}\mathsf{ST}_{\tau_{t}}\left(x_{t}\right)-v^{\star}\Big{\|}_{2}\lesssim\sqrt{\frac{k\log
n+t\log^{3}n}{n\lambda^{2}}}.$ (340)

###  F.5 Proof of Proposition 1

Let us begin by considering the magnitude of $\langle
v^{\star},\eta_{2}(x_{2})\rangle$, which is the focus of the claim (269). From
the AMP iteration (3), it is seen that

$\displaystyle x_{2}=M\eta_{1}(x_{1})=\Big{(}\lambda
v^{\star}\big{(}v^{\star}\big{)}^{\top}+W\Big{)}e_{s}=\lambda
v^{\star}_{s}v^{\star}+We_{s},$ (341)

where we note that $\eta_{1}(x_{1})=e_{s}$ as a consequence of the denoising
function (36b). Recognizing that each $W_{ii}$ (resp. $W_{ij}$ with $i\neq j$)
is an independent Gaussian random variable with variance $2/n$ (resp. $1/n$),
one can invoke standard Gaussian concentration results to obtain (Vershynin,,
2018, Chapter 2.6)

$\displaystyle\max_{1\leq i,j\leq n}\left|\big{(}We_{j}\big{)}_{i}\right|\leq
6\sqrt{\frac{\log n}{n}}$ (342)

with probability at least $1-O(n^{-11})$. Therefore, if
$\lambda|v^{\star}_{s}|\geq 12\sqrt{\frac{k\log n}{n}}$, then it follows from
(342) that

$\displaystyle|x_{2,i}|\geq|\lambda
v^{\star}_{s}|\cdot|v_{i}^{\star}|-\big{|}\big{(}We_{j}\big{)}_{i}\big{|}$
$\displaystyle>6\sqrt{\frac{\log n}{n}},\qquad\text{if
}|v^{\star}_{i}|\geq\frac{1}{2\sqrt{k}};$
$\displaystyle|x_{2,i}|\leq\big{|}\big{(}We_{j}\big{)}_{i}\big{|}$
$\displaystyle\leq 6\sqrt{\frac{\log n}{n}},\qquad\text{if }v^{\star}_{i}=0.$

In the meantime, the above argument also reveals that

$\displaystyle\mathrm{sign}(x_{2,i})$
$\displaystyle=\mathrm{sign}(v^{\star}_{i}),\qquad$ $\displaystyle\text{if
}|x_{2,i}|>6\sqrt{\frac{\log n}{n}};$
$\displaystyle\big{(}|x_{2,i}|-\tau_{2}\big{)}_{+}$ $\displaystyle=0,\qquad$
$\displaystyle\text{if }|x_{2,i}|\leq 6\sqrt{\frac{\log n}{n}}.$

With the preceding observations in place, we can demonstrate that

$\displaystyle\Big{\|}\mathrm{sign}(x_{2})\circ(|x_{2}|-\tau_{2}1)_{+}\Big{\|}_{2}^{2}$
$\displaystyle\leq\sum_{i=1}^{n}x_{2,i}^{2}\operatorname{\mathds{1}}\Big{(}|x_{2,i}|\gtrsim\sqrt{\frac{\log
n}{n}}\Big{)}\lesssim\sum_{i:v^{\star}_{i}\neq 0}\Big{(}|\lambda
v^{\star}_{s}v^{\star}_{i}|+\sqrt{\frac{\log n}{n}}\Big{)}^{2}$
$\displaystyle\lesssim\left(\lambda v^{\star}_{s}\right)^{2}+\frac{k\log
n}{n}\asymp\left(\lambda v^{\star}_{s}\right)^{2}$

under the assumption that $\lambda|v^{\star}_{s}|\geq 12\sqrt{\frac{k\log
n}{n}}$. In addition, the above properties also reveal that:

$\displaystyle\big{|}\langle
v^{\star},\mathrm{sign}(x_{2})\circ(|x_{2}|-\tau_{2}1)_{+}\rangle\big{|}$
$\displaystyle=\sum_{i:|x_{2,i}|>6\sqrt{\frac{\log
n}{n}}}\left(|x_{2,i}|-\tau_{2}\right)|v^{\star}_{i}|\geq\sum_{i:|v^{\star}_{i}|\geq\frac{1}{2\sqrt{k}}}\left(|x_{2,i}|-\tau_{2}\right)|v^{\star}_{i}|$
$\displaystyle\geq\frac{1}{2}\sum_{i:|v^{\star}_{i}|\geq\frac{1}{2\sqrt{k}}}|x_{2,i}|\cdot|v^{\star}_{i}|\gtrsim\sum_{i:|v^{\star}_{i}|\geq\frac{1}{2\sqrt{k}}}|\lambda
v^{\star}_{s}|\,v_{i}^{\star 2}\gtrsim\lambda|v^{\star}_{s}|,$ (343)

where the last line follows from the assumption $\lambda|v^{\star}_{s}|\geq
C_{5}\sqrt{\frac{k\log n}{n}}$ for some large enough constant $C_{5}>0$ (so
that $|x_{2,i}|\geq 2\tau_{2}$), as well as the following condition (using the
$k$-sparse property of $v^{\star}$)

$\displaystyle\sum_{i:|v^{\star}_{i}|\geq\frac{1}{2\sqrt{k}}}v_{i}^{\star
2}=1-\sum_{i:|v^{\star}_{i}|<\frac{1}{2\sqrt{k}}}v_{i}^{\star 2}\geq
1-k\cdot\bigg{(}\frac{1}{2\sqrt{k}}\bigg{)}^{2}=\frac{3}{4}.$ (344)

Putting the above pieces together and recalling that
$\|\eta_{(}x_{2})\|_{2}=1$, we conclude that

$\displaystyle\big{|}\langle
v^{\star},\,\eta_{2}(x_{2})\rangle\big{|}=\frac{\big{|}\langle
v^{\star},\mathrm{sign}(x_{2})\circ(|x_{2}|-\tau_{2}1)_{+}\rangle\big{|}}{\left\|\mathrm{sign}(x_{2})\circ(|x_{2}|-\tau_{2}1)_{+}\right\|_{2}}\asymp
1.$

Next, we turn to proving the second claim of Proposition 1, towards which we
would like to show that with probability at least $1-O(n^{-11})$,

$\displaystyle|\langle
x_{1},v^{\star}\rangle|=|v^{\star}_{\hat{s}}|\geq\frac{1}{2}\|v^{\star}\|_{\infty},$
(345)

where $\hat{s}\coloneqq\arg\max_{i}\left|M_{ii}\right|$ and
$x_{1}=e_{\hat{s}}$. Indeed, it follows from (342) that

$\displaystyle\lambda\big{(}v^{\star}_{i}\big{)}^{2}-6\sqrt{\frac{\log
n}{n}}\leq\Big{|}\big{(}\lambda
v^{\star}v^{\star\top}+W\big{)}_{ii}\Big{|}\leq\lambda\big{(}v^{\star}_{i}\big{)}^{2}+6\sqrt{\frac{\log
n}{n}}$

with probability at least $1-O(n^{-11})$. Given that $\hat{s}$ maximizes
$|(\lambda v^{\star}v^{\star\top}+W)_{ii}|$ over all $i\in[n]$, we have

$\displaystyle\lambda\big{(}v^{\star}_{\hat{s}}\big{)}^{2}+6\sqrt{\frac{\log
n}{n}}\geq\Big{|}\left(\lambda
v^{\star}v^{\star\top}+W\right)_{\hat{s}\hat{s}}\Big{|}\geq\Big{|}\big{(}\lambda
v^{\star}v^{\star\top}+W\big{)}_{jj}\Big{|}\geq\lambda\big{(}v^{\star}_{\max}\big{)}^{2}-6\sqrt{\frac{\log
n}{n}},\quad\text{with }j\coloneqq\arg\\!\max_{i}|v^{\star}_{i}|.$

In the case when $\lambda\|v^{\star}\|_{\infty}\gtrsim\sqrt{\frac{k\log
n}{n}}$, the above inequality immediately establishes (345) by observing that
$\|v^{\star}\|_{\infty}\geq\sqrt{\frac{\|v^{\star}\|_{2}^{2}}{k}}=\frac{1}{\sqrt{k}}.$
We have thus completed the proof of Proposition 1.

###  F.6 Proof of Proposition 2

For notational convenience, we omit the index of $j$ in $\mathcal{I}_{j}$ and
write $\mathcal{I}$ instead throughout this proof, as long as it is clear from
the context.

##### Step 1: analysis for a single round.

Let us first state some concentration properties regarding
$v^{\star}_{\mathcal{I}}$. By construction, $\|v^{\star}_{\mathcal{I}}\|_{0}$
can be viewed as the sum of $k$ independent Bernoulli random variables, each
of which has mean $p$. The Bernstein inequality tells us that

$\displaystyle\Big{|}\big{\|}v^{\star}_{\mathcal{I}}\big{\|}_{0}-kp\Big{|}\leq\sqrt{2kp(1-p)\log\frac{2}{\delta}}+2\log\frac{2}{\delta}$

holds with probability at least $1-\delta$. It thus implies that

$\big{\|}v^{\star}_{\mathcal{I}}\big{\|}_{0}-pk=o(pk)$

under the assumption that $kp\gtrsim\log n\gg\log\frac{2}{\delta}$ and
$\delta\asymp 1$ (e.g., $\delta=\frac{1}{10}$). In addition,
$\|v^{\star}_{\mathcal{I}}\big{\|}_{2}^{2}=\sum_{i\in\text{supp}(v^{\star})}v^{\star
2}_{i}\operatorname{\mathds{1}}(i\in\mathcal{I})$ is the sum of $k$
independent bounded random variables, with total variance bounded above by

$\mathsf{Var}\big{(}\|v^{\star}_{\mathcal{I}}\big{\|}_{2}^{2}\big{)}\leq
p\big{\|}v^{\star}_{\mathcal{I}}\big{\|}_{\infty}^{2}\sum_{i\in\text{supp}(v^{\star})}v^{\star
2}_{i}=p\big{\|}v^{\star}_{\mathcal{I}}\big{\|}_{\infty}^{2}.$

Invoking Bernstein’s inequality again gives

$\displaystyle\left|\big{\|}v^{\star}_{\mathcal{I}}\big{\|}_{2}^{2}-p\right|\leq\big{\|}v^{\star}_{\mathcal{I}}\big{\|}_{\infty}\sqrt{2p\log\frac{2}{\delta}}+2\big{\|}v^{\star}_{\mathcal{I}}\big{\|}_{\infty}^{2}\log\frac{2}{\delta},$

with probability at least $1-\delta$. Consequently, it guarantees that with
probability $1-\delta$,

$\displaystyle\|v^{\star}_{\mathcal{I}}\big{\|}_{2}^{2}-p=o(p)~{}\text{ and
}~{}\|v^{\star}_{\mathcal{I}^{c}}\big{\|}_{2}^{2}=1-p+o(p),$ (346)

under the assumption that $\|v^{\star}\|_{\infty}=o\big{(}\sqrt{\frac{\log
n}{k}}\big{)}$ and $p\gtrsim\frac{\log n}{k}$. Combining the above two
relations gives

$\displaystyle\lambda\big{\|}v^{\star}_{\mathcal{I}}\big{\|}_{2}^{2}~{}\gtrsim~{}\frac{\big{\|}v^{\star}_{\mathcal{I}}\big{\|}_{0}}{\sqrt{n}},$
(347)

with the proviso that $\lambda\gtrsim k/\sqrt{n}.$

Suppose now that there exists an oracle algorithm (as in (271)) whose returned
solution $v_{\mathcal{I}}=\mathsf{Oracle}(M_{\mathcal{I},\mathcal{I}})$
(computed solely based on $M_{\mathcal{I},\mathcal{I}}$) satisfies

$\displaystyle\langle
v^{\star}_{\mathcal{I}},v_{\mathcal{I}}\rangle\asymp\big{\|}v^{\star}_{\mathcal{I}}\big{\|}_{2}\asymp\sqrt{p}$

with probability at least $1-\delta$ for some small constant $\delta$ (note
that the randomness comes from the sampling process). Taking $v\coloneqq
M_{\mathcal{I}^{c},\mathcal{I}}v_{\mathcal{I}}$ yields

$\displaystyle v=M_{\mathcal{I}^{c},\mathcal{I}}v_{\mathcal{I}}=(\lambda
v^{\star}_{\mathcal{I}^{c}}v_{\mathcal{I}}^{\star\top}+W_{\mathcal{I}^{c},\mathcal{I}})v_{\mathcal{I}}=\alpha_{1}v_{\mathcal{I}^{c}}^{\star}+\phi_{0},$
(348)

where $\alpha_{1}=\lambda\langle
v^{\star}_{\mathcal{I}},v_{\mathcal{I}}\rangle\asymp\lambda\sqrt{p}$ and
$\phi_{0}\sim\mathcal{N}(0,\frac{\|v_{\mathcal{I}}\|_{2}^{2}}{n}I)$.
Importantly, both $\alpha_{1}$ and $\phi_{0}$ are independent of
$W_{\mathcal{I}^{c},\mathcal{I}^{c}}$. Based on the construction (277) of
$x_{1}$, it suffices to verify

$\displaystyle\frac{\big{\langle}v_{\mathcal{I}^{c}}^{\star},\mathsf{ST}_{\tau_{1}}(v)\big{\rangle}}{\big{\|}v_{\mathcal{I}^{c}}^{\star}\big{\|}_{2}\big{\|}\mathsf{ST}_{\tau_{1}}(v)\big{\|}_{2}}\asymp
1.$ (349)

In order to validate (349), we look at the distributional of (348). First,
given the fact that $\|\phi_{0}\|_{\infty}\leq 6\sqrt{\frac{\log n}{n}}$ with
probability at least $1-O(n^{-11})$ and
$\alpha_{1}\asymp\lambda\sqrt{p}\gtrsim\sqrt{\frac{k\log
n\log\frac{1}{\delta}}{n}},$ we can use (348) to get

$\displaystyle\mathrm{sign}\big{(}\mathsf{ST}_{\tau_{1}}(v_{i})\big{)}=\mathrm{sign}\big{(}v^{\star}_{i}\big{)}\qquad\text{and}\qquad\begin{cases}\Big{|}\mathsf{ST}_{\tau_{1}}(v_{i})\Big{|}\geq\frac{1}{2}\alpha_{1}|v_{i}^{\star}|\mathds{1}\Big{(}\lambda\sqrt{p}|v_{i}^{\star}|\geq
C_{8}\sqrt{\frac{\log n}{n}}1\Big{)}\\\
\Big{|}\mathsf{ST}_{\tau_{1}}(v_{i})\Big{|}\leq
2\alpha_{1}|v_{i}^{\star}|\mathds{1}\Big{(}\lambda\sqrt{p}|v_{i}^{\star}|\geq
C_{7}\sqrt{\frac{\log n}{n}}1\Big{)}\end{cases}\qquad i\in\mathcal{I}^{c}$

for some suitable constants $C_{7},C_{8}>0$. As a result, we can see that

$\displaystyle\Big{\langle}v_{\mathcal{I}^{c}}^{\star},\frac{\mathsf{ST}_{\tau_{1}}(v)}{\|\mathsf{ST}_{\tau_{1}}(v)\|_{2}}\Big{\rangle}\gtrsim\frac{\alpha_{1}\sum_{i\in\mathcal{B}}v_{i}^{\star
2}}{\alpha_{1}\|v^{\star}\|_{2}}\qquad\text{with
}~{}\mathcal{B}\coloneqq\Big{\\{}i\mid i\in\mathcal{I}^{c};|v_{i}^{\star}|\geq
C_{8}\frac{\sqrt{\log n/n}}{\lambda\sqrt{p}}\Big{\\}}.$ (350)

Moreover, recalling the concentration results
$\|v^{\star}_{\mathcal{I}}\big{\|}_{2}^{2}-p=o(p)$ and
$\big{\|}v^{\star}_{\mathcal{I}}\big{\|}_{0}-pk=o(pk)$, we find that

$\displaystyle\sum_{i\in\mathcal{B}^{c}\cap\mathcal{I}^{c}}v_{i}^{\star 2}$
$\displaystyle=\Big{\|}v_{\mathcal{I}^{c}}\circ\operatorname{\mathds{1}}\Big{(}v_{\mathcal{I}^{c}}<\frac{C_{8}\sqrt{\log
n/n}}{\lambda\sqrt{p}}1\Big{)}\Big{\|}_{2}^{2}\leq\big{(}k-kp+o(kp)\big{)}\cdot\frac{C_{8}^{2}\log
n}{\lambda^{2}pn}$
$\displaystyle\leq\big{(}k-kp+o(kp)\big{)}\cdot\frac{C_{8}^{2}\log
n}{10C_{8}^{2}k\log
n\log\frac{1}{\delta}}\leq\frac{1-p}{10\log(1/\delta)}(1+o(1))\leq\frac{1}{10}\|v_{\mathcal{I}^{c}}^{\star}\|_{2}^{2},$

provided that $\lambda^{2}p\geq 10C_{8}^{2}\frac{k\log
n\log\frac{1}{\delta}}{n}$. Substitution into (350) gives

$\Big{\langle}v_{\mathcal{I}^{c}}^{\star},\frac{\mathsf{ST}_{\tau_{1}}(v)}{\|\mathsf{ST}_{\tau_{1}}(v)\|_{2}}\Big{\rangle}\gtrsim
1,$

which together with $\|v_{\mathcal{I}^{c}}\|_{2}\asymp 1$ establishes the
required inequality (349).

##### Step 2: repeating the procedure for $N$ times.

Thus far, we have proved that inequalities (346) and (349) are satisfied with
probability $1-\delta$, for $\delta$ being some small constant (e.g.,
$\delta=1/10$); here, the uncertainty comes from the random sampling process.
In order to boost the success probability, we — as detailed in Step 1 — repeat
the sampling procedure for $N\coloneqq 10\log n/\log(1/\delta)$ times,
outputing $N$ independent subsets
$\mathcal{I}_{1},\ldots,\mathcal{I}_{N}\subseteq[n]$ and $N$ corresponding
estimators (denoted by $v^{j}$ for $1\leq j\leq N$). Then there exists at
least one subset $\mathcal{I}_{j}$ such that, with probability at least
$1-\delta^{N}=1-O(n^{-10})$,

$\displaystyle\|v^{\star}_{\mathcal{I}^{c}}\big{\|}_{2}^{2}=1-p+o(p)\qquad\text{and}\qquad\frac{\big{\langle}v_{\mathcal{I}^{c}}^{\star},\mathsf{ST}_{\tau_{1}}(v^{j})\big{\rangle}}{\big{\|}v_{\mathcal{I}^{c}}^{\star}\big{\|}_{2}\big{\|}\mathsf{ST}_{\tau_{1}}(v^{j})\big{\|}_{2}}\asymp
1$ (351)

for $v^{j}\coloneqq
M_{\mathcal{I}_{j}^{c},\mathcal{I}_{j}}v_{\mathcal{I}_{j}}$. Based on these
two relations, we arrive at

$\displaystyle\frac{\mathsf{ST}_{\tau_{1}}(v^{j})^{\top}M_{\mathcal{I}_{j}^{c},\mathcal{I}_{j}^{c}}\mathsf{ST}_{\tau_{1}}(v^{j})}{\|\mathsf{ST}_{\tau_{1}}(v^{j})\|_{2}^{2}}$
$\displaystyle=\lambda\frac{\big{\langle}v_{\mathcal{I}_{j}^{c}}^{\star},\mathsf{ST}_{\tau_{1}}(v^{j})\big{\rangle}^{2}}{\big{\|}\mathsf{ST}_{\tau_{1}}(v^{j})\big{\|}^{2}_{2}}+\underbrace{\frac{\mathsf{ST}_{\tau_{1}}(v^{j})^{\top}W_{\mathcal{I}_{j}^{c}\mathcal{I}_{j}^{c}}\mathsf{ST}_{\tau_{1}}(v^{j})}{\big{\|}\mathsf{ST}_{\tau_{1}}(v^{j})\big{\|}^{2}_{2}}}_{=:\varepsilon_{j}}$
$\displaystyle=\lambda\frac{\big{\langle}v_{\mathcal{I}_{j}^{c}}^{\star},\mathsf{ST}_{\tau_{1}}(v^{j})\big{\rangle}^{2}}{\|v_{\mathcal{I}_{j}^{c}}^{\star}\|_{2}^{2}\big{\|}\mathsf{ST}_{\tau_{1}}(v^{j})\big{\|}^{2}_{2}}\cdot\|v_{\mathcal{I}_{j}^{c}}^{\star}\|_{2}^{2}+\varepsilon_{j}$
$\displaystyle\gtrsim\lambda(1-p)+\varepsilon_{j},\qquad\text{where
}\varepsilon_{j}\sim\mathcal{N}\Big{(}0,\frac{1}{n}\Big{)}$
$\displaystyle\asymp\lambda$ (352)

Here, we remind the readers that since $v^{j}$ is independent of
$W_{\mathcal{I}_{j}^{c}\mathcal{I}_{j}^{c}}$, and $\varepsilon_{j}$ follows a
Gaussian distribution $\mathcal{N}(0,\frac{1}{n}).$ We also make note of the
relation that $\lambda(1-p)\gtrsim\frac{k(1-p)}{\sqrt{n}}\gtrsim\frac{\log
n}{\sqrt{n}}$ and $\max_{1\leq j\leq N}|\varepsilon_{j}|\leq 5\sqrt{\frac{\log
N}{n}}$ with probability $1-O(n^{-11})$.

Therefore, if we select $\widehat{j}$ according to (277) as follows:

$\displaystyle\widehat{j}\coloneqq\arg\max_{j}~{}\Bigg{\\{}\frac{\mathsf{ST}_{\tau_{1}}(v^{j})^{\top}M_{\mathcal{I}_{j}^{c},\mathcal{I}_{j}^{c}}\mathsf{ST}_{\tau_{1}}(v^{j})}{\|\mathsf{ST}_{\tau_{1}}(v^{j})\|_{2}^{2}}\Bigg{\\}},$

then we necessarily have

$\displaystyle\frac{\big{\langle}v_{\mathcal{I}_{\widehat{j}}^{c}}^{\star},\mathsf{ST}_{\tau_{1}}(v^{\widehat{j}})\big{\rangle}}{\big{\|}v_{\mathcal{I}_{\widehat{j}}^{c}}^{\star}\big{\|}_{2}\big{\|}\mathsf{ST}_{\tau_{1}}(v^{\widehat{j}})\big{\|}_{2}}\asymp
1.$ (353)

Otherwise, we would end up with

$\displaystyle\frac{\mathsf{ST}_{\tau_{1}}(v^{\widehat{j}})^{\top}M_{\mathcal{I}^{c},\mathcal{I}^{c}}\mathsf{ST}_{\tau_{1}}(v^{\widehat{j}})}{\|\mathsf{ST}_{\tau_{1}}(v^{\widehat{j}})\|_{2}^{2}}$
$\displaystyle=\lambda\frac{\big{\langle}v_{\mathcal{I}_{\widehat{j}}^{c}}^{\star},\mathsf{ST}_{\tau_{1}}(v^{\widehat{j}})\big{\rangle}^{2}}{\big{\|}\mathsf{ST}_{\tau_{1}}(v^{\widehat{j}})\big{\|}^{2}_{2}}+\frac{\mathsf{ST}_{\tau_{1}}(v^{\widehat{j}})^{\top}W_{\mathcal{I}_{\widehat{j}}^{c}\mathcal{I}_{\widehat{j}}^{c}}\mathsf{ST}_{\tau_{1}}(v^{\widehat{j}})}{\big{\|}\mathsf{ST}_{\tau_{1}}(v^{\widehat{j}})\big{\|}^{2}_{2}}$
$\displaystyle\ll\lambda+\sqrt{\frac{\log n}{n}}$
$\displaystyle\lesssim\frac{\mathsf{ST}_{\tau_{1}}(v^{j})^{\top}M_{\mathcal{I}^{c},\mathcal{I}^{c}}\mathsf{ST}_{\tau_{1}}(x^{j}_{1})}{\|\mathsf{ST}_{\tau_{1}}(x^{j}_{1})\|_{2}^{2}},$

where $j$ corresponds to the one obeying (351). This, however, contradicts the
definition of $\widehat{j}.$ We have therefore concluded the proof of
Proposition 2.

###  F.7 Proof of Lemma 15

In this subsection, we analyze the first three AMP iterates when initialized
at $\eta_{0}(x_{0})=0$ and $x_{1}=e_{s}$ for any given $s\in\mathcal{S}_{0}$,
where
$\mathcal{S}_{0}\coloneqq\\{s\in[n]\mid|v^{\star}_{s}|\geq\frac{1}{2}\|v^{\star}\|_{\infty}\\}$
(defined in expression (268)). Without loss of generality, we shall assume
$v_{s}^{\star}>0$ throughout this subsection.

##### The 2nd iterate.

It follows from the AMP update rule that

$\displaystyle x_{2}=M\eta_{1}(x_{1})=\Big{(}\lambda
v^{\star}\big{(}v^{\star}\big{)}^{\top}+W\Big{)}e_{s}=\lambda
v^{\star}_{s}v^{\star}+We_{s},$

where we use $\eta_{1}(x_{1})=e_{s}$ in view of the definition of the
denoising function in (36b). Recalling that in the proof of Theorem 2, we
establish the decomposition (51) with $\phi_{j}$ and $\beta_{t}^{j}$ defined
in (47) and (44) respectively. Instantiating this to the current case, we have

$\beta_{1}^{1}=1\qquad\text{and}\qquad\phi_{1}=We_{s}+\Big{(}\frac{\sqrt{2}}{2}-1\Big{)}e_{s}^{\top}We_{s}\sim\mathcal{N}\Big{(}0,\frac{1}{n}I_{n}\Big{)}.$

Hence, $x_{2}$ can be expressed as

$\displaystyle x_{2}$ $\displaystyle=\alpha_{2}v^{\star}+\phi_{1}+\xi_{1},$
(354)

where $\alpha_{2}=\lambda v^{\star}_{s}\gtrsim\lambda$ obeying
$|\alpha_{2}|\geq\|v^{\star}\|_{\infty}$, and
$\xi_{1}=(1-\frac{\sqrt{2}}{2})(e_{s}^{\top}We_{s})e_{s}$.

To proceed, we find it helpful to make note of the following two properties.
First, from expression (F.5), we know that

$\displaystyle\gamma_{2}^{-1}=\big{\|}\mathrm{sign}(x_{2})\circ(|x_{2}|-\tau_{2}1)_{+}\big{\|}_{2}\geq\big{|}\langle
v^{\star},\mathrm{sign}(x_{2})\circ(|x_{2}|-\tau_{2}1)_{+}\rangle\big{|}\gtrsim\lambda|v^{\star}_{s}|.$
(355)

In addition, with probability at least $1-O(n^{-11})$, one can derive from
(342) that

$\displaystyle|\xi_{1,s}|=\Big{|}\Big{(}1-\frac{\sqrt{2}}{2}\Big{)}e_{s}^{\top}We_{s}\Big{|}\leq\max_{1\leq
i\leq n}|W_{ii}|\lesssim\sqrt{\frac{\log n}{n}}.$ (356)

##### The 3rd iterate.

In view of decomposition (51), we write

$\displaystyle x_{3}$
$\displaystyle=M\eta_{2}(x_{2})-\langle\eta_{2}^{\prime}(x_{2})\rangle\eta_{1}(x_{1})=\alpha_{3}v^{\star}+\beta_{2}^{1}\phi_{1}+\beta_{2}^{2}\phi_{2}+\xi_{2},$

where (see(55))

$\alpha_{3}=\lambda
v^{\star\top}\eta_{2}(x_{2})\qquad\text{and}\qquad\xi_{2}\in\mathsf{span}\\{e_{s},\eta_{2}(x_{2})\\}.$

Proposition 1 tells us that $\alpha_{3}\asymp\lambda.$

Next, we look at the size of $\|\xi_{2}\|_{2}.$ To begin with, by definition,
we have $\mu_{2}^{1}=\frac{\xi_{1}^{\top}e_{s}}{\|\xi_{1}\|_{2}}=1$ for
$\xi_{1}=(1-\frac{\sqrt{2}}{2})(e_{s}^{\top}We_{s})e_{s}$. Combining this with
relation (56) for $t=2$, we arrive at

$\displaystyle\|\xi_{2}\|_{2}=\langle\phi_{1},\delta_{2}\rangle-\langle\delta_{2}^{\prime}\rangle+\Delta_{2}+O\Big{(}\sqrt{\frac{\log
n}{n}}\Big{)},$ (357)

where $\delta_{2}$ takes the following form

$\displaystyle\delta_{2}=\eta_{2}(\alpha_{2}v^{\star}+\phi_{1}+\xi_{1})-\eta_{2}(\alpha_{2}v^{\star}+\phi_{1}).$

To control $\|\xi_{2}\|_{2}$, it then suffices to upper bound $\Delta_{2}$ as
well as $\langle\phi_{1},\delta_{2}\rangle-\langle\delta_{2}^{\prime}\rangle$.
Let us start with the quantity $\Delta_{2}$. Recall that $|\Delta_{2}|\leq
A_{2}\lesssim\sqrt{\frac{2\log n}{n}}$ (in view of (308)), where we remind the
readers that the proof of (308) is built upon the assumptions
$\alpha_{2}\lesssim\lambda$ and $\tau_{2}\asymp\sqrt{\frac{\log n}{n}}.$

We then move on to consider the quantity
$\langle\phi_{1},\delta_{2}\rangle-\langle\delta_{2}^{\prime}\rangle$. First,
given that $\xi_{1}$ is along the direction of $e_{s}$, the entries of
$\delta_{2}$ are all zero except for $\delta_{2,s}.$ With this observation in
mind, the term of interest can be written as

$\displaystyle\big{|}\langle\phi_{1},\delta_{2}\rangle-\langle\delta_{2}^{\prime}\rangle\big{|}$
$\displaystyle=\Big{|}\phi_{1,s}\delta_{2,s}-\frac{1}{n}\delta_{2,s}^{\prime}\Big{|}\lesssim\sqrt{\frac{\log
n}{n}}\cdot\frac{|\xi_{1,s}|}{\lambda v_{s}^{\star}}+\frac{1}{n\lambda
v_{s}^{\star}}.$ (358)

To see why the last inequality is valid, we use inequality (355) to obtain

$\displaystyle|\delta_{2,s}|=\big{|}\eta_{2}(\alpha_{2}v^{\star}_{s}+\phi_{1,s}+\xi_{1,s})-\eta_{2}(\alpha_{2}v^{\star}_{s}+\phi_{1,s})|\leq\gamma_{2}|\xi_{1,s}\big{|}\lesssim\frac{|\xi_{1,s}|}{\lambda
v^{\star}_{s}},$

as a result of the Lipschitz property of $\eta_{t}$, and in addition,

$\displaystyle|\delta_{2,s}^{\prime}|\leq 2\gamma_{2}\lesssim\frac{1}{\lambda
v^{\star}_{s}}.$

Taking inequality (358) together with (356) and recalling
$v^{\star}_{s}\gtrsim\frac{1}{\sqrt{k}}$ (cf. (269)) lead to

$\displaystyle\big{|}\langle\phi_{1},\delta_{2}\rangle-\langle\delta_{2}^{\prime}\rangle\big{|}$
$\displaystyle\lesssim\sqrt{\frac{\log n}{n}}\sqrt{\frac{k\log
n}{n\lambda^{2}}}+\frac{\sqrt{k}}{n\lambda}\lesssim\sqrt{\frac{\log n}{n}}.$

Substitution back into (357) gives

$\displaystyle\|\xi_{2}\|_{2}\lesssim\sqrt{\frac{\log n}{n}}.$

We have thus established Lemma 15.

## Acknowledgment

This work was partially supported by NSF grants DMS 2147546/2015447 and the
NSF CAREER award DMS-2143215. Part of this work was done while G. Li and Y.
Wei were visiting the Simons Institute for the Theory of Computing.

## References

  * Amini and Wainwright, (2008) Amini, A. A. and Wainwright, M. J. (2008).  High-dimensional analysis of semidefinite relaxations for sparse principal components.  In 2008 IEEE international symposium on information theory, pages 2454–2458. IEEE.
  * Aubin et al., (2020) Aubin, B., Loureiro, B., Baker, A., Krzakala, F., and Zdeborová, L. (2020).  Exact asymptotics for phase retrieval and compressed sensing with random generative priors.  In Mathematical and Scientific Machine Learning, pages 55–73. PMLR.
  * Bai and Yao, (2008) Bai, Z. and Yao, J.-f. (2008).  Central limit theorems for eigenvalues in a spiked population model.  In Annales de l’IHP Probabilités et statistiques, volume 44, pages 447–474.
  * Baik et al., (2005) Baik, J., Arous, G. B., and Péché, S. (2005).  Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices.  The Annals of Probability, 33(5):1643–1697.
  * Bandeira et al., (2019) Bandeira, A. S., Kunisky, D., and Wein, A. S. (2019).  Computational hardness of certifying bounds on constrained pca problems.  arXiv preprint arXiv:1902.07324.
  * Bandeira et al., (2018) Bandeira, A. S., Perry, A., and Wein, A. S. (2018).  Notes on computational-to-statistical gaps: predictions using statistical physics.  Portugaliae Mathematica, 75(2):159–186.
  * Bandeira and Van Handel, (2016) Bandeira, A. S. and Van Handel, R. (2016).  Sharp nonasymptotic bounds on the norm of random matrices with independent entries.  The Annals of Probability, 44(4):2479–2506.
  * Bao et al., (2021) Bao, Z., Ding, X., and Wang, K. (2021).  Singular vector and singular subspace distribution for the matrix denoising model.  The Annals of Statistics, 49(1):370–392.
  * Barbier et al., (2016) Barbier, J., Dia, M., Macris, N., and Krzakala, F. (2016).  The mutual information in random linear estimation.  In 2016 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 625–632. IEEE.
  * Barbier et al., (2019) Barbier, J., Krzakala, F., Macris, N., Miolane, L., and Zdeborová, L. (2019).  Optimal errors and phase transitions in high-dimensional generalized linear models.  Proceedings of the National Academy of Sciences, 116(12):5451–5460.
  * Bayati et al., (2015) Bayati, M., Lelarge, M., and Montanari, A. (2015).  Universality in polytope phase transitions and message passing algorithms.  The Annals of Applied Probability, 25(2):753–822.
  * (12) Bayati, M. and Montanari, A. (2011a).  The dynamics of message passing on dense graphs, with applications to compressed sensing.  IEEE Transactions on Information Theory, 57(2):764–785.
  * (13) Bayati, M. and Montanari, A. (2011b).  The LASSO risk for gaussian matrices.  IEEE Transactions on Information Theory, 58(4):1997–2017.
  * (14) Berthet, Q. and Rigollet, P. (2013a).  Computational lower bounds for sparse PCA.  arXiv preprint arXiv:1304.0828.
  * (15) Berthet, Q. and Rigollet, P. (2013b).  Optimal detection of sparse principal components in high dimension.  The Annals of Statistics, 41(4):1780–1815.
  * Bolthausen, (2009) Bolthausen, E. (2009).  On the high-temperature phase of the sherrington-kirkpatrick model.  In Seminar at EURANDOM, Eindhoven.
  * Borgerding and Schniter, (2016) Borgerding, M. and Schniter, P. (2016).  Onsager-corrected deep learning for sparse linear inverse problems.  In 2016 IEEE Global Conference on Signal and Information Processing (GlobalSIP), pages 227–231. IEEE.
  * Bu et al., (2020) Bu, Z., Klusowski, J. M., Rush, C., and Su, W. J. (2020).  Algorithmic analysis and statistical estimation of SLOPE via approximate message passing.  IEEE Transactions on Information Theory, 67(1):506–537.
  * Cai et al., (2015) Cai, T., Ma, Z., and Wu, Y. (2015).  Optimal estimation and rank detection for sparse spiked covariance matrices.  Probability theory and related fields, 161(3):781–815.
  * Candes et al., (2015) Candes, E. J., Li, X., and Soltanolkotabi, M. (2015).  Phase retrieval via Wirtinger flow: Theory and algorithms.  IEEE Transactions on Information Theory, 61(4):1985–2007.
  * Capitaine et al., (2009) Capitaine, M., Donati-Martin, C., and Féral, D. (2009).  The largest eigenvalues of finite rank deformation of large wigner matrices: convergence and nonuniversality of the fluctuations.  The Annals of Probability, 37(1):1–47.
  * Celentano et al., (2021) Celentano, M., Fan, Z., and Mei, S. (2021).  Local convexity of the TAP free energy and AMP convergence for $z_{2}$-synchronization.  arXiv preprint arXiv:2106.11428.
  * Celentano and Montanari, (2022) Celentano, M. and Montanari, A. (2022).  Fundamental barriers to high-dimensional regression with convex penalties.  The Annals of Statistics, 50(1):170–196.
  * Celentano et al., (2020) Celentano, M., Montanari, A., and Wei, Y. (2020).  The Lasso with general Gaussian designs with applications to hypothesis testing.  arXiv preprint arXiv:2007.13716.
  * Chen and Lam, (2021) Chen, W.-K. and Lam, W.-K. (2021).  Universality of approximate message passing algorithms.  Electronic Journal of Probability, 26:1–44.
  * (26) Chen, Y., Cheng, C., and Fan, J. (2021a).  Asymmetry helps: Eigenvalue and eigenvector analyses of asymmetrically perturbed low-rank matrices.  The Annals of statistics, 49(1):435.
  * (27) Chen, Y., Chi, Y., Fan, J., and Ma, C. (2021b).  Spectral methods for data science: A statistical perspective.  Foundations and Trends® in Machine Learning, 14(5):566–806.
  * Cheng et al., (2021) Cheng, C., Wei, Y., and Chen, Y. (2021).  Tackling small eigen-gaps: Fine-grained eigenvector estimation and inference under heteroscedastic noise.  IEEE Transactions on Information Theory, 67(11):7380–7419.
  * Chi et al., (2019) Chi, Y., Lu, Y. M., and Chen, Y. (2019).  Nonconvex optimization meets low-rank matrix factorization: An overview.  IEEE Transactions on Signal Processing, 67(20):5239–5269.
  * d’Aspremont et al., (2004) d’Aspremont, A., Ghaoui, L., Jordan, M., and Lanckriet, G. (2004).  A direct formulation for sparse PCA using semidefinite programming.  Advances in neural information processing systems, 17.
  * Deshpande et al., (2017) Deshpande, Y., Abbe, E., and Montanari, A. (2017).  Asymptotic mutual information for the balanced binary stochastic block model.  Information and Inference: A Journal of the IMA, 6(2):125–170.
  * (32) Deshpande, Y. and Montanari, A. (2014a).  Information-theoretically optimal sparse PCA.  In 2014 IEEE International Symposium on Information Theory, pages 2197–2201. IEEE.
  * (33) Deshpande, Y. and Montanari, A. (2014b).  Sparse PCA via covariance thresholding.  Advances in Neural Information Processing Systems, 27.
  * Deshpande et al., (2014) Deshpande, Y., Montanari, A., and Richard, E. (2014).  Cone-constrained principal component analysis.  Advances in Neural Information Processing Systems, 27.
  * Ding et al., (2019) Ding, Y., Kunisky, D., Wein, A. S., and Bandeira, A. S. (2019).  Subexponential-time algorithms for sparse PCA.  arXiv preprint arXiv:1907.11635.
  * Donoho and Montanari, (2016) Donoho, D. and Montanari, A. (2016).  High dimensional robust m-estimation: Asymptotic variance via approximate message passing.  Probability Theory and Related Fields, 166(3):935–969.
  * Donoho et al., (2013) Donoho, D. L., Javanmard, A., and Montanari, A. (2013).  Information-theoretically optimal compressed sensing via spatial coupling and approximate message passing.  IEEE transactions on information theory, 59(11):7434–7464.
  * Donoho et al., (2009) Donoho, D. L., Maleki, A., and Montanari, A. (2009).  Message-passing algorithms for compressed sensing.  Proceedings of the National Academy of Sciences, 106(45):18914–18919.
  * Donoho and Montanari, (2015) Donoho, D. L. and Montanari, A. (2015).  Variance breakdown of huber (m)-estimators: $n/p\rightarrow(1,\infty)$.  arXiv preprint arXiv:1503.02106.
  * Dudeja et al., (2022) Dudeja, R., Lu, Y. M., and Sen, S. (2022).  Universality of approximate message passing with semi-random matrices.  arXiv preprint arXiv:2204.04281.
  * El Alaoui et al., (2020) El Alaoui, A., Krzakala, F., and Jordan, M. (2020).  Fundamental limits of detection in the spiked wigner model.  The Annals of Statistics, 48(2):863–885.
  * El Karoui, (2018) El Karoui, N. (2018).  On the impact of predictor geometry on the performance on high-dimensional ridge-regularized generalized robust regression estimators.  Probability Theory and Related Fields, 170(1):95–175.
  * (43) Fan, J., Fan, Y., Han, X., and Lv, J. (2022a).  Asymptotic theory of eigenvectors for random matrices with diverging spikes.  Journal of the American Statistical Association, 117(538):996–1009.
  * Fan, (2022) Fan, Z. (2022).  Approximate message passing algorithms for rotationally invariant matrices.  The Annals of Statistics, 50(1):197–224.
  * (45) Fan, Z., Li, Y., and Sen, S. (2022b).  TAP equations for orthogonally invariant spin glasses at high temperature.  arXiv preprint arXiv:2202.09325.
  * Fan et al., (2021) Fan, Z., Mei, S., and Montanari, A. (2021).  TAP free energy, spin glasses and variational inference.  The Annals of Probability, 49(1):1–45.
  * Fan and Wu, (2021) Fan, Z. and Wu, Y. (2021).  The replica-symmetric free energy for Ising spin glasses with orthogonally invariant couplings.  arXiv preprint arXiv:2105.02797.
  * Feng et al., (2022) Feng, O. Y., Venkataramanan, R., Rush, C., Samworth, R. J., et al. (2022).  A unifying tutorial on approximate message passing.  Foundations and Trends® in Machine Learning, 15(4):335–536.
  * Féral and Péché, (2007) Féral, D. and Péché, S. (2007).  The largest eigenvalue of rank one deformation of large wigner matrices.  Communications in mathematical physics, 272(1):185–228.
  * Fletcher and Rangan, (2014) Fletcher, A. K. and Rangan, S. (2014).  Scalable inference for neuronal connectivity from calcium imaging.  Advances in neural information processing systems, 27.
  * Fletcher and Rangan, (2018) Fletcher, A. K. and Rangan, S. (2018).  Iterative reconstruction of rank-one matrices in noise.  Information and Inference: A Journal of the IMA, 7(3):531–562.
  * Gao and Zhang, (2022) Gao, C. and Zhang, A. Y. (2022).  SDP achieves exact minimax optimality in phase synchronization.  IEEE Transactions on Information Theory.
  * Hopkins et al., (2017) Hopkins, S. B., Kothari, P. K., Potechin, A., Raghavendra, P., Schramm, T., and Steurer, D. (2017).  The power of sum-of-squares for detecting hidden structures.  In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 720–731. IEEE.
  * Hsu et al., (2012) Hsu, D., Kakade, S., and Zhang, T. (2012).  A tail inequality for quadratic forms of subgaussian random vectors.  Electronic Communications in Probability, 17:1–6.
  * Hu and Lu, (2020) Hu, H. and Lu, Y. M. (2020).  Universality laws for high-dimensional learning with random features.  arXiv preprint arXiv:2009.07669.
  * Javanmard and Montanari, (2013) Javanmard, A. and Montanari, A. (2013).  State evolution for general approximate message passing algorithms, with applications to spatial coupling.  Information and Inference: A Journal of the IMA, 2(2):115–144.
  * Javanmard et al., (2016) Javanmard, A., Montanari, A., and Ricci-Tersenghi, F. (2016).  Phase transitions in semidefinite relaxations.  Proceedings of the National Academy of Sciences, 113(16):E2218–E2223.
  * Johnstone, (2001) Johnstone, I. M. (2001).  On the distribution of the largest eigenvalue in principal components analysis.  The Annals of statistics, 29(2):295–327.
  * Johnstone and Lu, (2009) Johnstone, I. M. and Lu, A. Y. (2009).  On consistency and sparsity for principal components analysis in high dimensions.  Journal of the American Statistical Association, 104(486):682–693.
  * Johnstone and Paul, (2018) Johnstone, I. M. and Paul, D. (2018).  Pca in high dimensions: An orientation.  Proceedings of the IEEE, 106(8):1277–1292.
  * Keshavan et al., (2010) Keshavan, R. H., Montanari, A., and Oh, S. (2010).  Matrix completion from noisy entries.  Journal of Machine Learning Research, 11:2057–2078.
  * Knowles and Yin, (2013) Knowles, A. and Yin, J. (2013).  The isotropic semicircle law and deformation of Wigner matrices.  Communications on Pure and Applied Mathematics, 66(11):1663–1749.
  * Krauthgamer et al., (2015) Krauthgamer, R., Nadler, B., and Vilenchik, D. (2015).  Do semidefinite relaxations solve sparse PCA up to the information limit?  The Annals of Statistics, 43(3):1300–1322.
  * Krzakala et al., (2016) Krzakala, F., Xu, J., and Zdeborová, L. (2016).  Mutual information in rank-one matrix estimation.  In 2016 IEEE Information Theory Workshop (ITW), pages 71–75. IEEE.
  * Lee et al., (2016) Lee, J. O., Schnelli, K., Stetler, B., and Yau, H.-T. (2016).  Bulk universality for deformed Wigner matrices.  The Annals of Probability, 44(3):2349–2425.
  * Lelarge and Miolane, (2019) Lelarge, M. and Miolane, L. (2019).  Fundamental limits of symmetric low-rank matrix estimation.  Probability Theory and Related Fields, 173(3):859–929.
  * Lesieur et al., (2015) Lesieur, T., Krzakala, F., and Zdeborová, L. (2015).  Phase transitions in sparse PCA.  In 2015 IEEE International Symposium on Information Theory (ISIT), pages 1635–1639. IEEE.
  * Lesieur et al., (2017) Lesieur, T., Krzakala, F., and Zdeborová, L. (2017).  Constrained low-rank matrix estimation: Phase transitions, approximate message passing and applications.  Journal of Statistical Mechanics: Theory and Experiment, 2017(7):073403.
  * Li et al., (2021) Li, G., Cai, C., Poor, H. V., and Chen, Y. (2021).  Minimax estimation of linear functions of eigenvectors in the face of small eigen-gaps.  arXiv preprint arXiv:2104.03298.
  * Li et al., (2023) Li, G., Fan, W., and Wei, Y. (2023).  Approximate message passing from random initialization with applications to $\mathbb{Z}_{2}$ synchronization.  arXiv preprint arXiv:2302.03682.
  * Li and Wei, (2021) Li, Y. and Wei, Y. (2021).  Minimum $\ell_{1}$-norm interpolators: Precise asymptotics and multiple descent.  arXiv preprint arXiv:2110.09502.
  * Ma et al., (2020) Ma, C., Wang, K., Chi, Y., and Chen, Y. (2020).  Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution.  Foundations of Computational Mathematics, 20(3):451–632.
  * Ma et al., (2018) Ma, J., Xu, J., and Maleki, A. (2018).  Optimization-based AMP for phase retrieval: The impact of initialization and $\ell_{2}$-regularization.  arXiv preprint arXiv:1801.01170.
  * Ma, (2013) Ma, Z. (2013).  Sparse principal component analysis and iterative thresholding.  The Annals of Statistics, 41(2):772–801.
  * Ma and Nandy, (2021) Ma, Z. and Nandy, S. (2021).  Community detection with contextual multilayer networks.  arXiv preprint arXiv:2104.02960.
  * Macris et al., (2020) Macris, N., Rush, C., et al. (2020).  All-or-nothing statistical and computational phase transitions in sparse spiked matrix estimation.  Advances in Neural Information Processing Systems, 33:14915–14926.
  * Massart, (2007) Massart, P. (2007).  Concentration inequalities and model selection: Ecole d’Eté de Probabilités de Saint-Flour XXXIII-2003.  Springer.
  * Mondelli and Venkataramanan, (2021) Mondelli, M. and Venkataramanan, R. (2021).  PCA initialization for approximate message passing in rotationally invariant models.  Advances in Neural Information Processing Systems, 34:29616–29629.
  * Montanari and Richard, (2015) Montanari, A. and Richard, E. (2015).  Non-negative principal component analysis: Message passing algorithms and sharp asymptotics.  IEEE Transactions on Information Theory, 62(3):1458–1484.
  * Montanari and Sen, (2016) Montanari, A. and Sen, S. (2016).  Semidefinite programs on sparse random graphs and their application to community detection.  In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 814–827.
  * Montanari and Venkataramanan, (2021) Montanari, A. and Venkataramanan, R. (2021).  Estimation of low-rank matrices via approximate message passing.  The Annals of Statistics, 49(1):321–345.
  * Oymak and Tropp, (2018) Oymak, S. and Tropp, J. A. (2018).  Universality laws for randomized dimension reduction, with applications.  Information and Inference: A Journal of the IMA, 7(3):337–446.
  * Péché, (2006) Péché, S. (2006).  The largest eigenvalue of small rank perturbations of hermitian random matrices.  Probability Theory and Related Fields, 134(1):127–173.
  * Peng, (2012) Peng, M. (2012).  Eigenvalues of deformed random matrices.  arXiv preprint arXiv:1205.0572.
  * (85) Perry, A., Wein, A. S., Bandeira, A. S., and Moitra, A. (2018a).  Message-passing algorithms for synchronization problems over compact groups.  Communications on Pure and Applied Mathematics, 71(11):2275–2322.
  * (86) Perry, A., Wein, A. S., Bandeira, A. S., and Moitra, A. (2018b).  Optimality and sub-optimality of PCA i: Spiked random matrix models.  The Annals of Statistics, 46(5):2416–2451.
  * Rangan and Fletcher, (2012) Rangan, S. and Fletcher, A. K. (2012).  Iterative estimation of constrained rank-one matrices in noise.  In 2012 IEEE International Symposium on Information Theory Proceedings, pages 1246–1250. IEEE.
  * Reeves and Pfister, (2019) Reeves, G. and Pfister, H. D. (2019).  The replica-symmetric prediction for random linear estimation with gaussian matrices is exact.  IEEE Transactions on Information Theory, 65(4):2252–2283.
  * Rudelson and Vershynin, (2013) Rudelson, M. and Vershynin, R. (2013).  Hanson-Wright inequality and sub-gaussian concentration.  Electronic Communications in Probability, 18:1–9.
  * Rush et al., (2017) Rush, C., Greig, A., and Venkataramanan, R. (2017).  Capacity-achieving sparse superposition codes via approximate message passing decoding.  IEEE Transactions on Information Theory, 63(3):1476–1500.
  * Rush and Venkataramanan, (2018) Rush, C. and Venkataramanan, R. (2018).  Finite sample analysis of approximate message passing algorithms.  IEEE Transactions on Information Theory, 64(11):7264–7286.
  * Schniter, (2011) Schniter, P. (2011).  A message-passing receiver for bicm-ofdm over unknown clustered-sparse channels.  IEEE Journal of Selected Topics in Signal Processing, 5(8):1462–1474.
  * Schniter and Rangan, (2014) Schniter, P. and Rangan, S. (2014).  Compressive phase retrieval via generalized approximate message passing.  IEEE Transactions on Signal Processing, 63(4):1043–1055.
  * Sellke, (2021) Sellke, M. (2021).  Optimizing mean field spin glasses with external field.  arXiv preprint arXiv:2105.03506.
  * Simchowitz et al., (2018) Simchowitz, M., El Alaoui, A., and Recht, B. (2018).  Tight query complexity lower bounds for PCA via finite sample deformed wigner law.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1249–1259.
  * Singer, (2011) Singer, A. (2011).  Angular synchronization by eigenvectors and semidefinite programming.  Applied and computational harmonic analysis, 30(1):20–36.
  * Sur and Candès, (2019) Sur, P. and Candès, E. J. (2019).  A modern maximum-likelihood theory for high-dimensional logistic regression.  Proceedings of the National Academy of Sciences, 116(29):14516–14525.
  * Sur et al., (2019) Sur, P., Chen, Y., and Candès, E. J. (2019).  The likelihood ratio test in high-dimensional logistic regression is asymptotically a rescaled chi-square.  Probability Theory and Related Fields, 175(1-2):487–558.
  * Thrampoulidis et al., (2018) Thrampoulidis, C., Abbasi, E., and Hassibi, B. (2018).  Precise error analysis of regularized $m$-estimators in high dimensions.  IEEE Transactions on Information Theory, 64(8):5592–5628.
  * Venkataramanan et al., (2021) Venkataramanan, R., Kögler, K., and Mondelli, M. (2021).  Estimation in rotationally invariant generalized linear models via approximate message passing.  arXiv preprint arXiv:2112.04330.
  * Vershynin, (2018) Vershynin, R. (2018).  High-dimensional probability: An introduction with applications in data science, volume 47.  Cambridge university press.
  * Vu and Lei, (2012) Vu, V. and Lei, J. (2012).  Minimax rates of estimation for sparse PCA in high dimensions.  In Artificial intelligence and statistics, pages 1278–1286. PMLR.
  * Vu et al., (2013) Vu, V. Q., Cho, J., Lei, J., and Rohe, K. (2013).  Fantope projection and selection: A near-optimal convex relaxation of sparse PCA.  Advances in neural information processing systems, 26.
  * Wainwright, (2019) Wainwright, M. J. (2019).  High-dimensional statistics: A non-asymptotic viewpoint, volume 48.  Cambridge University Press.
  * Wang et al., (2016) Wang, T., Berthet, Q., and Samworth, R. J. (2016).  Statistical and computational trade-offs in estimation of sparse principal components.  The Annals of Statistics, 44(5):1896–1930.
  * Wang et al., (2022) Wang, T., Zhong, X., and Fan, Z. (2022).  Universality of approximate message passing algorithms and tensor networks.  arXiv preprint arXiv:2206.13037.
  * Wei et al., (2019) Wei, Y., Wainwright, M. J., and Guntuboyina, A. (2019).  The geometry of hypothesis testing over convex cones: Generalized likelihood ratio tests and minimax radii.  The Annals of Statistics, 47(2):994–1024.
  * Yan et al., (2021) Yan, Y., Chen, Y., and Fan, J. (2021).  Inference for heteroskedastic PCA with missing data.  arXiv preprint arXiv:2107.12365.
  * Zdeborová and Krzakala, (2016) Zdeborová, L. and Krzakala, F. (2016).  Statistical physics of inference: Thresholds and algorithms.  Advances in Physics, 65(5):453–552.
  * Zhong and Boumal, (2018) Zhong, Y. and Boumal, N. (2018).  Near-optimal bounds for phase synchronization.  SIAM Journal on Optimization, 28(2):989–1016.
  * Zhou and Chen, (2023) Zhou, Y. and Chen, Y. (2023).  Deflated heteropca: Overcoming the curse of ill-conditioning in heteroskedastic PCA.  arXiv preprint arXiv:2303.06198.
  * Zou et al., (2006) Zou, H., Hastie, T., and Tibshirani, R. (2006).  Sparse principal component analysis.  Journal of computational and graphical statistics, 15(2):265–286.