# Optimal Vehicle Trajectory Planning for Static Obstacle Avoidance using
Nonlinear Optimization

Yajia Zhang  Hongyi Sun  Ruizhi Chai  Daike Kang  Shan Li  Liyun Li The
authors are with Xmotors.ai, a subsidiary of Guangzhou Xiaopeng Motors
Technology Co Ltd. 3940 Freedom Circle, Santa Clara, CA, USA 95054
*Corresponding author: Yajia Zhang<EMAIL_ADDRESS>
###### Abstract

Vehicle trajectory planning is a key component for an autonomous driving
system. A practical system not only requires the component to compute a
feasible trajectory, but also a comfortable one given certain comfort metrics.
Nevertheless, computation efficiency is critical for the system to be deployed
as a commercial product. In this paper, we present a novel trajectory planning
algorithm based on nonlinear optimization. The algorithm computes a
kinematically feasible and comfort-optimal trajectory that achieves collision
avoidance with static obstacles. Furthermore, the algorithm is time efficient.
It generates an 6-second trajectory within 10 milliseconds on an Intel i7
machine or 20 milliseconds on an Nvidia Drive Orin platform.

###### Index Terms:

autonomous driving, intelligent robots, numerical optimization

##  I Introduction

The goal of vehicle trajectory planning is to find feasible trajectories for
autonomous vehicles to navigate safely and comfortably in the environment. For
urban driving, autonomous vehicles need the ability to travel through complex
scenarios, e.g., narrow passages formed by parked vehicles. Furthermore, to
account for environment or perception changes, the planning algorithm is
normally required to generate trajectories at 10 hertz rate or even higher.
Thus computation efficiency is a critical factor on evaluating a trajectory
planning algorithm.

In this paper, we present a novel optimal trajectory planning algorithm for
autonomous vehicles using nonlinear numerical optimization. Given a drivable
corridor that implicitly incorporates the geometry of static obstacles, the
trajectory planner computes a kinematically feasible trajectory within the
drivable corridor with optimal comfort metrics (see Fig. 1). We adopt the
methodology to hierarchically solve autonomous vehicle trajectory planning by
planning path and speed profile in a sequential order. Path planning is
responsible for providing the geometrical component of a trajectory to avoid
collisions with static obstacles; speed profile planning assigns the temporal
component given the planned path to avoid collisions with dynamic obstacles.
This hierarchical approach breaks the trajectory planning problem into two
sequential lower dimensional problems and greatly reduces the overall
complexity. Though the proposed algorithm in this paper can be extended to
avoid dynamic obstacles given their predicted trajectories, we limit our
application of the algorithm for static obstacle collision avoidance. A latter
step, a speed profile planner uses a similar algorithm in [16] to override the
speed profile of the planned trajectory if necessary to avoid collisions with
dynamic obstacles.

Figure 1: A $12$-second trajectory (in dark blue, with resolution $t=0.1s$)
generated by the proposed planning algorithm for a synthetic problem. Red line
is the reference line, i.e, road centerline. Yellow and green lines are the
left and right boundaries of the drivable corridor respectively. Note, the
irregular shape of the corridor boundaries are due to incorporation of static
obstacles. The trajectory in light blue is the initial guess for the
optimization procedure.

For autonomous vehicles, we normally have direct controls over acceleration
through throttle and brake, and the angle of the steering wheel that
corresponds to the curvature of a vehicle’s trajectory according a vehicle
bicycle model (see Fig. 2). In order to obtain graceful motions, these
physical control commands must be continuous over time. This means we need to
take linear jerk, i.e., $j=da/dt$ and curvature change rate, i.e.,
$\dot{\kappa}=d\kappa/dt$, which are at least one order higher than the
control commands, into consideration in trajectory planning.

Compared to closed-form modelings of trajectories, discretized or piecewise
modeling has the advantage on flexibility. To tackle complex urban driving
scenarios, we model the trajectory using a piecewise function, with each piece
corresponding to a constant “control” variable pair $(j,\dot{\kappa})$ that
transits from one vehicle state to the next. These sequence of control
variable pairs decide the spatial and temporal information of the trajectory.
Nevertheless, though our goal is to find an optimal control sequence
essentially, it is difficult to use these control variables directly as
optimization variables due to a chain-like dependency, i.e., the selection of
$i$th control pair depends on all previous control pairs from $1$ to $i-1$.
The chain-like dependency results a dense Jacobian and Hessian matrices in
optimization and thus makes them computationally expensive to update at every
iteration. To solve this, we use discretized vehicle states as optimization
variables instead of control variables. A discretized vehicle state now only
depends on its previous state and the dependency is sparse through all
optimization variables. To satisfy kinematic constraints and maintain the
connectivity of the trajectory, we also set up equality constraints between
consecutive discretized states according to the kinematic model.

Besides sparse dependency formulation, we also use a couple of techniques to
speed up the nonlinear optimization procedure and improve the convergence
rate, including smoothing drivable corridor boundaries, caching intermediate
optimization results, etc. These techniques reduce at least $50\%$ of the
computation time.

##  II Related Work

Trajectory planning for autonomous vehicles has been a vigorous research topic
since the DARPA Grand and Urban Challenge. A number of algorithms have been
developed to tackle the challenges [9, 10, 13, 7, 12]. These algorithms can be
categorized into a couple of classes: randomized planners, such as Rapidly
Exploring Random Tree (RRT)[8], C-PRM[11], can be used for car-like robots
with differential constraints. Some can even produce high-quality paths given
enough computing time [6]. The problem is they are general planners intend to
work regardless of the target problem and they lack the ability to exploit and
utilize the dedicated road-like structured environment for autonomous
vehicles, i.e., environment with directional centerline and boundaries. Thus,
the computed trajectories are usually sub-optimal for autonomous vehicles,
especially at high speed. The application of these algorithms are mostly
limited to off-road scenarios, e.g., parking.

Discrete search methods, such as [2], compute a trajectory by searching from a
set of precomputed maneuvers and concatenating them to a maneuver sequence.
The concatenation is performed by examining whether the starting state of one
maneuver is sufficiently close to the ending state of the target maneuver. For
simple environment with fewer obstacles, these methods generally work well.
However, to deal with complex scenarios in urban driving, the number of
precomputed maneuvers needs to grow exponentially, which makes these methods
impractical.

Instead of planning in the map frame, some methods [15] transform the planning
problem to a Frenet frame that is defined by a smooth driving guide line. The
motion of the vehicle is decoupled to two 1-dimensional motions w.r.t. the
driving guide line: longitudinal motion that moves along the driving guide
line and lateral motions that moves perpendicularly to the driving guide line.
Longitudinal and lateral motions are modeled using quintic or quartic
polynomials and are planned individually. Then, longitudinal and lateral
motions are combined and transformed back to map frame for constraint checking
and selection. Our previous work [17] adopts a similar idea in [15] that plans
a path/trajectory in a Frenet frame but we use piecewise trajectory modeling
for the 1-dimensional motions to improve the flexibility. Frenet frame motion
decoupling is advantageous since it can effectively exploit the road
structure, and lower the complexity by reducing the dimensionality of
planning. However, the drawbacks are also obvious: vehicle’s kinematic
constraints, such as curvature, curvature change rate, etc, are defined in the
map frame and they become too complex in the Frenet frame (see Appendix in
[15]) to consider directly for planning; also the frame transformation
requires a driving guide line that is $C^{3}$ continuous to accurately
decouple the motion to the second-order derivative level (e.g., acceleration
level), which requires a preprocessing of the driving guide line.

The most flexible methods that can deal with complex environments are
optimization based methods. The work in [18] runs a sequential quadratic
programming procedure in the map frame to directly compute a trajectory. The
trajectory is represented by a sequence of discretized positional points, and
these positional points are used as optimization variables. The optimization
procedure iteratively finds a sequence of points that minimizes the objective
function that combines safety and comfort factors. The advantages of
optimization methods in the map frame include direct modeling of trajectory
optimality and enforcement of constraint satisfaction. Furthermore, as the
trajectory is modeled as a sequence of densely discretized points, these
methods achieve maximal control over the spatial and temporal of the
trajectory to deal with complex scenarios.

Our proposed method follows a similar idea as in [18] to use a discretized
modeling of the trajectory and use these discretized points as optimization
variables. But besides the positional information of one state, we use a
populated state representation including heading, curvature, curvature change
rate, etc, that are directly linked to kinematic feasibility. This augmented
state representation makes the objective and constraints easier to formulate
using exact form. Between consecutive states, a list of equality constraints
are set up to maintain the kinematic feasibility and connectivity of the
trajectory.

In general, nonlinear optimization is more difficult to solve than quadratic
programming. Some work such as [1] [17] uses linear functions to linearize the
nonlinear constraints and formulates the objective function into a quadratic
form. However, the approximation sacrifices accuracy and could cause
substantial deviations in modeling for the original problem. Our ideology is
to keep the modeling close to the original problem, and use other techniques
such as smoothing input functions, better guess of starting point, caching
intermediate optimization results, etc, to speed up the overall optimization
process.

##  III Problem Definition

A state $s$ for an autonomous vehicle normally includes the following
variables $(x,y,\theta,\kappa,v,a)$. $x$ and $y$ specify the coordinate of a
reference point on the vehicle, normally the center of gravity or center of
rear axis, in the map frame. $\theta$ is the heading angle of the vehicle in
the map frame. $\kappa$ is the curvature of the turning circle given instant
steering angle $\alpha$ (see Fig.2). $v$ and $a$ are the linear velocity and
acceleration respectively. The goal of trajectory planning is to find a
function $\boldsymbol{S}(t)$ that maps a temporal parameter $t\in[0,t_{max}]$
to a feasible state $s$.

Figure 2: Illustration of a vehicle bicycle model. Bicycle model simplifies a
four-wheeled vehicle to a two-wheeled bicycle with two wheels at the center of
the front axis and rear axis respectively (dark points in the figure). The
steering angle $\alpha$ leads to a circular movement of the vehicle with
radius $R=L/\boldsymbol{\tan}(\alpha)$, where $L$ is the axis length, i.e.,
the distance between front and rear axis. $\kappa$ in the vehicle state space
is the inverse of $R$, i.e., $\boldsymbol{\tan}(\alpha)/L$, and implicitly
represents the steering angle of the vehicle.

###  III-A Vehicle Kinematic Model

Kinematic model specifies how the vehicle state evolve over time given a
control input. We assume linear jerk $j$, i.e., $\frac{da}{dt}$, and curvature
change rate $\dot{\kappa}$, i.e., $\frac{d\kappa}{dt}$, are control variables
in the model. For a given time interval $\Delta t$, the transition from one
vehicle state $s_{0}$ to the next state $s_{1}$ are given by the following
equations, assuming $j$ and $\dot{\kappa}$ remain constant within time $\Delta
t$:

$\displaystyle a_{1}$ $\displaystyle=a_{0}+\boldsymbol{\Delta a}(\Delta t)$
(1) $\displaystyle=a_{0}+\int_{0}^{\Delta t}\boldsymbol{j}(t)dt=a_{0}+j\Delta
t$ $\displaystyle v_{1}$ $\displaystyle=v_{0}+\boldsymbol{\Delta v}(\Delta t)$
(2) $\displaystyle=v_{0}+\int_{0}^{\Delta
t}\boldsymbol{a}(t)dt=v_{0}+a_{0}\Delta t+\frac{1}{2}j\Delta t^{2}$
$\displaystyle\kappa_{1}$
$\displaystyle=\kappa_{0}+\boldsymbol{\Delta\kappa}(\Delta t)$ (3)
$\displaystyle=\kappa_{0}+\int_{0}^{\Delta
t}\boldsymbol{\dot{\kappa}}(t)dt=\kappa_{0}+\dot{\kappa}\Delta t$
$\displaystyle\theta_{1}$
$\displaystyle=\theta_{0}+\boldsymbol{\Delta\theta}(\Delta t)$ (4)
$\displaystyle=\theta_{0}+\int_{0}^{\Delta s}\boldsymbol{\kappa}(s)ds$
$\displaystyle=\theta_{0}+\int_{0}^{\Delta
t}\boldsymbol{\kappa}(\boldsymbol{s}(t))\boldsymbol{s^{\prime}}(t)dt$
$\displaystyle=\theta_{0}+\kappa_{0}v_{0}\Delta
t+\frac{1}{2}(\kappa_{0}a_{0}+v_{0}\dot{\kappa})\Delta t^{2}$
$\displaystyle+\frac{1}{3}(\frac{1}{2}\kappa_{0}j+a_{0}\dot{\kappa})\Delta
t^{3}+\frac{1}{8}\dot{\kappa}j\Delta t^{4}$ $\displaystyle x_{1}$
$\displaystyle=x_{0}+\boldsymbol{\Delta x}(\Delta t)$ (5)
$\displaystyle=x_{0}+\int_{0}^{\Delta
s}\boldsymbol{cos}(\boldsymbol{\theta}(s))ds$
$\displaystyle=x_{0}+\int_{0}^{\Delta
t}\boldsymbol{cos}(\boldsymbol{\theta}(\boldsymbol{s}(t)))\boldsymbol{s^{\prime}}(t)dt$
$\displaystyle y_{1}$ $\displaystyle=y_{0}+\boldsymbol{\Delta y}(\Delta t)$
(6) $\displaystyle=y_{0}+\int_{0}^{\Delta
s}\boldsymbol{sin}(\boldsymbol{\theta}(s))ds$
$\displaystyle=y_{0}+\int_{0}^{\Delta
t}\boldsymbol{sin}(\boldsymbol{\theta}(\boldsymbol{s}(t)))\boldsymbol{s^{\prime}}(t)dt$

$\boldsymbol{\Delta X},X\in\\{x,y,\theta,\kappa,v,a\\}$ represents the
increment function for each element in the state space according to the
kinematic model. $s$ is an auxiliary variable representing the distance the
vehicle has travelled. Though other functions are straightforward to evaluate,
positional increment functions $\boldsymbol{\Delta x}$ and $\boldsymbol{\Delta
y}$ are difficult to compute directly. The integrals in this form normally do
not have closed-form solutions. To address the problem, we use Gaussian-
Legendre quadrature to approximate the integration. The integration problem is
then transformed to a weighted summation on target function values at given
Gauss nodes:

$\displaystyle\boldsymbol{\Delta x}(\Delta t)=\int_{0}^{\Delta
t}\boldsymbol{cos}(\boldsymbol{\theta}(\boldsymbol{s}(t)))\boldsymbol{s^{\prime}}(t)dt$
$\displaystyle\approx\frac{1}{2}\Delta
t\sum_{i=1}^{N}w_{i}\boldsymbol{cos}(\boldsymbol{\theta}(\boldsymbol{s}(\frac{1}{2}\Delta
t\xi_{i}+\frac{1}{2}\Delta t)))\boldsymbol{s}^{\prime}(\frac{1}{2}\Delta
t\xi_{i}+\frac{1}{2}\Delta t)$ $\displaystyle\boldsymbol{\Delta y}(\Delta
t)=\int_{0}^{\Delta
t}\boldsymbol{sin}(\boldsymbol{\theta}(\boldsymbol{s}(t)))\boldsymbol{s^{\prime}}(t)dt$
$\displaystyle\approx\frac{1}{2}\Delta
t\sum_{i=1}^{N}w_{i}\boldsymbol{sin}(\boldsymbol{\theta}(\boldsymbol{s}(\frac{1}{2}\Delta
t\xi_{i}+\frac{1}{2}\Delta t)))\boldsymbol{s}^{\prime}(\frac{1}{2}\Delta
t\xi_{i}+\frac{1}{2}\Delta t)$

$N$ is the order of the Gaussian-Legendre quadrature and it decides the level
of accuracy the approximation can achieve. $\xi_{i}$ and $w_{i}$ are nodes and
corresponding weights for the $N$th order Gauss-Legendre quadrature. In our
implementation, we use $N=10$.

###  III-B Trajectory Planning Problem Input

The input to the proposed planner includes the following items:

  * •

Initial state $s_{0}$.

  * •

Geometrical parameters of the vehicle, including length $l$, width $w$, axis
length $l_{axis}$, for collision avoidance modeling.

  * •

Vehicle’s kinematic bounds, including maximal steering angle $\alpha_{max}$,
maximal steering angle rate $\dot{\alpha}_{max}$, acceleration and jerk
bounds, etc.

  * •

Vehicle kinematic model (see Fig. 2)

  * •

Reference line $l_{ref}$, normally the centerline of the road, in the form of
a directed polyline, i.e., a sequence of two dimensional points.

  * •

Drivable corridor (see Fig. 3) which consists two directed polylines formed by
road boundaries and surrounding static obstacles.

  * •

Target speed $v_{target}$ which is the desired speed of the vehicle, either
from user input or speed limit from road.

##  IV Optimization Formulation

The trajectory planning problem is formulated as a numerical optimization
problem. The constraints and objective function are nonlinear functions of the
optimization variables, which makes the problem a typical nonlinear
optimization problem.

###  IV-A Trajectory Modeling and Variables

The trajectory $\boldsymbol{S}(t)$ is modeled as a piecewise function. It is
discretized by the temporal parameter $t$ with $\Delta t$ as resolution. Each
discretized point corresponds to a vehicle state.

$x_{0}$ |  | $x_{1}$ |  | $x_{2}$ |  | $x_{n-2}$ |  | $x_{n-1}$
---|---|---|---|---|---|---|---|---
$y_{0}$ |  | $y_{1}$ |  | $y_{2}$ |  | $y_{n-2}$ |  | $y_{n-1}$
$\theta_{0}$ | $\xrightarrow{\Delta t}$ | $\theta_{1}$ | $\xrightarrow{\Delta t}$ | $\theta_{2}$ | $\ldots$ | $\theta_{n-2}$ | $\xrightarrow{\Delta t}$ | $\theta_{n-1}$
$\kappa_{0}$ |  | $\kappa_{1}$ |  | $\kappa_{2}$ |  | $\kappa_{n-2}$ |  | $\kappa_{n-1}$
$v_{0}$ |  | $v_{1}$ |  | $v_{2}$ |  | $v_{n-2}$ |  | $v_{n-1}$
$a_{0}$ |  | $a_{1}$ |  | $a_{2}$ |  | $a_{n-2}$ |  | $a_{n-1}$

Between consecutive states, we assume a constant linear jerk term $j$, and a
constant third-order angular term $\dot{\kappa}$ as transition variables. To
maintain the continuity of the trajectory, consecutive states must satisfy the
equality relation defined by the kinematic model discussed in V-A. The
optimality evaluation and constraint satisfaction checking of the trajectory
are performed on these discretized trajectory points. In optimization,
$(x,y,\theta,\kappa,v,a)$ at the discretized states, along with transition
variables $j$ and $\dot{\kappa}$, are optimization variables. For a trajectory
with $n$ discrete states, we have $8(n-1)$ variables (excluding the initial
state $s_{0}$).

###  IV-B Objective Formulation

Optimality evaluation of a vehicle trajectory includes the following cost
factors, and the objective function is a weighted summation of these costs:

  * •

Centripetal acceleration This factor penalizes the centripetal acceleration so
that the autonomous vehicle needs to slow down at curves or cut straight at
curvy roads.
$f_{centri\\_acc}=\Sigma(v_{i}^{2}\kappa_{i})^{2}$.

  * •

Centripetal jerk This factor penalizes the sudden of vehicles steering wheel
when the speed is high.
$f_{centri\\_jerk}=\Sigma(2v_{i}a_{i}\kappa_{i}+v_{i}^{2}\dot{\kappa}_{i})^{2}$

  * •

Curvature change rate This factor penalizes the general sudden changes of
steering wheel.
$f_{\dot{\kappa}}=\Sigma\dot{\kappa}_{i}^{2}$

  * •

Linear jerk This factor penalizes sudden accelerations and brakes.
$f_{linear\\_jerk}=\Sigma j_{i}^{2}$

  * •

Distance to the reference line This factor encourages the vehicle to drive
close to the center of the road.
$f_{lat\\_distance}=\Sigma\boldsymbol{L}_{\delta^{l}}(\boldsymbol{d}((x_{i},y_{i}),\boldsymbol{P}_{\\{x,y\\}}(x_{i},y_{i},l_{ref})))$

  * •

Closeness to target speed. To encourage the trajectory to travel further, we
penalize the difference between vehicle’s speed and a user-defined target
speed.
$f_{\Delta v}=\Sigma\boldsymbol{L}_{\delta^{v}}(v_{i}-v_{target})$

$\Sigma$ represents the summation operation over state index $i\in[1,n-1]$.
$\boldsymbol{P}$ is a projection function that finds the projection point
$(x_{p},y_{p})$, along its direction $\theta_{p}$, on a polyline $l$ given a
point $(x,y)$. $\boldsymbol{d}$ is a function that computes the Euclidean
distance between two points. $\boldsymbol{L}_{\delta}$ is a Huber loss
function [5], which is commonly used in robust regression. We use Huber loss
to model the cost of distance to reference line and closeness to target speed.
In contrast to other cost factors in quadratic form, Huber loss function has
the property that the cost is of quadratic form if the input is within a user
defined $\delta$, linear if the input is outside. Thus it avoids the
underlying cost factor from dominating the overall objective function when
outlier input happens. Take the cost term of distance to reference line as an
example, when autonomous vehicle initiates a lane change, a natural approach
is to switch the reference line from ego lane (the lane where the ego vehicle
is in) to the target lane. If a quadratic form of the cost is used, at the
beginning of the lane change, this cost factor will become excessively large
numerically, which causes other cost factors essentially become ineffective
and leads to drastic lateral motions. The same idea applies to the closeness
to target speed factor during ego vehicle starts from a static state to avoid
drastic longitudinal motions.

Figure 3: Illustration of drivable corridor boundaries and vehicle geometrical
modeling for collision checking. Two circles with radius $R$ are constructed
with origins at the middle of front and rear axises respectively. For vehicles
with different geometry, the number of circles, the selection of origins and
radius can be different to better fit a specific shape. Collision checking is
performed by comparing the projection distances (in red) of two origins on to
the drivable corridor boundaries and radius $R$.

###  IV-C Constraints

####  IV-C1 Equality constraints for trajectory continuity

To maintain the continuity of the planned trajectory, the following equality
constraints derived from the kinematic model must be satisfied between
consecutive states:

$\displaystyle X_{i+1}-X_{i}-\boldsymbol{\Delta X}(\Delta
t)=0,X\in\\{x,y,\theta,\kappa,v,a\\}$ (7)

####  IV-C2 Collision avoidance constraints

We use two circles with origins at the middle of the vehicle’s front and rear
axises to approximate the shape of the vehicle (see Fig. 3). The same
projection function $\boldsymbol{P}$ is used to project the origins of the
circles onto the boundaries of the drivable corridor. The Euclidean distances
between the origins and the projected points are used to check whether the
vehicle is in collision with the boundaries.

####  IV-C3 Kinematic limit and pose constraints

At each discretized state $s_{i}$, the following constraints must be
satisfied:

  * •

Linear acceleration $a_{i}\in[a_{min},a_{max}]$

  * •

Linear jerk $j_{i}\in[j_{min},j_{max}]$

  * •

Linear velocity $v_{i}\in[0.0,+\infty)$

  * •

Curvature $|\kappa_{i}|\leq\kappa_{max}$

  * •

Centripetal acceleration $|v_{i}^{2}\kappa_{i}|\leq a_{centri\\_max}$

  * •

Centripetal jerk $|2v_{i}a_{i}\kappa_{i}+v_{i}^{2}\dot{\kappa}_{i}|\leq
j_{centri\\_max}$

  * •

Heading angle difference
$|\theta_{i}-\boldsymbol{P}_{\theta}(x_{i},y_{i},l_{ref})|\leq\theta_{diff\\_max}$

The first six constraints are from vehicle’s kinematic limits. The heading
difference constraint is not necessary but we find it is helpful on
convergence rate in large curvature scenarios such as U-turns as it reduces
the volume of the search space.

Figure 4: Comparison between original drivable corridor boundaries (top) and
smoothed ones (bottom). The sharp corners are smoothed using a quadratic
programming method described in [17]. The optimizer takes 60 and 7 iterations
to converge to an optimal trajectory respectively given original and smoothed
corridor boundaries.

##  V Implementation and Experiments

We use optimization package IPOPT [14] with linear solver MA97 from HSL[4] to
implement the proposed algorithm. We test the algorithm on a list of synthetic
problems and conduct extensive road tests. The reported computation times are
from an Intel i7 machine with 64GB memory for synthetic problems and an Nvidia
Drive Orin platform for road tests. Vehicle geometry and kinematic bounds are
set according to a specific vehicle model from Xiaopeng Motors. Target speed
$v_{target}$ is set dynamically according to road speed limit on road tests.

###  V-A Initial Guess of Trajectory and Warm Start

Initial guess is important in nonlinear optimization. We use a simple
proportional controller to compute a trajectory for the optimizer to start
with. The controller computes the longitudinal and lateral feedback gains
based on the difference between vehicle’s speed to target speed $v_{target}$
and lateral distance from vehicle’s position to the given reference line
$l_{ref}$ (see Fig.5 for an example trajectory from the P-controller).

Furthermore, in road tests, if the planning for previous cycle is successful
and the problem is similar to current one, e.g., the target reference lines
are the same, the variable values along with their bound multipliers from
previous cycle are used to “warm start” the IPOPT solver. Our experiments show
that in most cases ($>90\%$), using warm start data can reduce the number of
iterations to 2 or 3.

Figure 5: Planned trajectory and its geometrical and temporal properties
(heading $\theta$, curvature $\kappa$, curvature temporal change rate
$\dot{\kappa}$, velocity $v$, acceleration $a$ and linear jerk $j$) from a
synthetic obstacle avoidance scenario. Computed centripetal acceleration and
jerk are also shown. The limits of these properties are drawn in red. The
planned trajectory is shown in dark blue and the initial guess from
P-controller is shown in light blue. The trajectory is 8-second long. The
autonomous vehicle is set to start from a moderate speed ($3m/s$). To avoid
the collision with the static obstacle and maintain a comfort lateral motion,
the vehicle needs to slow down its speed while making the lateral movement.
This example takes the algorithm 46 iterations (computation time $89ms$) to
converge to an optimal solution. Note, the initial guess is in collision with
the boundary which makes the problem difficult to solve.

###  V-B Smoothness of Drivable Corridor Boundaries

We find the smoothness and density of the drivable corridor boundaries greatly
affect the convergence rate of the optimization process, especially when the
boundaries contain sharp corners due to the incorporation of static obstacles.
Our intuitive explanation is that dense resolution of the drivable corridor
(and reference line) can reduce projection error from the polyline projection
function $\boldsymbol{P}$, and smoother edge can lead to smoother derivative
changes. In our implementation, we perform a simple preprocessing step to
smooth out sharp corners and linearly interpolate the boundaries to a higher
resolution (from $1m$ to $0.1m$) for corridor boundaries (see Fig.4).

###  V-C Implementation Optimization

We profile the computation time of the algorithm and identify the time
consuming bottlenecks. One bottleneck is the projection function
$\boldsymbol{P}$ that projects a positional point $(x,y)$ onto a polyline (the
reference line or drivable corridor boundaries in our case). One naive
implementation of $\boldsymbol{P}$ is to loop through all the points in the
polyline and locate the nearest line segment for projection, which is a $O(n)$
algorithm where $n$ is the number of point in the polyline. As IPOPT uses a
filtered line search strategy, the projection will be called at each trial
point and the computation time becomes significant. Our time profiling shows
that the projection function alone takes over $40\%$ of overall computation
time.

To improve this, we use R-tree [3] to index the polyline before the
optimization procedure, and the projection algorithm becomes $O(log(n))$.
Though there is an overhead time for indexing, this reduces $70\%$ of the time
used for the projection function.

###  V-D Testing Results

We test the proposed algorithm on a list of synthetic problems to analyze the
convergence rate (see. Fig.5 for example). We also deploy the proposed
algorithm on an electric vehicle from Xiaopeng for road tests. The test
vehicle equips an Nvidia Drive Orin computation platform. The algorithm is run
on a single core of Drive Orin. The temporal length for the trajectory is $4s$
long. Fig. 6 shows histograms of the computation time and number of
optimization iterations from an over one hour test drive on urban roads in
Guangzhou, China. We set the cutoff-time for the optimizer to 50 milliseconds.
More than 95% of the planning cycles can get reasonable warm starts from
previous planning cycles, and less than 1% of the cycles fail to return a
feasible trajectory. The failure cycles are mostly ($>90\%$) due to improper
settings of the drivable corridor, but some cases are indeed difficult to
solve within the given cutoff time, see Fig.7 for an example.

Figure 6: Histograms of computation time and number of optimization iterations
from an over one hour test drive. The cutoff time for computation is $50$ ms.
There are less than $1\%$ of the planning cycles that the algorithm fails to
compute a feasible trajectory.

Figure 7: An example extracted from a failed road test planning cycle. The
algorithm cannot converge to a feasible trajectory within $50$ ms computation
time. We reproduce the problem offline and the algorithm finds the optimal
trajectory after $46$ iterations. The results are show in this figure. The
planned trajectory is shown in dark blue and the initial guess from
P-controller is shown in light blue.

##  VI Conclusion and Future Work

We propose a novel nonlinear numerical optimization algorithm for autonomous
vehicles. This algorithm is able to reliably find safe and comfortable
trajectories for an autonomous vehicle to navigate in cluttered urban driving
environments, both in terms of success rate and computation time.

For future work, we plan to further develop a strategy to better initialize
the optimization, make the algorithm more robust to difficult scenarios, and
also extend the work to reliably handle dynamic obstacles.

## References

  * [1] Jianyu Chen, Wei Zhan, and Masayoshi Tomizuka.  Constrained iterative lqr for on-road autonomous driving motion planning.  In 2017 IEEE 20th International Conference on Intelligent Transportation Systems (ITSC), pages 1–7, 2017.
  * [2] E. Frazzoli, M.A. Dahleh, and E. Feron.  Maneuver-based motion planning for nonlinear systems with symmetries.  IEEE Transactions on Robotics, 21(6):1077–1091, 2005.
  * [3] Antonin Guttman.  R-trees: A dynamic index structure for spatial searching.  In Proceedings of the 1984 ACM SIGMOD international conference on Management of data, pages 47–57, 1984.
  * [4] HSL.  Hsl. a collection of fortran codes for large scale scientific computation.  http://www.hsl.rl.ac.uk/.
  * [5] Peter J. Huber.  Robust Estimation of a Location Parameter.  The Annals of Mathematical Statistics, 35(1):73 – 101, 1964.
  * [6] Jeong hwan Jeon, Sertac Karaman, and Emilio Frazzoli.  Anytime computation of time-optimal off-road vehicle maneuvers using the rrt.  In Decision and Control and European Control Conference (CDC-ECC), 2011 50th IEEE Conference on, pages 3276–3282. IEEE, 2011.
  * [7] Yoshiaki Kuwata, Justin Teo, Gaston Fiore, Sertac Karaman, Emilio Frazzoli, and Jonathan P How.  Real-time motion planning with applications to autonomous urban driving.  IEEE Transactions on Control Systems Technology, 17(5):1105–1118, 2009.
  * [8] Steven M LaValle and James J Kuffner Jr.  Randomized kinodynamic planning.  The international journal of robotics research, 20(5):378–400, 2001\.
  * [9] J. Levinson, J. Askeland, J. Becker, J. Dolson, D. Held, S. Kammel, J. Z. Kolter, D. Langer, O. Pink, V. Pratt, M. Sokolsky, G. Stanek, D. Stavens, A. Teichman, M. Werling, and S. Thrun.  Towards fully autonomous driving: Systems and algorithms.  In 2011 IEEE Intelligent Vehicles Symposium (IV), pages 163–168, June 2011.
  * [10] Isaac Miller, Mark Campbell, Dan Huttenlocher, Frank-Robert Kline, Aaron Nathan, Sergei Lupashin, Jason Catlin, Brian Schimpf, Pete Moran, Noah Zych, et al.  Team cornell’s skynet: Robust perception and planning in an urban environment.  Journal of Field Robotics, 25(8):493–527, 2008.
  * [11] Guang Song and Nancy M Amato.  Randomized motion planning for car-like robots with c-prm.  In Proceedings 2001 IEEE/RSJ International Conference on Intelligent Robots and Systems. Expanding the Societal Role of Robotics in the the Next Millennium (Cat. No. 01CH37180), volume 1, pages 37–42. IEEE, 2001\.
  * [12] Sebastian Thrun, Mike Montemerlo, Hendrik Dahlkamp, David Stavens, Andrei Aron, James Diebel, Philip Fong, John Gale, Morgan Halpenny, Gabriel Hoffmann, et al.  Stanley: The robot that won the darpa grand challenge.  Journal of field Robotics, 23(9):661–692, 2006.
  * [13] Chris Urmson, Joshua Anhalt, Drew Bagnell, Christopher Baker, Robert Bittner, MN Clark, John Dolan, Dave Duggins, Tugrul Galatali, Chris Geyer, et al.  Autonomous driving in urban environments: Boss and the urban challenge.  Journal of Field Robotics, 25(8):425–466, 2008.
  * [14] Andreas Wächter and Lorenz T Biegler.  On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming.  Mathematical programming, 106(1):25–57, 2006.
  * [15] Moritz Werling, Julius Ziegler, Sören Kammel, and Sebastian Thrun.  Optimal trajectory generation for dynamic street scenarios in a frenet frame.  In Robotics and Automation (ICRA), 2010 IEEE International Conference on, pages 987–993. IEEE, 2010.
  * [16] Yajia Zhang, Hongyi Sun, Jinyun Zhou, Jiangtao Hu, and Jinghao Miao.  Optimal trajectory generation for autonomous vehicles under centripetal acceleration constraints for in-lane driving scenarios.  IEEE Intelligent Transportation Systems Conference (ITSC), 2019\.
  * [17] Yajia Zhang, Hongyi Sun, Jinyun Zhou, Jiacheng Pan, Jiangtao Hu, and Jinghao Miao.  Optimal vehicle path planning using quadratic optimization for baidu apollo open platform.  In 2020 IEEE Intelligent Vehicles Symposium (IV). IEEE, oct 2020.
  * [18] Julius Ziegler, Philipp Bender, Markus Schreiber, Henning Lategahn, Tobias Strauss, Christoph Stiller, Thao Dang, Uwe Franke, Nils Appenrodt, Christoph Gustav Keller, et al.  Making bertha drive-an autonomous journey on a historic route.  IEEE Intell. Transport. Syst. Mag., 6(2):8–20, 2014.


$\mathbb{P}\left(\sigma_{min}(A_{n}-\lambda_{i_{\ell}}I_{n})\leq\delta_{i_{\ell}}n^{-1/2},\ell=1,\cdots,k\right)\lesssim\delta_{i_{1}}\cdots\delta_{i_{k}}+e^{-\Omega(n)}$
(8.1)

for any sufficiently large $n\in\mathbb{N}_{+}$.

###  8.1. Outline of the main arguments

We outline how to prove Theorem 1.2 for $d$ different $\lambda_{i}$’s under
the inductive hypothesis. All the results presented in this section will be
proven later.

The following proposition generalizes Proposition 6.2. We did not state the
general $d$ version there as the proof will rely on the (not yet verified)
induction hypothesis.

######  Proposition 8.1.

Let $A_{n+1}$ and $\lambda_{1},\cdots,\lambda_{d}$ satisfy the assumptions of
Theorem 1.2. For any $p>1$ we have

$\displaystyle\mathbb{P}(\sigma_{min}(A_{n+1}-\lambda_{i}I_{n+1})\leq\delta_{i}n^{-1/2},i=1,2,\cdots,d)\lesssim\delta_{1}\delta_{2}\cdots\delta_{d}+e^{-\Omega(n)}$
$\displaystyle+\mathbb{E}_{A_{n}}\sup_{r_{1},\cdots,r_{d}}\mathbb{P}_{X}\left(\frac{|\langle(A_{n}-\lambda_{i}I_{n})^{-1}X,X\rangle-
r_{i}|}{\|(A_{n}-\lambda_{i}I_{n})^{-1}X\|_{2}}\leq\delta_{i},\frac{\prod_{i=1}^{d}\mu_{1}(\lambda_{i})}{n^{d/2}}\leq(\prod_{i=1}^{n}\delta_{i})^{-p}\right),$

where we omit $i=1,\cdots,d$ in the second line.

At this point we can apply Theorem 2.1 to bound the probability in question,
so that we need to integrate the function $I(\theta)$ (2.2) over the region
$\\{\sum_{i=1}^{d}|\theta_{i}\delta_{i}|^{2}\leq d\\}$. Again we temporarily
replace the denominator $\|(A_{n}-\lambda_{i}I_{n})^{-1}X\|_{2}$ by
$\|(A_{n}-\lambda_{i}I_{n})^{-1}X\|_{*}$ and return to this issue at the end.
We apply Hölder’s inequality to $I(\theta)$ as in (5.2) and obtain

$I(\theta)\lesssim\left(\mathbb{E}_{X_{2},X_{2}^{\prime}}e^{9\langle
X_{2}+X_{2}^{\prime},u\rangle}\right)^{1/9}\left(\mathbb{E}_{\widetilde{X}}e^{-c^{\prime\prime}\|\sum_{i=1}^{d}\frac{\theta_{i}}{\mu_{1}(\lambda_{i})}(A_{n}-\lambda_{i}I_{n})^{-1}\widetilde{X}\|_{2}^{2}}\right)^{\frac{8}{9}},\theta\in\mathbb{R}^{d},$

where the first term on the right hand side is $O(1)$.

Now we have to bound from above $I(\theta)$ carefully, depending on both the
dimension $d$ and the region of $\theta$. Let $2^{[d]}$ denote the collection
of all the subsets of $\\{1,2,\cdots,d\\}$, and for any $\mathcal{A}\in
2^{[d]}$ let $\mathcal{D}_{\mathcal{A}}$ be defined as follows:

$\mathcal{D}_{\mathcal{A}}:=\left\\{\theta\in\mathbb{R}^{d}:\sum_{i=1}^{d}|\theta_{i}\delta_{i}|^{2}\leq
d,\quad|\theta_{i}|\geq 1\text{ if }i\in\mathcal{A},\quad|\theta_{i}|<1\text{
if }i\notin\mathcal{A}\right\\}.$

We introduce another useful notation: for any $\mathcal{A}\in 2^{[d]}$ with
$\mathcal{A}\neq\emptyset$, define

$\|\theta\|_{\mathcal{A}}:=\left(\prod_{i\in\mathcal{A}}|\theta_{i}|\right)^{\frac{1}{|\mathcal{A}|}}$

the geometric average of $|\theta_{i}|$ on $\mathcal{A}$, where
$|\mathcal{A}|$ denotes the cardinality of the set $\mathcal{A}$. Then, we
observe that, to bound
$\int_{\mathcal{D}_{\mathcal{A}}}I(\theta)^{1/2}d\theta$, it suffices to bound

$\int_{\mathcal{D}_{\mathcal{A}}}\mathbb{P}_{\widetilde{X}}\left(\left\|\sum_{i=1}^{d}\frac{\theta_{i}}{\mu_{1}(\lambda_{i})}(A_{n}-\lambda_{i}I_{n})^{-1}\widetilde{X}\right\|_{2}\leq\|\theta\|_{\mathcal{A}}^{\frac{1}{1o^{d}+1}}\right)^{\frac{4}{9}}d\theta.$
(8.2)

This is because for any $\mathcal{A}\neq\emptyset$ and any
$c^{\prime\prime}>0$,

$\int_{\mathcal{D}_{\mathcal{A}}}e^{-c^{\prime\prime}\|\theta\|_{\mathcal{A}}^{2/(10^{d}+1)}}d\theta=O(1).$

Now we estimate (8.2) for $\mathcal{A}=\\{1,2,\cdots,d\\}$ (we simply write
$\mathcal{A}=[d]$ in this case). We first renormalize
$(\theta_{1},\cdots,\theta_{d})$, then apply Lemma 4.1, and then simplify the
integral to a one-variate integration. That is,

$\eqref{integralforsimplified}_{\mathcal{A}=[d]}=\int_{\mathcal{D}_{[d]}}\mathbb{P}_{\widetilde{X}}\left(\left\|\sum_{i=1}^{d}\frac{\theta_{i}/\|\theta\|_{[d]}}{\mu_{1}(\lambda_{i})}(A_{n}-\lambda_{i}I_{n})^{-1}\widetilde{X}\right\|_{2}\leq\|\theta\|_{[d]}^{-\frac{10^{d}}{10^{d}+1}}\right)^{\frac{4}{9}}d\theta.$
(8.3)

Then we wish to apply Lemma 4.1 to the probability inside the integration,
which provides an estimate independent of $(\theta_{1},\cdots,\theta_{d})$
with $\|\theta\|_{[d]}=1$ except for the subscript $J$, where $J$ depends on
the relative value of $\theta_{i}$.

We let $\sum_{1}^{[d]},\cdots,\sum_{d}^{[d]}$ denote a partition of the
hyperplane $\|\theta\|_{[d]}=1$ (this partition also depends on $A_{n}$) such
that Lemma 4.1 gives $J=i$ when $\theta/\|\theta\|_{[d]}\in\sum_{i}^{[d]}$.
Then, for any $\eta>0$, we have

$\eqref{integralforsimplified}_{\mathcal{A}=[d]}\lesssim\sum_{\ell=1}^{d}\int_{s=1}^{\|\delta\|_{[d]}}s^{d-1+\eta}\sup_{\theta\in\sum_{\ell}^{[d]}}\mathbb{P}_{\widetilde{X}}\left(\left\|\sum_{i=1}^{d}\frac{\theta_{i}}{\mu_{1}(\lambda_{i})}(A_{n}-\lambda_{i}I_{n})^{-1}\widetilde{X}\right\|_{2}\leq
s^{-\frac{10^{d}}{10^{d}+1}}\right)^{\frac{4}{9}}ds$ (8.4)

where $\|\delta\|_{[d]}:=(\delta_{1}\cdots\delta_{d})^{1/d}$. The factor
$s^{d-1+\eta}$ comes from the change in coordinates, as implied by the
following lemma:

######  Lemma 8.2.

Let $A_{d}(s)$ denote the volume of the following region in $\mathbb{R}^{d}$:

$\left\\{(\theta_{1},\cdots,\theta_{d})\in\mathbb{R}^{d}:|\prod_{i=1}^{d}\theta_{i}|\leq
s^{d},|\theta_{i}|\geq 1\text{ for each }i\right\\}.$

Then there exists a constant $C_{d}$ and a polynomial $p_{d}(x)$ such that for
any $s>1$,

$0<\frac{d}{ds}A_{d}(s)\leq C_{d}s^{d-1}p_{d}(\log s).$

Now we apply a further change in the coordinates to obtain

$\eqref{integralforsimplified}_{\mathcal{A}=[d]}\lesssim\sum_{\ell=1}^{d}\int_{\frac{1}{\|\delta\|_{[d]}}}^{1}s^{-\frac{(10^{d}+1)(d+\eta)}{10^{d}}-1}\sup_{\theta\in\sum_{\ell}^{[d]}}\mathbb{P}_{\widetilde{X}}\left(\left\|\sum_{i=1}^{d}\frac{\theta_{i}}{\mu_{1}(\lambda_{i})}(A_{n}-\lambda_{i}I_{n})^{-1}\widetilde{X}\right\|_{2}\leq
s\right)^{\frac{4}{9}}ds.$ (8.5)

We can choose $\eta>0$ to be sufficiently small (depending on $d$) so that
$(10^{d}+1)(d+\eta)/10^{d}+1-\frac{4}{9}\leq d+\frac{3}{4}$. Applying Lemma
4.1 and taking the decomposition in the same form as (5.14), replacing
$\sqrt{\mu_{1}(\lambda_{1})\mu_{1}(\lambda_{2})}$ by
$(\prod_{i=1}^{d}\mu_{1}(\lambda_{i}))^{1/d}$, we get

$\eqref{integralforsimplified}_{\mathcal{A}=[d]}\lesssim\sum_{\ell=1}^{d}\sum_{k=2}^{cn}e^{-k}\left(\frac{(\prod_{i=1}^{d}\mu_{1}(\lambda_{i}))^{1/d}}{\mu_{k}(\lambda_{\ell})}\right)^{d-1/4}+e^{-\Omega(n)}.$
(8.6)

We have made very careful choices of parameters such that the power of each
$\mu_{1}(\lambda_{i})$ is less than 1. Similarly, applying Lemma 4.4 for any
$\emptyset\neq\mathcal{A}\in 2^{[d]}$ we obtain

$\eqref{integralforsimplified}_{\mathcal{A}}\lesssim\sum_{\ell=1}^{d}\sum_{k=2}^{cn}e^{-k}\left(\frac{(\prod_{i=1}^{|\mathcal{A}|}\mu_{1}(\lambda_{i}))^{1/|\mathcal{A}|}}{\mu_{k}(\lambda_{\ell})}\right)^{|\mathcal{A}|-1/4}+e^{-\Omega(n)}.$
(8.7)

Now we can prove the following lemma for general $d$, generalizing Lemma 5.1.

######  Lemma 8.3.

Under theorem 1.2, for any $\delta_{1},\cdots,\delta_{d}\geq e^{-cn}$, any
$u\in\mathbb{R}^{n}$ with $\|u\|_{2}\leq d$, and any $p>1$, we have the
following estimate:

$\displaystyle\mathbb{E}_{A_{n}}\sup_{r_{1},\cdots,r_{d}}\mathbb{P}_{X}\left(\frac{|\langle(A_{n}-\lambda_{i}I_{n})^{-1}X,X\rangle-
r_{i}|}{\|(A_{n}-\lambda_{i}I_{n})^{-1}\|_{*}}\leq\delta_{i},\langle
X,u\rangle\geq
s,\frac{\prod_{i=1}^{d}\mu_{1}(\lambda_{i})}{n^{d/2}}\leq(\prod_{i=1}^{d}\delta_{i})^{-p}\right)$
(8.8) $\displaystyle\lesssim e^{-s}\prod_{i=1}^{d}\delta_{i}+e^{-\Omega(n)}$
$\displaystyle+e^{-s}(\prod_{i=1}^{d}\delta_{i})\mathbb{E}_{A_{n}}\left[\left(\frac{\prod_{i=1}^{d}\mu_{1}(\lambda_{i})}{n^{d/2}}\right)^{1-\frac{1}{8d}}\wedge\left\\{\frac{\prod_{i=1}^{d}\mu_{1}(\lambda_{i})}{n^{d/2}}\leq(\prod_{i=1}^{d}\delta_{i})^{-p}\right\\}\right]^{\frac{8d-2}{8d-1}},$

where $c$ depends on the assumptions in Theorem, on $\kappa$ and $\Delta$.

This lemma (with $u=0$, $s=0$ and $p>1$ sufficiently close to 1) combined with
Proposition 8.1 and Hanson-Wright imply the following initial estimate:

######  Lemma 8.4.

(Initial estimate) Under theorem 1.2, for any $\delta_{1},\cdots,\delta_{d}>0$

$\mathbb{P}(\sigma_{min}(A_{n+1}-\lambda_{i}I_{n+1})\leq\delta_{i}n^{-1/2},i=1,\cdots,d)\lesssim(\prod_{i=1}^{d}\delta_{i})^{\frac{1}{8d}}+e^{-cn}.$

By bootstrapping this estimate finitely many times, we can prove that

######  Lemma 8.5.

(Bootstrap) In the setting of this section, for any
$\delta_{1},\cdots,\delta_{d}>0$

$\mathbb{P}(\sigma_{min}(A_{n+1}-\lambda_{i}I_{n+1})\leq\delta_{i}n^{-1/2},i=1,\cdots,d)\lesssim(\prod_{i=1}^{d}\delta_{i})(\log(\prod_{i=1}^{d}\delta_{i})^{-1})^{d/2}+e^{-cn}.$

Finally, the additional log factor can be removed following the procedure in
Section 7.2. The details are given in the next subsection, and this completes
the proof of Theorem 1.2 for any $d\in\mathbb{N}_{+}$.

###  8.2. Proofs of intermediate steps

Now we prove all the results claimed in Section 8.1.

###### Proof of Proposition 8.1.

We first prove that, for any $p>1$,

$\mathbb{P}(\sigma_{min}(A_{n+1}-\lambda_{i}I_{n+1})\leq\delta_{i}n^{-1/2},i=1,\cdots,d\quad\mathcal{P}^{p,d})\lesssim\prod_{i=1}^{d}\delta_{i}+e^{-\Omega(n)},$
(8.9)

where we define

$\mathcal{P}^{p,d}:=\left\\{\prod_{i=1}^{d}\sigma_{min}(A^{(j)}_{n+1}-\lambda_{i}I_{n})\leq(\prod_{i=1}^{d}\delta_{i})^{p}n^{-d/2}\text{
for at least }\frac{1}{4}n\text{ values }j\in[n+1]\right\\}.$

Once this is proven, we can deduce Proposition 8.1 in exactly the same way as
the proof of Proposition 6.2 is worked out: we use the no-gaps delocalization
result (Theorem 6.3) to deduce that (6.6) holds for all $i=1,\cdots,d$ and for
at least $\frac{1}{2}n$ choices of $j\in[n+1]$.

Now we prove (8.9). We fix some $j\in[n+1]$ such that the event in
$\mathcal{P}^{p,d}$ holds for $j$ and moreover, for all the $d$ eigenvectors
associated with the least singular values of $A_{n+1}-\lambda_{j}I_{n+1}$
($j=1,\cdots,d$), their $j$-th coordinates have an absolute value of at least
$cn^{-1/2}$ for some fixed $c$. The latter property can be satisfied with
probability $1-e^{-\Omega(n)}$ thanks to Theorem 6.3. We take a dyadic
partition of $[(\prod_{i=1}^{d}\delta_{i})^{p},1]$ and consider each subevent
where $\sigma_{min}(A_{n+1}^{(j)}-\lambda_{i}I_{n})\leq x_{i}n^{-1/2}$ and
$\prod_{i=1}^{d}x_{i}\leq 2^{p}(\prod_{i=1}^{d}\delta_{i})^{p}$. If there
exists some $k\in[d]$ with $x_{k}>\delta_{k}$, then we first use our induction
hypothesis and Lemma (5.2) to deduce that, for any $\eta>0$,

$\mathbb{P}(\prod_{i\in[d]\setminus\\{k\\}}\sigma_{min}(A_{n+1}^{(j)}-\lambda_{i}I_{n})\leq\prod_{i\in[d]\setminus\\{k\\}}x_{i})\lesssim(\prod_{i\in[d]\setminus\\{k\\}}x_{i})^{1-\eta}+e^{-\Omega(n)}$
(8.10)

Then we use Fact (6.4) to show that we have

$\mathbb{P}(\sigma_{min}(A_{n+1}-\lambda_{k}I_{n+1})\leq
x_{k}n^{-1/2},\sigma_{min}(A_{n+1}^{(j)}-\lambda_{k}I_{n})\leq
x_{k}n^{-1/2}\mid\mathcal{HA}_{[d]\setminus\\{k\\}})\lesssim x_{k},$

where we denote by $\mathcal{HA}_{[d]\setminus\\{k\\}}$ the event

$\mathcal{HA}_{[d]\setminus\\{k\\}}:=\left\\{\prod_{i\in[d]\setminus\\{k\\}}\sigma_{min}(A_{n+1}^{(j)}-\lambda_{i}I_{n})\leq\prod_{i\in[d]\setminus\\{k\\}}x_{i}\right\\}.$

Combining the last two estimates completes the proof, and our dyadic partition
leads to an entropy cost of $\log((\prod_{i=1}^{d}\delta_{i})^{-1})^{C_{d}}$.
If for all $k$ we have $x_{k}<\delta_{k}$ then for some $j\in[d]$ we have
$x_{j}\leq\delta_{j}(\prod_{i=1}^{d}\delta_{i})^{(p-1)/d}$. We choose some
$k\neq j$ and apply the induction hypothesis to $[d]\setminus\\{k\\}$ and
apply Fact (6.4) to $\\{k\\}$. It is straightforward to check that the bound
is good enough. ∎

###### Proof of Lemma 8.2.

Evidently we have $A_{1}(s)=2(s-1)$ and we have already computed
$A_{2}(s)=4(s^{2}\ln s^{2}-s^{2}+1)$. We let $F_{d}(s^{d}):=A_{d}(s)$ and note
the following iterative formula:

$A_{d}(s)\equiv
F_{d}(s^{d})=2\int_{1}^{s^{d}}F_{d-1}\left(\frac{s^{d}}{y}\right)dy,$

where we first integrate over $y=|\theta_{1}|$, and on this cross-section we
have $\prod_{i=2}^{d}|\theta_{i}|\leq\frac{s^{d}}{y}$. Then the claim follows
from direct, but tedious computations. We can check via induction that for
each $d$, we can find a constant $C_{d}$ satisfying

$F_{d}(s^{d})=C_{d}s^{d}\ln^{d-1}(s^{d})+s^{d}(\text{ lower powers of
}\ln(s^{d}))+\text{ const}.$

∎

###### Proof of Lemma 8.3.

We first define the following event, for any $p>1$:

$\mathcal{H}:=\left\\{\langle X,u\rangle\geq
s,\frac{\prod_{i=1}^{d}\mu_{1}(\lambda_{i})}{n^{d/2}}\leq(\prod_{i=1}^{d}\delta_{i})^{-p},\frac{\prod_{i\in\mathcal{A}}\mu_{1}(\lambda_{i})}{n^{|\mathcal{A}|/2}}\leq(\prod_{i=1}^{d}\delta_{i})^{-p},\mathcal{A}\in
2^{[d]}\right\\}.$

Then to prove Lemma 8.3, we suffice to prove the lemma if we replace the first
line of (8.8) with

$\mathbb{E}_{A_{n}}\sup_{r_{1},\cdots,r_{d}}\mathbb{P}_{X}\left(\frac{|\langle(A_{n}-\lambda_{i}I_{n})^{-1}X,X\rangle-
r_{i}|}{\|A_{n}-\lambda_{i}I_{n})^{-1}\|_{*}}\leq\delta_{i},i=1,\cdots,d,\quad\wedge\mathcal{H}.\right)$

This is because for each $\emptyset\neq\mathcal{A}\in 2^{[d]}$ such that
$\mathcal{A}\neq\\{1,\cdots,d\\}$, we have by the induction hypothesis and
Lemma 5.2 that
$\mathbb{P}\left(\frac{\prod_{i\in\mathcal{A}}\mu_{1}(\lambda_{i})}{n^{|\mathcal{A}|/2}}\geq(\prod_{i=1}^{d}\delta_{i})^{-p}\right)\lesssim\prod_{i=1}^{d}\delta_{i}+e^{-\Omega(n)}$.

Now we can apply Theorem 2.1 which yields that it suffices to bound

$\sum_{A\in
2^{[d]}}\mathbb{E}_{A_{n}}\left[\frac{\prod_{i\in\mathcal{A}}\mu_{1}(\lambda_{i})}{\prod_{i\in\mathcal{A}}\|(A_{n}-\lambda_{i}I_{n})\|_{*}}\cdot\int_{\mathcal{D}_{\mathcal{A}}}I(\theta)^{1/2}d\theta\quad\wedge\mathcal{H}\right].$

Now we plug in estimates (8.6) and (8.7), and it suffices to bound

$\sum_{A\in
2^{[d]}}\sum_{\ell=1}^{d}\mathbb{E}_{A_{n}}\left[\frac{\prod_{i\in\mathcal{A}}\mu_{1}(\lambda_{i})}{\prod_{i\in\mathcal{A}}\|(A_{n}-\lambda_{i}I_{n})\|_{*}}\cdot\sum_{k=2}^{cn}e^{-k}\left(\frac{(\prod_{i=1}^{|\mathcal{A}|}\mu_{1}(\lambda_{i}))^{1/|\mathcal{A}|}}{\mu_{k}(\lambda_{\ell})}\right)^{|\mathcal{A}|-1/4}\wedge\mathcal{H}\right].$

Now we apply Hölder’s inequality, combined with Lemma 3.1 and Corollary 3.2
which shows $\mu_{1}(\lambda_{i})/\|A_{n}-\lambda_{i}I_{n}\|_{*}$ and
$\sqrt{n}/k\mu_{k}(\lambda_{\ell})$ have all finite $p$-th moments, to deduce
that it suffices to bound the following expression (omitting computation
details)

$\sum_{\mathcal{A}\in
2^{[d]}}\mathbb{E}_{A_{n}}\left[\left(\frac{\prod_{i=1}^{|\mathcal{A}|}\mu_{1}(\lambda_{i})}{n^{|\mathcal{A}|/2}}\right)^{1-\frac{1}{8|\mathcal{A}|}}\wedge\mathcal{H}\right]^{\frac{8|\mathcal{A}|-2}{8|\mathcal{A}|-1}}.$

The case where $\mathcal{A}=\\{1,\cdots,d\\}$ is as given in the statement of
Lemma 8.3. It remains to show that for any $\mathcal{A}\neq\\{1,\cdots,d\\}$,
the given expectation is $O(1)$. For this purpose we compute

$\int_{0}^{(\prod_{i\in\mathcal{A}}\delta_{i})^{-\frac{8|\mathcal{A}|-1}{8|\mathcal{A}|}p}}\mathbb{P}\left(\prod_{i\in\mathcal{A}}\sigma_{min}(A_{n}-\lambda_{i}I_{n})\leq
x^{-\frac{8|\mathcal{A}|}{8|\mathcal{A}|-1}}n^{-|\mathcal{A}|/2}\right)dx.$
(8.11)

By the induction hypothesis and an application of Lemma 5.2, we obtain for any
$\eta>0$ and $x>1$,

$\mathbb{P}\left(\prod_{i\in\mathcal{A}}\sigma_{min}(A_{n}-\lambda_{i}I_{n})\leq
x^{-\frac{8|\mathcal{A}|}{8|\mathcal{A}|-1}}n^{-|\mathcal{A}|/2}\right)\leq
x^{-\frac{8|\mathcal{A}|}{8|\mathcal{A}|-1}+\eta}+e^{-\Omega(n)},$

and hence that $\eqref{whatline1432}=O(1)$ by choosing $\eta>0$ small. This
completes the proof. ∎

###### Proof of Lemma 8.4.

We first apply Hanson-Wright (Theorem 7.1) to deduce that for each
$i\in\\{1,2,\cdots,d\\}$, where we also use $\|M\|_{*}\geq\|M\|_{HS}$ for any
square matrix $M$,

$\mathbb{P}_{X}\left(\|(A_{n}-\lambda_{i}I_{n})^{-1}X\|_{2}\geq
C^{\prime}(\log(\prod_{i=1}^{d}\delta_{i})^{-1})^{1/2}\cdot\|(A_{n}-\lambda_{i}I_{n})^{-1}\|_{*}\right)\leq\prod_{i=1}^{d}\delta_{i}$

Then the result follows from applying Proposition 8.1 and Lemma 8.3 where we
take $u=0$, $s=0$, take $p>1$ sufficiently close to 1, and take $\delta_{i}$
to be $\delta_{i}\cdot(\log(\prod_{i=1}^{d}\delta_{i})^{-1})^{1/2}$.

∎

###### Proof of Lemma 8.5.

We set up the following bootstrap argument: suppose that for some
$\tau\in(0,1)$ we have proven the following for all
$\delta_{1},\cdots,\delta_{d}>0$,

$\mathbb{P}(\sigma_{min}(A_{n+1}-\lambda_{i}I_{n+1})\leq\delta_{i}n^{-1/2},i=1,\cdots,d)\lesssim\left(\prod_{i=1}^{d}\delta_{i}\right)^{\tau}+e^{-\Omega(n)},$

then this implies that

$\displaystyle\mathbb{P}(\sigma_{min}(A_{n+1}-\lambda_{i}I_{n+1})\leq\delta_{i}n^{-1/2},i=1,\cdots,d)$
$\displaystyle\quad\lesssim\left(\prod_{i=1}^{d}\delta_{i}\right)^{\tau+\frac{1}{9d}}(\log(\prod_{i=1}^{d}\delta_{i})^{-1})^{d/2}+e^{-\Omega(n)}.$

We prove this claim via the following steps. By our assumption and an
application of Lemma 5.2, we get for any $\omega>0$ and $x>1$,

$\mathbb{P}\left(\prod_{i=1}^{d}\sigma_{min}(A_{n}-\lambda_{i}I_{n})\leq
x^{-\frac{8d}{8d-1}}n^{-d/2}\right)\leq
x^{-\frac{8d}{8d-1}\tau(1-\omega)}+e^{-\Omega(n)},$

so that

$\displaystyle\int_{0}^{(\prod_{i=1}^{d}\delta_{i})^{-\frac{8d-1}{8d}p}}\mathbb{P}\left(\prod_{i=1}^{d}\sigma_{min}(A_{n}-\lambda_{i}I_{n})\leq
x^{-\frac{8d}{8d-1}}n^{-d/2}\right)dx$ $\displaystyle\quad\quad\lesssim
1+(\prod_{i=1}^{d}\delta_{i})^{p\tau(1-\omega)-\frac{8d-1}{8d}p},$

and
$\mathbb{E}_{A_{n}}\left[(\frac{\prod_{i=1}^{d}\mu_{1}(\lambda_{i})}{n^{d/2}})^{1-\frac{1}{8d}}\right]^{\frac{8d-2}{8d-1}}\lesssim\max\left\\{1,(\prod_{i=1}^{d}\delta_{i})^{\frac{8d-2}{8d-1}p\tau(1-\omega)-\frac{4d-1}{4d}p}\right\\}.$

Now we apply Hanson-Wright (Theorem 7.1) as in the proof of the previous
lemma, then apply Proposition 8.1 and Lemma 8.3 where we take $u=0$, $s=0$ and
take $\delta_{i}$ to be
$\delta_{i}\log((\prod_{j=1}^{d}\delta_{j})^{-1})^{1/2}.$ This gives us

$\displaystyle\mathbb{P}(\sigma_{min}(A_{n+1}-\lambda_{i}I_{n+1})\leq\delta_{i}n^{-1/2},i=1,\cdots,d)$
$\displaystyle\lesssim\left(\prod_{i=1}^{d}\delta_{i}\right)^{\min\\{1,\frac{8d-2}{8d-1}p\tau(1-\omega)-\frac{4d-1}{4d}p+1\\}}(\log(\prod_{i=1}^{d}\delta_{i})^{-1})^{d/2}+e^{-\Omega(n)}.$

Now we take $\omega>0$ sufficiently small, take $p>1$ that satisfies
$p(1-\omega)=\frac{8d-1}{8d-2}$, and satisfies
$-\frac{4d-1}{4d}p+1\geq\frac{1}{9d}$. This justifies the claim.

Finally, we apply the bootstrap procedure finitely many times, initiated at
$\frac{1}{8d}$ and proceed with step size $\frac{1}{10d}$. The procedure stops
after less than $10d$ iterations. ∎

###### Proof of Theorem 1.2 for general $d$.

The arguments follow those given in Section 7.2 and we will only give a
sketch. Let
$\mathcal{E}:=\\{\prod_{i=1}^{d}\sigma_{min}(A_{n}-\lambda_{i}I_{n})\geq(\prod_{i}\delta_{i})^{p}n^{-p/2}\\}$.
Consider the following decomposition

$\displaystyle\mathbb{P}^{\mathcal{E}}(Q(A,X,\lambda_{i})\leq
C\delta_{i},i=1,\cdots,d)$ (8.12) $\displaystyle\leq\sum_{\mathcal{A}\in
2^{[d]}}\mathbb{P}^{\mathcal{E}}(Q(A,X,\lambda_{i})\leq
C\delta_{i},i\in[d];\frac{\|(A_{n}-\lambda_{i}I_{n})^{-1}X\|_{2}}{\|(A_{n}-\lambda_{i}I_{n})^{-1}\|_{*}}\geq
2,i\in\mathcal{A}).$

The case $\mathcal{A}=\emptyset$ can be verified directly. We just apply Lemma
8.3 (taking $s=0$, $u=0$) and Lemma 8.5 to show that this term is bounded by
$\delta_{1}\cdots\delta_{d}+e^{-\Omega(n)}$.

For a general $\mathcal{A}\neq\emptyset$, we consider a direct product of
$|\mathcal{A}|$ dyadic partitions

$2^{j_{i}}\leq\|(A_{n}-\lambda_{i}I_{n})^{-1}X\|_{2}/\|(A_{n}-\lambda_{i}I_{n})^{-1}\|_{*}\leq
2^{j_{i+1}},i\in\mathcal{A}$

where we terminate each dyadic partition at $\log n$ (i.e. set $j_{i}\leq\log
n$ for each $i\in\mathcal{A}$) thanks to an application of Hanson-Wright
(Theorem 7.1).

As in Lemma 7.6, we can prove the following: for any $(t_{1},\cdots,t_{d})$
satisfying $t_{i}=1$ if $i\notin\mathcal{A}$ and $t_{i}\geq 2$ if
$i\in\mathcal{A}$,

$\displaystyle\mathbb{P}_{X}^{\mathcal{E}}\left(Q_{*}(A,X,\lambda_{i})\leq
2Ct_{i}\delta_{i},i=1,\cdots,d;\quad\frac{\|(A_{n}-\lambda_{i}I_{n})^{-1}X\|_{2}}{\|(A_{n}-\lambda_{i}I_{n})^{-1}\|_{*}}\geq
t_{i},\quad i\in\mathcal{A}\right)$ (8.13) $\displaystyle\leq
2^{d}\sum_{k_{j}=1,j\in\mathcal{A}}^{n}\mathbb{P}_{X}^{\mathcal{E}}\left(Q_{*}(A,X,\lambda_{i})\leq
2Ct_{i}\delta_{i},i\in[d];\langle X,v_{k_{j}}(\lambda_{j})\rangle\geq
t_{j}\log(1+k_{j}),j\in\mathcal{A}\right),$

where each $v_{k_{j}}(\lambda_{j})$, $j\in\mathcal{A}$ is chosen from an
orthonormal basis of eigenvectors of $A_{n}$ and these vectors are not
necessarily distinct.

To compute the probability in the second line of (LABEL:decomposition1481), we
use Lemmas 8.3 and 8.5 to obtain a bound (where we take the vector
$u:=\sum_{j\in\mathcal{A}}v_{k_{j}}(\lambda_{j})$ in Lemma 8.3)

$\begin{aligned} &\mathbb{P}_{X}^{\mathcal{E}}\left(Q_{*}(A,X,\lambda_{i})\leq
2Ct_{i}\delta_{i},i\in[d];\langle X,v_{k_{j}}(\lambda_{j})\rangle\geq
t_{j}\log(1+k_{j}),j\in\mathcal{A}\right)\\\
&\lesssim\delta_{1}\cdots\delta_{d}\prod_{j\in\mathcal{A}}t_{j}\cdot
e^{-\sum_{j\in\mathcal{A}}t_{j}\log(1+k_{j})}\end{aligned}.$

This step completes the proof by noticing that, for each $\mathcal{A}\in
2^{[d]}$,

$\sum_{j_{i}=1,i\in\mathcal{A}}^{\infty}\sum_{k_{i}=1,i\in\mathcal{A}}^{\infty}2^{\sum_{i\in\mathcal{A}}j_{i}}\prod_{i\in\mathcal{A}}(k_{i}+1)^{-2^{j_{i}}}=\left(\sum_{j=1}^{\infty}\sum_{k=1}^{\infty}2^{j}(k+1)^{-2^{j}}\right)^{|\mathcal{A}|}=O(1).$

∎

##  9\. Mesoscopically separated locations

In this section, we assume that the locations $\lambda_{1},\cdots,\lambda_{d}$
are separated from one another only by distance $\Delta n^{-1/2+\sigma}$, for
some fixed values of $\Delta>0$ and $\sigma>0$.

We prove Theorem 1.5, which states that all the results in Theorem 1.2 hold
true but with a larger error $e^{-\Omega(n^{\sigma/2})}$ rather than
$e^{-\Omega(n)}$.

We first state two useful corollaries of the local arcsine law. The first is
an adaptation of Corollary 3.9 to scale $k\sim n^{\sigma}$.

######  Corollary 9.1.

In the setting of Corollary 3.8, for any
$\lambda_{i}\in[(-(2-\kappa)\sqrt{n},(2-\kappa)\sqrt{n}]$, $i=1,\cdots,d$, any
$c_{0}>0$ and any $k\geq c_{0}n^{\sigma}$,

$\mathbb{P}\left(\frac{\mu_{k}(\lambda_{i})}{\mu_{1}(\lambda_{i})}\geq
10^{-5}d^{-1}\right)\leq e^{-\Omega(n^{\sigma/2})}.$ (9.1)

###### Proof.

By Corollary 3.6, with probability $1-e^{-\Omega(n^{\frac{\sigma}{2}})}$,
$\mu_{k}(\lambda_{i})\in[\frac{C_{1}\sqrt{n}}{k},\frac{C_{2}\sqrt{n}}{k}]$ for
all $k\geq c_{0}n^{\sigma}$ any any $\sigma>0$. Then it suffices to consider
the event $\mu_{1}(\lambda_{i})\leq C\sqrt{n}/{n^{\sigma}}$ for any $C>0$, but
this event implies that on the interval of length
$2C^{-1}n^{\sigma-\frac{1}{2}}$ centered at $\lambda_{i}$, $A_{n}$ has no
eigenvalues. By Theorem 3.3, the possibility of this event is less than
$e^{-\Omega(n^{\sigma/2})}$. ∎

Recall the notation $\mu_{c_{j}(i;k)}(\lambda_{j})$ introduced in Definition
4.2, where $c_{j}(i;k)$ is the subscript of the singular vector of
$(A_{n}-\lambda_{j}I_{n})^{-1}$ sharing the same singular vector with the
$k$-th largest singular value of $(A_{n}-\lambda_{i}I_{n})^{-1}$.

We prove the following further estimate:

######  Lemma 9.2.

Let $\Delta>0,\kappa>0$ and $\sigma\in(0,1)$ be fixed. Fix any
$\lambda_{1},\cdots,\lambda_{d}\in[-(2-\kappa)\sqrt{n},(2-\kappa)\sqrt{n}]$
satisfying $|\lambda_{i}-\lambda_{j}|\geq\Delta n^{\sigma-\frac{1}{2}}$ for
any $i\neq j$. Then

  1. (1)

We can find some constant $\Delta_{0}>0$ and some $C_{0}>0$ depending on
$\Delta$ such that, for any $k\leq\Delta_{0}n^{\sigma}$, we have

$\mathbb{P}(c_{j}(i;k)\leq C_{0}n^{\sigma})\leq\exp(-\Omega(n^{\sigma/2})).$
(9.2)

  2. (2)

We can further find some $\Delta_{0}>0$ which is sufficiently small such that
for any $i\neq j\in\\{1,2,\cdots,d\\}$ and, we have on an event with
probability $1-e^{-\Omega(n^{\sigma/2})},$

$\frac{\mu_{c_{i}(j;1)}(\lambda_{i})}{\mu_{1}(\lambda_{i})}\leq
10^{-5}d^{-1}\frac{\mu_{1}(\lambda_{j})}{\mu_{1}(\lambda_{j})}$ (9.3)

  3. (3)

Suppose we are given $(\theta_{1},\cdots,\theta_{d})\in\mathbb{R}^{d}$ and
some $J\in\\{1,\cdots,d\\}$ that satisfy
$|\frac{\theta_{J}}{\mu_{1}(\lambda_{J})}|\geq|\frac{\theta_{i}}{\mu_{1}(\lambda_{i})}|$
for any $i\neq J$. Then we can find some (small) $\Delta_{0}>0$ such that on
an event with probability $1-e^{-\Omega(n^{\sigma/2})},$ for any $1\leq
k\leq\Delta_{0}n^{\sigma/2}$, we have

$|\theta_{i}|\frac{\mu_{c_{i}(J;k)}(\lambda_{i})}{\mu_{1}(\lambda_{i})}\leq
10^{-2}d^{-1}|\theta_{J}|\frac{\mu_{k}(\lambda_{J})}{\mu_{1}(\lambda_{J})}$
(9.4)

###### Proof.

Suppose that for $c_{j}(i;k)\leq C_{0}n^{\sigma}$, then there are at most
$k+C_{0}n^{\sigma}\leq(\Delta_{0}+C_{0})n^{\sigma}$ number of eigenvalues of
$A_{n}$ in the interval $[\lambda_{i},\lambda_{j}]$ (or
$[\lambda_{j},\lambda_{i}]$). However, if $\Delta_{0}+C_{0}$ is chosen to be
sufficiently small, this event has probability $e^{-\Omega(n^{\sigma/2})}$
according to Theorem 3.3.

For the second claim, we combine the first claim (we keep $C_{0}$ fixed and
set $\Delta_{0}$ even smaller) with Corollary 9.1 to deduce that (9.3) holds.

For the third claim, we combine our initial assumption on the subscript $J$,
the estimate in Corollary 3.6 giving a range
$\mu_{k}\in[C_{1}\sqrt{n}/k,C_{2}\sqrt{n}/k]$, and our first claim stating
that $c_{i}(j,k)$ are large enough. Fine tuning the value of $\Delta_{0}$ to
be small completes the proof. ∎

Having proven these estimates, we can derive a straightforward generalization
of Lemma 4.1 and 4.4 to $\lambda_{i}$’s at a mesoscopic distance. We outline
them here but we omit the proof, as the proofs are essentially identical.

######  Lemma 9.3.

Assume that $A_{n}$ satisfies the assumptions in Theorem 1.5 and assume that
$X_{2}\sim\operatorname{Col}_{n}(\zeta_{2})$ and
$\zeta_{2}\in\Gamma_{2}(G,K,\sigma_{0})$. Fix any $\kappa>0$ and $\Delta>0$ to
be sufficiently small, and some $\sigma\in(0,1)$. Then there exists an event
$\mathcal{E}_{1}$ with $\mathbb{P}(\mathcal{E}_{1})\geq
1-\exp(-\Omega(n^{\sigma/2}))$ such that for any $A_{n}\in\mathcal{E}_{1}$,
the following holds:

Fix any given $(\theta_{1},\cdots,\theta_{d})\in\mathbb{R}^{d}$ with
$\prod_{i=1}^{d}|\theta_{i}|=1$ , and fix any given
$\lambda_{1},\cdots,\lambda_{d}\in[-(2-\kappa)\sqrt{n},(2-\kappa)\sqrt{n}]$
with $|\lambda_{i}-\lambda_{j}|\geq\Delta n^{-\frac{1}{2}+\sigma}$ whenever
$i\neq j$.

Then there exists some $J\in\\{1,\cdots,d\\}$ (depending on $A_{n}$ and
$\theta$) such that, for any

$s\in\left(0,\frac{C\cdot\mu_{k}(\lambda_{J})}{{\left(\prod_{i=1}^{d}\mu_{1}(\lambda_{i})\right)^{1/d}}}\right)$

and any $k\leq c_{0}n^{\sigma}$, we have

$\mathbb{P}_{\widetilde{X}}\left(\left\|\sum_{i=1}^{d}\frac{\theta_{i}}{\mu_{1}(\lambda_{i})}(A_{n}-\lambda_{i}I_{n})^{-1}\widetilde{X}\right\|_{2}\leq
s\right)\lesssim se^{-k},$ (9.5)

where $c_{0}$, $C$ are universal constant depending only on the various
parameters $G,B$,$\sigma_{0}$,$K$.

######  Lemma 9.4.

Assume that $A_{n}$ satisfies the assumptions in Theorem 1.5 and that
$X_{2}\sim\operatorname{Col}_{n}(\zeta_{2})$ and
$\zeta_{2}\in\Gamma_{2}(G,K,\sigma_{0})$. Fix any $\kappa>0$ and $\Delta>0$ to
be sufficiently small, and some $\sigma\in(0,1)$. Then there exists an event
$\mathcal{E}_{2}$ with $\mathbb{P}(\mathcal{E}_{2})\geq
1-\exp(-\Omega(n^{\sigma/2}))$ such that for any $A_{n}\in\mathcal{E}_{2}$,
the following holds:

Fix any given $(\theta_{1},\cdots,\theta_{d})\in\mathbb{R}^{d}$, assume that
we can find some $\mathcal{A}\subset\\{1,\cdots,d\\}$ satisfying:
$|\mathcal{A}|=\ell$ for some $1\leq\ell\leq d-1$, that
$\prod_{i\in\mathcal{A}}|\theta_{i}|=1$ and for any $j\notin\mathcal{A}$,
$|\theta_{j}|<1$. Fix any given
$\lambda_{1},\cdots,\lambda_{d}\in[-(2-\kappa)\sqrt{n},(2-\kappa)\sqrt{n}]$
satisfying $|\lambda_{i}-\lambda_{j}|\geq\Delta n^{-\frac{1}{2}+\sigma}$
whenever $i\neq j$.

Then there exists some $J\in\\{1,\cdots,d\\}$ (depending on $A_{n}$ and
$\theta$) such that, for any

$s\in\left(0,\frac{C\cdot\mu_{k}(\lambda_{J})}{{\left(\prod_{i\in\mathcal{A}}\mu_{1}(\lambda_{i})\right)^{1/\ell}}}\right)$

and for any $k\leq c_{0}n^{\sigma}$, we have

$\mathbb{P}_{\widetilde{X}}\left(\left\|\sum_{i=1}^{d}\frac{\theta_{i}}{\mu_{1}(\lambda_{i})}(A_{n}-\lambda_{i}I_{n})^{-1}\widetilde{X}\right\|_{2}\leq
s\right)\lesssim se^{-k},$ (9.6)

where $c_{0}$ and $C$ are universal constants that depend only on the various
parameters $G,B$,$\sigma_{0}$,$K$.

Under the assumption of Theorem 1.5, the statement of Proposition 8.1 holds
almost without change. We restate it here:

######  Proposition 9.5.

Under the assumption of Theorem 1.5, for any $p>1$ we have

$\displaystyle\mathbb{P}(\sigma_{min}(A_{n+1}-\lambda_{i}I_{n+1})\leq\delta_{i}n^{-1/2},i=1,2,\cdots,d)\lesssim\delta_{1}\delta_{2}\cdots\delta_{d}+e^{-\Omega(n^{\sigma/2})}$
$\displaystyle+\mathbb{E}_{A_{n}}\sup_{r_{1},\cdots,r_{d}}\mathbb{P}_{X}\left(\frac{|\langle(A_{n}-\lambda_{i}I_{n})^{-1}X,X\rangle-
r_{i}|}{\|(A_{n}-\lambda_{i}I_{n})^{-1}X\|_{2}}\leq\delta_{i},\frac{\prod_{i=1}^{d}\mu_{1}(\lambda_{i})}{n^{d/2}}\leq(\prod_{i=1}^{n}\delta_{i})^{-p}\right).$

The only difference here, compared to Proposition 8.1 is that the
$e^{-\Omega(n)}$ error is replaced by $e^{-\Omega(n^{\sigma/2})}$. This change
comes from the induction hypothesis: in the induction hypothesis here, the
error is $e^{-\Omega(n^{\sigma/2})}$. We can then easily prove the following
analog of Lemma 8.3:

######  Lemma 9.6.

Under the assumption of Theorem 1.5, for any $\delta_{1},\cdots,\delta_{d}\geq
e^{-cn^{\sigma}}$, any $u\in\mathbb{R}^{n}$ with $\|u\|_{2}\leq d$, and any
$p>1$, we have the following estimate:

$\displaystyle\mathbb{E}_{A_{n}}\sup_{r_{1},\cdots,r_{d}}\mathbb{P}_{X}\left(\frac{|\langle(A_{n}-\lambda_{i}I_{n})^{-1}X,X\rangle-
r_{i}|}{\|(A_{n}-\lambda_{i}I_{n})^{-1}\|_{*}}\leq\delta_{i},\langle
X,u\rangle\geq
s,\frac{\prod_{i=1}^{d}\mu_{1}(\lambda_{i})}{n^{d/2}}\leq(\prod_{i=1}^{d}\delta_{i})^{-p}\right)$
(9.7) $\displaystyle\lesssim
e^{-s}\prod_{i=1}^{d}\delta_{i}+e^{-\Omega(n^{\sigma/2})}$
$\displaystyle+e^{-s}(\prod_{i=1}^{d}\delta_{i})\mathbb{E}_{A_{n}}\left[\left(\frac{\prod_{i=1}^{d}\mu_{1}(\lambda_{i})}{n^{d/2}}\right)^{1-\frac{1}{8d}}\wedge\left\\{\frac{\prod_{i=1}^{d}\mu_{1}(\lambda_{i})}{n^{d/2}}\leq(\prod_{i=1}^{d}\delta_{i})^{-p}\right\\}\right]^{\frac{8d-2}{8d-1}},$

where $c$ depends on the assumptions in Theorem, on $\kappa$ and $\Delta$.

We will not give the proof because it essentially follows the proof of Lemma
8.3. The only place where a change is made is where we take the following
decomposition

$[\prod_{i=1}^{d}\delta_{i},1]=\left[\prod_{i=1}^{d}\delta_{i},\frac{\mu_{c_{0}n^{\sigma}}(\lambda_{J})}{(\prod_{i=1}^{d}\mu_{1}(\lambda_{i}))^{1/d}}\right]\cup\bigcup_{k=2}^{c_{0}n^{\sigma}}\left[\frac{\mu_{k}(\lambda_{J})}{(\prod_{i=1}^{d}\mu_{1}(\lambda_{i}))^{1/d}},\frac{\mu_{k-1}(\lambda_{J})}{(\prod_{i=1}^{d}\mu_{1}(\lambda_{i}))^{1/d}}\right]$
(9.8)

when applying Lemma 9.3 and 9.4. The assumption that
$\prod_{i=1}^{d}\delta_{i}\geq e^{-cn^{\sigma}}$ for an appropriate $c>0$
ensures that the integral over the first interval in the decomposition (9.8)
is finite.

Now we can prove Theorem 1.2.

###### Proof of Theorem 1.5.

The proof here is identical to the proof of Theorem 1.2. We can derive the
corresponding versions of Lemma 8.4 and 8.5 where the only difference is that
we replace all $e^{-\Omega(n)}$ terms by $e^{-\Omega(n^{\sigma/2})}$. Then we
remove the log factor in exactly the same way as the proof of Theorem 1.2. The
details are omitted. ∎

## Acknowledgments

The author thanks Professor Julian Sahasrabudhe for some related discussions.

## References

  * [1] Greg W. Anderson, Alice Guionnet and Ofer Zeitouni  “An introduction to random matrices” 118, Cambridge Studies in Advanced Mathematics  Cambridge University Press, Cambridge, 2010, pp. xiv+492
  * [2] Gérard Ben Arous and Paul Bourgade  “Extreme gaps between eigenvalues of random matrices”  In _Ann. Probab._ 41.4, 2013, pp. 2648–2681
  * [3] Julius Borcea, Petter Brändén and Thomas M. Liggett  “Negative dependence and the geometry of polynomials”  In _J. Amer. Math. Soc._ 22.2, 2009, pp. 521–567
  * [4] P. Bourgade  “Mesoscopic fluctuations of the zeta zeros”  In _Probab. Theory Related Fields_ 148.3-4, 2010, pp. 479–500
  * [5] Paul Bourgade  “Extreme gaps between eigenvalues of Wigner matrices”  In _J. Eur. Math. Soc. (JEMS)_ 24.8, 2022, pp. 2823–2873
  * [6] Paul Bourgade and Krishnan Mody  “Gaussian fluctuations of the determinant of Wigner matrices”  In _Electron. J. Probab._ 24, 2019, pp. Paper No. 9628
  * [7] Paul Bourgade, Krishnan Mody and Michel Pain  “Optimal local law and central limit theorem for $\beta$-ensembles”  In _Comm. Math. Phys._ 390.3, 2022, pp. 1017–1079
  * [8] Paul Bourgade, Laszlo Erdős, Horng-Tzer Yau and Jun Yin  “Fixed energy universality for generalized Wigner matrices”  In _Comm. Pure Appl. Math._ 69.10, 2016, pp. 1815–1881
  * [9] Marcelo Campos, Letícia Mattos, Robert Morris and Natasha Morrison  “On the singularity of random symmetric matrices”  In _Duke Math. J._ 170.5, 2021, pp. 881–907
  * [10] Marcelo Campos, Matthew Jenssen, Marcus Michelen and Julian Sahasrabudhe  “The least singular value of a random symmetric matrix”  In _Forum Math. Pi_ 12, 2024, pp. Paper No. e369
  * [11] Hong-Bin Chen, Sinho Chewi and Jonathan Niles-Weed  “Dimension-free log-Sobolev inequalities for mixture distributions”  In _J. Funct. Anal._ 281.11, 2021, pp. Paper No. 10923617
  * [12] Kevin P. Costello, Terence Tao and Van Vu  “Random symmetric matrices are almost surely nonsingular”  In _Duke Math. J._ 135.2, 2006, pp. 395–413
  * [13] L. Erdësh  “Universality of Wigner random matrices: a survey of recent results”  In _Uspekhi Mat. Nauk_ 66.3(399), 2011, pp. 67–198
  * [14] C.. Esseen  “On the Kolmogorov-Rogozin inequality for the concentration function”  In _Z. Wahrscheinlichkeitstheorie und Verw. Gebiete_ 5, 1966, pp. 210–216
  * [15] Renjie Feng, Gang Tian and Dongyi Wei  “Small gaps of GOE”  In _Geom. Funct. Anal._ 29.6, 2019, pp. 1794–1827
  * [16] Stephen Cong Ge  “The Eigenvalue Spacing of IID Random Matrices and Related Least Singular Value Results” Thesis (Ph.D.)–University of California, Los Angeles  ProQuest LLC, Ann Arbor, MI, 2017, pp. 63
  * [17] Subhroshekhar Ghosh  “Determinantal processes and completeness of random exponentials: the critical case”  In _Probab. Theory Related Fields_ 163.3-4, 2015, pp. 643–665
  * [18] Alice Guionnet and Jonathan Husson  “Large deviations for the largest eigenvalue of Rademacher matrices”  In _Ann. Probab._ 48.3, 2020, pp. 1436–1465
  * [19] D.. Hanson and F.. Wright  “A bound on tail probabilities for quadratic forms in independent random variables”  In _Ann. Math. Statist._ 42, 1971, pp. 1079–1083
  * [20] Vishesh Jain, Ashwin Sah and Mehtaab Sawhney  “On the smallest singular value of symmetric random matrices”  In _Combin. Probab. Comput._ 31.4, 2022, pp. 662–683
  * [21] Galyna Livshyts, Grigoris Paouris and Peter Pivovarov  “On sharp bounds for marginal densities of product measures”  In _Israel J. Math._ 216.2, 2016, pp. 877–889
  * [22] Galyna V. Livshyts, Konstantin Tikhomirov and Roman Vershynin  “The smallest singular value of inhomogeneous square random matrices”  In _Ann. Probab._ 49.3, 2021, pp. 1286–1309
  * [23] Kyle Luh and Sean O’Rourke  “Eigenvectors and controllability of non-Hermitian random matrices and directed graphs”  In _Electron. J. Probab._ 26, 2021, pp. Paper No. 1643
  * [24] Russell Lyons  “Determinantal probability measures”  In _Publ. Math. Inst. Hautes Études Sci._ , 2003, pp. 167–212
  * [25] Krishnan Mody  “The log-characteristic polynomial of generalized wigner matrices is log-correlated”  In _arXiv preprint arXiv:2302.05956_ , 2023
  * [26] Hoi Nguyen, Terence Tao and Van Vu  “Random matrices: tail bounds for gaps between eigenvalues”  In _Probab. Theory Related Fields_ 167.3-4, 2017, pp. 777–816
  * [27] Hoi H. Nguyen  “Inverse Littlewood-Offord problems and the singularity of random symmetric matrices”  In _Duke Math. J._ 161.4, 2012, pp. 545–586
  * [28] Hoi H. Nguyen  “Random matrices: overcrowding estimates for the spectrum”  In _J. Funct. Anal._ 275.8, 2018, pp. 2197–2224
  * [29] Robin Pemantle  “Towards a theory of negative dependence” Probabilistic techniques in equilibrium and nonequilibrium statistical physics  In _J. Math. Phys._ 41.3, 2000, pp. 1371–1390
  * [30] Mark Rudelson and Roman Vershynin  “No-gaps delocalization for general random matrices”  In _Geom. Funct. Anal._ 26.6, 2016, pp. 1716–1776
  * [31] Mark Rudelson and Roman Vershynin  “Smallest singular value of a random rectangular matrix”  In _Comm. Pure Appl. Math._ 62.12, 2009, pp. 1707–1739
  * [32] Mark Rudelson and Roman Vershynin  “The Littlewood-Offord problem and invertibility of random matrices”  In _Adv. Math._ 218.2, 2008, pp. 600–633
  * [33] Terence Tao and Van Vu  “A central limit theorem for the determinant of a Wigner matrix”  In _Adv. Math._ 231.1, 2012, pp. 74–101
  * [34] Terence Tao and Van Vu  “Random matrices have simple spectrum”  In _Combinatorica_ 37.3, 2017, pp. 539–553
  * [35] Terence Tao and Van Vu  “Random matrices: universality of local eigenvalue statistics”  In _Acta Math._ 206.1, 2011, pp. 127–204
  * [36] Konstantin Tikhomirov  “Singularity of random Bernoulli matrices”  In _Ann. of Math. (2)_ 191.2, 2020, pp. 593–634
  * [37] Roman Vershynin  “High-dimensional probability” An introduction with applications in data science, With a foreword by Sara van de Geer 47, Cambridge Series in Statistical and Probabilistic Mathematics  Cambridge University Press, Cambridge, 2018, pp. xiv+284
  * [38] Roman Vershynin  “Invertibility of symmetric random matrices”  In _Random Structures Algorithms_ 44.2, 2014, pp. 135–182
  * [39] Van H. Vu  “Recent progress in combinatorial random matrix theory”  In _Probab. Surv._ 18, 2021, pp. 179–200
  * [40] Eugene P. Wigner  “On the distribution of the roots of certain symmetric matrices”  In _Ann. of Math. (2)_ 67, 1958, pp. 325–327
  * [41] F.. Wright  “A bound on tail probabilities for quadratic forms in independent random variables whose distributions are not necessarily symmetric”  In _Ann. Probability_ 1.6, 1973, pp. 1068–1070