# When a system of real quadratic equations has a solution

Alexander Barvinok  Department of Mathematics, University of Michigan, Ann
Arbor, MI 48109-1043, USA  {barvinok<EMAIL_ADDRESS>and  Mark Rudelson

(Date: October 3, 2021)

###### Abstract.

We provide a sufficient condition for solvability of a system of real
quadratic equations $p_{i}(x)=y_{i}$, $i=1,\ldots,m$, where
$p_{i}:{\mathbb{R}}^{n}\longrightarrow{\mathbb{R}}$ are quadratic forms. By
solving a positive semidefinite program, one can reduce it to another system
of the type $q_{i}(x)=\alpha_{i}$, $i=1,\ldots,m$, where
$q_{i}:{\mathbb{R}}^{n}\longrightarrow{\mathbb{R}}$ are quadratic forms and
$\alpha_{i}=\operatorname{trace}q_{i}$. We prove that the latter system has
solution $x\in{\mathbb{R}}^{n}$ if for some (equivalently, for any)
orthonormal basis $A_{1},\ldots,A_{m}$ in the space spanned by the matrices of
the forms $q_{i}$, the operator norm of $A_{1}^{2}+\ldots+A_{m}^{2}$ does not
exceed $\eta/m$ for some absolute constant $\eta>0$. The condition can be
checked in polynomial time and is satisfied, for example, for random $q_{i}$
provided $m\leq\gamma\sqrt{n}$ for an absolute constant $\gamma>0$. We prove a
similar sufficient condition for a system of homogeneous quadratic equations
to have a non-trivial solution. While the condition we obtain is of an
algebraic nature, the proof relies on analytic tools including Fourier
analysis and measure concentration.

###### Key words and phrases:

positive semidefinite relaxation, quadratic equations, algorithms

###### 2020 Mathematics Subject Classification:

Primary: 14P05. Secondary: 14Q30, 90C22

Research of AB and MR is partially supported by NSF Grants DMS 1855428 and DMS
2054408 respectively.

##  1\. Introduction and main results

###  1.1. Systems of real quadratic equations

Let $q_{1},\ldots,q_{m}:{\mathbb{R}}^{n}\longrightarrow{\mathbb{R}}$ be
quadratic forms,

$q_{i}(x)=\langle Q_{i}x,x\rangle\quad\text{for}\quad i=1,\ldots,m,$

where $Q_{i}$ are $n\times n$ symmetric matrices and

$\langle x,y\rangle=\sum_{i=1}^{n}\xi_{i}\eta_{i}\quad\text{for}\quad
x=\left(\xi_{1},\ldots,\xi_{n}\right)\quad\text{and}\quad
y=\left(\eta_{1},\ldots,\eta_{n}\right)$

is the standard scalar product in ${\mathbb{R}}^{n}$.

Let $\alpha_{1},\ldots,\alpha_{m}$ be real numbers. We want to find out when
the system of equations

(1.1) $q_{i}(x)=\alpha_{i}\quad\text{for}\quad i=1,\ldots,m$

has a solution $x\in{\mathbb{R}}^{n}$. Such systems of equations appear in
various contexts, see, for example, [6], [12], [13]. If the number $m$ of
equations is fixed in advance, one can decide in polynomial time whether the
system has a solution [1], [8], [4]. The same is true if the number $n$ of
variables is fixed in advance, in which case a polynomial time algorithm to
test feasibility exists even if $q_{i}$ are polynomials of an arbitrary
degree, see, for example, [5].

If $m$ and $n$ are both allowed to grow, the problem becomes computationally
hard. Unless the computational complexity hierarchy collapses, there is no
polynomial time algorithm to test the feasibility of (1.1). Furthermore, it is
not known whether the feasibility problem belongs to the complexity class NP.
In other words, it is not known whether one can present a polynomial size
certificate for the system (1.1) to have a solution when it is indeed feasible
(note that using repeated squaring of the type $x_{n+1}=x_{n}^{2}$, one can
construct examples of feasible systems for which no solution has a polynomial
size description).

In fact, testing the feasibility of an arbitrary system of real polynomial
equations can be easily reduced to testing the feasibility of a system (1.1).
First, we gradually reduce the degree of polynomials by introducing new
variables and equations of the type $\xi_{ij}-\xi_{i}\xi_{j}=0$, and hence
reduce a given polynomial system to a system

$q_{i}(x)=0\quad\text{for}\quad i=1,\ldots,m,$

where $q_{i}$ are quadratic, not necessarily homogeneous, polynomials. Then we
introduce another variable $\tau$ and replace the above system by a system of
homogeneous quadratic equations

$\tau^{2}q_{i}\left(\tau^{-1}x\right)=0\quad\text{for}\quad i=1,\ldots,m$

with one more quadratic constraint $\tau^{2}=1$.

We are also interested in systems of homogeneous equations

(1.2) $q_{i}(x)=0\quad\text{for}\quad i=1,\ldots,m,$

in which case we want to find out whether the system has a non-trivial
solution $x\neq 0$. The problem is also computationally hard. We briefly
sketch how an efficient algorithm for testing the existence of a non-trivial
solution in (1.2) would produce an efficient algorithm for testing the
feasibility of (1.1). Given a system (1.1), by introducing a new variable
$\tau$, as above we replace (1.1) by a system of homogeneous quadratic
equations, where we want to enforce $\tau\neq 0$. This is done by introducing
yet another variable $\sigma$ and the equation

$R^{2}\tau^{2}-\left(\xi_{1}^{2}+\ldots+\xi_{n}^{2}\right)=\sigma^{2}$

binding all variables together, so that if $\tau=0$ then all other variables
are necessarily $0$. Here $R$ is meant to be a very large constant and in
fact, it can be treated as infinitely large, with computations in the ordered
field of rational functions in $R$, the trick first introduced in [9].

In this paper, we present a computationally simple sufficient criteria for
(1.1), respectively (1.2), to have a solution, respectively a non-trivial
solution. We start with by now a standard procedure of semidefinite
relaxation.

###  1.2. Positive semidefinite relaxation

For an $n\times n$ real symmetric matrix $X$, we write $X\succeq 0$ to say
that $X$ is positive semidefinite.

Given (1.1), we consider the following system of linear equations

(1.3) $\operatorname{trace}(Q_{i}X)=\alpha_{i}\quad\text{for}\quad
i=1,\ldots,m\qquad\text{where}\qquad X\succeq 0$

in $n\times n$ positive semidefinite matrices $X$. Unlike (1.1), the system
(1.3) is convex and efficient algorithms are available to test its
feasibility, see [13] for a survey. Clearly, if
$x=\left(\xi_{1},\ldots,\xi_{n}\right)$ is a solution to (1.1) then the matrix
$X=\left(x_{ij}\right)$ defined by $x_{ij}=\xi_{i}\xi_{j}$ is a positive
semidefinite solution to (1.3). If $m\leq 2$, then the converse is true: if
the system (1.3) has a solution then so does (1.1), see, for example, Section
II.13 of [2]. For $m\geq 3$ the system (1.3) may have solutions while (1.1)
may be infeasible. For example, the system of quadratic equations

$\xi_{1}^{2}=1,\quad\xi_{2}^{2}=1\quad\text{and}\quad\xi_{1}\xi_{2}=0$

does not have a solution, whereas the $2\times 2$ identity matrix $I$ is the
solution to its positive semidefinite relaxation. One corollary of our results
is that such examples are, in some sense, “atypical”.

Our goal is to find a computationally simple criterion when a solution to
(1.3) implies the existence of a solution to (1.1).

Let $X$ be a solution to (1.3). Since $X\succeq 0$, we can write $X=TT^{\ast}$
for an $n\times n$ matrix $T$. Then

$\operatorname{trace}(Q_{i}X)=\operatorname{trace}(Q_{i}TT^{\ast})=\operatorname{trace}(T^{\ast}Q_{i}T).$

Let us define matrices

(1.4) $\widehat{Q_{i}}=T^{\ast}Q_{i}T\quad\text{for}\quad i=1,\ldots,m$

and the corresponding quadratic forms
$\widehat{q_{i}}:{\mathbb{R}}^{n}\longrightarrow{\mathbb{R}}$,

(1.5)
$\widehat{q_{i}}(x)=\langle\widehat{Q_{i}}x,x\rangle=q_{i}(Tx)\quad\text{for}\quad
i=1,\ldots,m.$

If $x\in{\mathbb{R}}^{n}$ is a solution to the system

(1.6) $\widehat{q_{i}}(x)=\alpha_{i}\quad\text{for}\quad i=1,\ldots,m$

then $y=Tx$ is a solution to (1.1). We note that

(1.7) $\alpha_{i}=\operatorname{trace}\widehat{Q_{i}}\quad\text{for}\quad
i=1,\ldots,m.$

It may happen that the system (1.1) has a solution while (1.6) does not, but
if $X$ and hence $T$ are invertible, the systems (1.1) and (1.6) are
equivalent. Furthermore, if there are no invertible $X\succeq 0$ satisfying
(1.3), then the affine subspace defined by the equations
$\operatorname{trace}(Q_{i}X)=\alpha_{i}$ intersects the cone of positive
semidefinite matrices at a proper face, and the system (1.1) can be
effectively reduced to a system of quadratic equations in fewer variables,
cf., for example, Section II.12 of [2]. Summarizing, a solution $X$ to (1.3)
allows us to replace (1.1) by a similar system, where the right hand sides
$\alpha_{i}$ are the traces of the quadratic forms in the left hand side.

Ultimately, we are interested in finding out when the system (1.6) of
quadratic equations with additional conditions (1.7) has a solution
$x\in{\mathbb{R}}^{n}$.

###  1.3. Reduction to an orthonormal basis and the main result

Before we state our main result, some remarks are in order. As agreed, we
consider the system (1.1) where $\alpha_{i}=\operatorname{trace}q_{i}$.
Without loss of generality, we assume that the quadratic forms $q_{i}$ and
hence their matrices $Q_{i}$ are linearly independent. For an invertible
$m\times m$ matrix $M=\left(\mu_{ij}\right)$, let us define new forms

$\tilde{q}_{i}=\sum_{j=1}^{m}\mu_{ij}q_{j}\quad\text{for}\quad i=1,\ldots,m$

and new right hand sides

$\tilde{\alpha_{i}}=\sum_{j=1}^{m}\mu_{ij}\alpha_{j}\quad\text{for}\quad
i=1,\ldots,m.$

Then the system (1.1) has a solution if and only if the system

$\tilde{q}_{i}(x)=\tilde{\alpha}_{i}\quad\text{for}\quad i=1,\ldots,m$

has a solution. Hence, ideally, a criterion for the system (1.1) to have a
solution should depend not on the forms $q_{1},\ldots,q_{m}$ per se (or their
matrices $Q_{1},\ldots,Q_{m}$) but on the subspace
$\operatorname{span}\left(q_{1},\ldots,q_{m}\right)$ in the space of quadratic
forms (equivalently, on the subspace
$\operatorname{span}\left(Q_{1},\dots,Q_{m}\right)$ in the space of $n\times
n$ real symmetric matrices).

We consider the standard inner product in space of $n\times n$ real matrices:

$\langle X,Y\rangle=\operatorname{trace}X^{\ast}Y.$

In particular, for symmetric matrices $X=\left(\xi_{ij}\right)$ and
$Y=\left(\eta_{ij}\right)$ we have

$\langle X,Y\rangle=\operatorname{trace}XY=\sum_{1\leq i,j\leq
n}\xi_{ij}\eta_{ij}$

and the space of $n\times n$ symmetric matrices becomes a Euclidean space.

We will be using the following observation. Let ${\mathcal{L}}$ be a subspace
in the space of $n\times n$ symmetric matrices and let $A_{1},\ldots,A_{m}$ be
an orthonormal basis of ${\mathcal{L}}$, so that

$\langle
A_{i},A_{j}\rangle=\operatorname{trace}A_{i}A_{j}=\begin{cases}1&\text{if\
}i=j,\\\ 0&\text{if\ }i\neq j.\end{cases}$

Then the matrix $A_{1}^{2}+\ldots+A_{m}^{2}$ does not depend on a choice of an
orthonormal basis and hence is an invariant of the subspace ${\mathcal{L}}$.
Indeed, if $B_{1},\ldots,B_{m}$ is another orthonormal basis of
${\mathcal{L}}$, then

$B_{i}=\sum_{j=1}^{m}\mu_{ij}A_{j}\quad\text{for}\quad i=1,\ldots,m$

and some orthogonal matrix $M=\left(\mu_{ij}\right)$ and hence

$\sum_{i=1}^{m}B_{i}^{2}=\sum_{i=1}^{m}\left(\sum_{1\leq j_{1},j_{2}\leq
m}\mu_{ij_{1}}\mu_{ij_{2}}A_{j_{1}}A_{j_{2}}\right)=\sum_{1\leq
j_{1},j_{2}\leq
m}\left(\sum_{i=1}^{m}\mu_{ij_{1}}\mu_{ij_{2}}\right)A_{j_{1}}A_{j_{2}}=\sum_{j=1}^{m}A_{j}^{2}.$

For an $n\times n$ real symmetric matrix $Q$, we denote by
$\|Q\|_{\mathrm{op}}$ the operator norm of $Q$, that is, the largest absolute
value of an eigenvalue of $Q$.

We prove the following main result.

######  Theorem 1.1.

There is an absolute constant $\eta>0$ such that the following holds. Let
$Q_{1},\ldots,Q_{m}$, $m\geq 3$, be linearly independent $n\times n$ symmetric
matrices and let $q_{i}:{\mathbb{R}}^{n}\longrightarrow{\mathbb{R}}$ for
$i=1,\ldots,m$ be the corresponding quadratic forms,

$q_{i}(x)=\langle Q_{i}x,x\rangle\quad\text{for}\quad i=1,\ldots,m.$

Suppose that

$\left\|\sum_{i=1}^{m}A_{i}^{2}\right\|_{\mathrm{op}}\ \leq\ \frac{\eta}{m}$

for some (equivalently, for any) orthonormal basis $A_{1},\ldots,A_{m}$ of the
subspace
$\operatorname{span}\left(Q_{1},\ldots,Q_{m}\right)$. Then the system of
quadratic equations

$q_{i}(x)=\operatorname{trace}Q_{i}\quad\text{for}\quad i=1,\ldots,m$

has a solution $x\in{\mathbb{R}}^{n}$.

We prove a similar result for systems of homogeneous quadratic equations,
where we are interested in finding a non-trivial solution.

######  Theorem 1.2.

There is an absolute constant $\eta>0$ such that the following holds. Let
$Q_{1},\ldots,Q_{m}$, $m\geq 3$, be $n\times n$ real symmetric matrices such
that

$\operatorname{trace}Q_{i}=0\quad\text{for}\quad i=1,\ldots,m,$

and let $q_{i}:{\mathbb{R}}^{n}\longrightarrow{\mathbb{R}}$,

$q_{i}(x)=\langle Q_{i}x,x\rangle\quad\text{for}\quad i=1,\ldots,m,$

be the corresponding quadratic forms. Suppose that

$\left\|\sum_{i=1}^{m}A_{i}^{2}\right\|_{\mathrm{op}}\ \leq\ \frac{\eta}{m}$

for some (equivalently, for any) orthonormal basis $A_{1},\ldots,A_{m}$ of the
subspace
$\operatorname{span}\left(Q_{1},\ldots,Q_{m}\right)$. Then the system (1.2) of
equations has a solution $x\neq 0$.

######  Remark 1.3.

Our proofs of Theorems 1.1 and 1.2 work for $\eta=10^{-6}$, however, we made
no effort to optimize this constant.

Note that the operator norm of the matrix $\sum_{i=1}^{m}A_{i}^{2}$ is its
largest eigenvalue. Thus, the criterion appearing in Theorems 1.1 and 1.2 is
algebraic like the problem itself. Despite that, the proofs of these theorems
rely on analytic tools: introduction of the Gaussian measure, the Fourier
transform asymptotic, and the measure concentration. We discuss this in more
detail in Section 2.

###  1.4. Discussion

####  1.4.1. Computational complexity

Given matrices $Q_{1},\ldots,Q_{m}$, one can compute an orthonormal basis
$A_{1},\ldots,A_{m}$ of $\operatorname{span}\left(Q_{1},\ldots,Q_{m}\right)$,
using, for example, the Gram-Schmidt orthogonalization process. Then one can
check the inequality for the operator norm of $A_{1}^{2}+\ldots+A_{m}^{2}$.
These are standard linear algebra problems that can be solved in polynomial
time. However, we don’t know how to find a solution $x$ in polynomial time or
whether a solution $x$ with a polynomial size description even exists when the
conditions of Theorems 1.1 and 1.2 are satisfied.

####  1.4.2. The case of random matrices

Let $Q_{1},\ldots,Q_{m}$ be independent symmetric random matrices with entries
above the diagonal being independent normal random variables of expectation
$0$ and variance $1$ and the diagonal entries being normal of expectation $0$
and variance $2$. In other words, up to the scaling factor of $\sqrt{n}$, the
matrices $Q_{1},\ldots,Q_{m}$ are sampled independently from the Gaussian
Orthogonal Ensemble (GOE).

We assume that $m\leq n$. As $n$ grows, with high probability we have (we
ignore low-order terms)

$\|Q_{i}\|_{\mathrm{op}}\approx 2\sqrt{n}\quad\text{and}\quad\langle
Q_{i},Q_{i}\rangle\approx n^{2}\quad\text{for}\quad i=1,\ldots,m,$

see, for example, Section 2.3 of [14].

Let $A_{1},\ldots,A_{m}$ be the orthonormal basis of
$\operatorname{span}\left(Q_{1},\ldots,Q_{m}\right)$ obtained by the Gram -
Schmidt orthogonalization from $Q_{1},\ldots,Q_{m}$. Then, up to a normalizing
factor, each $A_{i}$ is also sampled from GOE, so we have

$\|A_{i}\|_{\mathrm{op}}\approx\frac{2}{\sqrt{n}}\quad\text{for}\quad
i=1,\ldots,m,$

with high probability. Hence

$\left\|\sum_{i=1}^{m}A_{i}^{2}\right\|_{\mathrm{op}}\ \leq\
\sum_{i=1}^{m}\|A_{i}\|^{2}_{\mathrm{op}}\ \approx\ \frac{4m}{n}.$

Hence if $m\leq\sqrt{\eta n}/2$, with high probability the conditions of
Theorems 1.1 and 1.2 are satisfied. Similar behavior can be observed for other
models of random symmetric matrices with independent entries sampled from a
distribution with expectation 0, variance 1 and sub-Gaussian tail. Informally,
for the conditions of Theorems 1.1 and 1.2 to hold, we want $n$ to be
substantially larger than $m$ and the subspace
$\operatorname{span}\left(Q_{1},\ldots,Q_{m}\right)$ to be sufficiently
generic.

####  1.4.3. The metric geometry of the cone of positive semidefinite matrices

As before, we consider the space $\operatorname{Sym}_{n}$ of $n\times n$
symmetric matrices as a Euclidean space. Let
${\mathcal{S}}_{+}\subset\operatorname{Sym}_{n}$ be the convex cone of
positive semidefinite matrices. From Section 1.4.2, we deduce the following
metric property of ${\mathcal{S}}_{+}$: There is an absolute constant
$\gamma>0$ such that if ${\mathcal{A}}\subset\operatorname{Sym}_{n}$ is a
random affine subspace with $\operatorname{codim}A\leq\gamma\sqrt{n}$
containing the identity matrix $I_{n}$, then ${\mathcal{A}}$ contains a
positive semidefinite matrix of rank 1 with probability approaching $1$ as $n$
grows.

We don’t know if the estimates of Theorem 1.1 and Sections 1.4.2 and 1.4.3 are
optimal, or, for example, whether we can make $m$ in Section 1.4.2 and
$\operatorname{codim}{\mathcal{A}}$ in Section 1.4.3 proportional to $n$
instead of $\sqrt{n}$. There is a vast literature on the average
characteristics of the set of solutions for systems of real polynomial
equations, see, for example, [7] and reference therein, but much less appears
to be known regarding solvability of such systems with high probability.

####  1.4.4. Solving positive semidefinite relaxation

Suppose we want to apply Theorem 1.1 to test the solvability of the original
system (1.1), where we do not necessarily have
$\alpha_{i}=\operatorname{trace}q_{i}$. We begin by looking for a solution $X$
to the positive semidefinite program (1.3). If there is no solution $X$, we
conclude that the system (1.1) has no solutions. If there is a solution
$X\succeq 0$ with $\operatorname{rank}X\leq 1$, we conclude that the system
(1.1) has a solution. The difficulty arises when we find a solution $X\succeq
0$ but with $\operatorname{rank}X>1$. It is known that if there is a solution
$X\succeq 0$, then there is a solution $X\succeq 0$ with an additional
constraint

$\operatorname{rank}X\ \leq\
\left\lfloor\frac{\sqrt{8m+1}-1}{2}\right\rfloor.$

Any extreme point of the set of solutions to (1.3) satisfies this condition,
see, for example, Section II.13 of [2]. Curiously, if we are to use Theorem
1.1 to ascertain the existence of a solution, it makes sense to try to find an
$X\succeq 0$ not on the boundary, but as close as possible to the “middle” of
the set of solutions of (1.3) because we want the transformed matrices
$\widehat{Q}_{i}$ given by (1.4) to be as generic as possible. For example,
one can look for $X$ with the maximum von Neumann entropy

$\sum_{j=1}^{n}\lambda_{j}\ln\frac{1}{\lambda_{j}},$

where $\lambda_{1},\ldots,\lambda_{n}$ are the eigenvalues of $X$, see, for
example, [15]. Finding such an $X$ is a convex optimization problem and hence
can be solved efficiently. Informally, if the number $m$ of equations is
rather small compared to the number $n$ of variables, if the matrices
$Q_{1},\ldots,Q_{m}$ of equations in (1.1) are sufficiently generic, and if
the solutions $X$ to the positive semidefinite relaxation (1.3) can be found
deep enough the cone of ${\mathcal{S}_{+}}$ positive semidefinite matrices,
then the system (1.1) will have a solution.

We note that in the homogeneous case one should also be careful about working
with the positive semidefinite relaxation. Namely, if $X\succeq 0$ is a
solution to the system of equations

(1.8) $\operatorname{trace}(Q_{i}X)=0\quad\text{for}\quad i=1,\ldots,m,$

we factor $X=TT^{\ast}$, define $\widehat{Q_{i}}$ by (1.4) and define
$\widehat{q_{i}}$ by (1.5), then to deduce the existence of a non-trivial
solution to the system (1.2) from the existence of a non-trivial solution to
the system

$\widehat{q_{i}}(x)=0\quad\text{for}\quad i=1,\ldots,m,$

we must require $T$ and hence $X$ to be invertible. If there are no invertible
$X\succeq 0$ satisfying (1.8), we reduce (1.2) to a system of homogeneous
quadratic equations in fewer variables, see Section 1.2.

In the rest of the paper, we prove Theorems 1.1 and 1.2. Although the
statements are real algebraic, our proofs use analytic methods, in particular,
the Fourier transform.

##  2\.  Outline of the proof

In what follows, we denote the imaginary unit by $\sqrt{-1}$, so as to use $i$
for indices.

Let $Q_{1},\ldots,Q_{m}$ be $n\times n$ real symmetric matrices and let $I$ be
the $n\times n$ identity matrix. For real $\tau_{1},\ldots,\tau_{m}$, we
consider the matrix

$Q(t)=I-\sqrt{-1}\sum_{i=1}^{m}\tau_{i}Q_{i}\quad\text{for}\quad
t=\left(\tau_{1},\ldots,\tau_{m}\right).$

Since the eigenvalues $\lambda_{1}(t),\ldots,\lambda_{n}(t)$ of the linear
combination $\sum_{i=1}^{m}\tau_{i}Q_{i}$ are real, we have

$\det Q(t)=\prod_{i=1}^{n}\left(1-\sqrt{-1}\lambda_{i}(t)\right)\neq
0\quad\text{for all}\quad t\in{\mathbb{R}}^{m}.$

Therefore, we can pick a branch of

$\det^{\quad-\frac{1}{2}}Q(t),$

which we select in such a way so that at $t=0$ we get $1$.

It is also more convenient to rescale and define quadratic forms by

$q(x)=\frac{1}{2}\langle Qx,x\rangle.$

Our proof of Theorems 1.1 hinges on the analysis of the Fourier transform of
the function $F(t):=\det^{-\frac{1}{2}}Q(t),\ t\in\mathbb{R}^{m}$. Namely, we
prove the following result.

######  Theorem 2.1.

Let $Q_{1},\ldots,Q_{m}$ be $n\times n$ real symmetric matrices, let

$q_{i}(x)=\frac{1}{2}\langle Q_{i}x,x\rangle\quad\text{for}\quad
i=1,\ldots,m,$

be the corresponding quadratic forms and let $\alpha_{1},\ldots,\alpha_{m}$ be
real numbers. Suppose that

(2.1)
$\int_{{\mathbb{R}}^{m}}\left|\det^{\quad-\frac{1}{2}}\left(I-\sqrt{-1}\sum_{i=1}^{m}\tau_{i}Q_{i}\right)\right|\
dt\ <\ +\infty$

and that

(2.2)
$\int_{{\mathbb{R}}^{m}}\det^{\quad-\frac{1}{2}}\left(I-\sqrt{-1}\sum_{i=1}^{m}\tau_{i}Q_{i}\right)\exp\left\\{-\sqrt{-1}\sum_{i=1}^{m}\alpha_{i}\tau_{i}\right\\}\
dt\ \neq 0.$

Then the system (1.1) of equations has a solution $x\in{\mathbb{R}}^{n}$.

We prove a similar result for homogeneous systems.

######  Theorem 2.2.

Let $Q_{1},\ldots,Q_{m}$ and $q_{1},\ldots,q_{m}$ be as in Theorem 2.1 and
assume, additionally, that $m<n$. Suppose that

$\int_{{\mathbb{R}}^{m}}\det^{\quad-\frac{1}{2}}\left(I-\sqrt{-1}\sum_{i=1}^{m}\tau_{i}Q_{i}\right)\
dt\ \neq 0,$

where the integral converges absolutely. Then the system (1.2) of equations
has a solution $x\neq 0$.

We prove Theorems 2.1 and 2.2 in Section 3. Theorems 1.1 and 1.2 are deduced
from Theorems 2.1 and 2.2 respectively. Since the proofs are very similar,
below we discuss the plan of the proof of Theorem 1.1 only.

First, we note that we can replace matrices $Q_{1},\ldots,Q_{m}$ by an
orthonormal set of matrices $A_{1},\ldots,A_{m}$ and quadratic forms $q_{i}$
by quadratic forms

$a_{i}(x)=\frac{1}{2}\langle A_{i}x,x\rangle\quad\text{for}\quad
i=1,\ldots,m.$

We let

$\alpha_{i}=\frac{1}{2}\operatorname{trace}A_{i}$

and consider an equivalent system

$a_{i}(x)=\alpha_{i}\quad\text{for}\quad i=1,\ldots,m$

of quadratic equations, see Section 1.3.

Using Theorem 2.1, we conclude that it suffices to prove that

(2.3)
$\int_{{\mathbb{R}}^{m}}\det^{\quad-\frac{1}{2}}\left(I-\sqrt{-1}\sum_{i=1}^{m}\tau_{i}A_{i}\right)\exp\left\\{-\sqrt{-1}\sum_{i=1}^{m}\alpha_{i}\tau_{i}\right\\}\
dt\neq 0,$

where the integral converges absolutely. Up to a scaling normalization factor,
we rewrite the integral in polar coordinates as follows.

Let ${\mathbb{S}}^{m-1}\subset{\mathbb{R}}^{m}$ be the unit sphere endowed
with the Haar probability measure. For $w\in{\mathbb{S}}^{m-1}$,
$w=\left(\omega_{1},\ldots,\omega_{m}\right)$, we define the matrix

$A(w)=\sum_{i=1}^{m}\omega_{i}A_{i}.$

Up to a non-zero scaling factor, in polar coordinates the integral (2.3) can
be written as

(2.4)
$\int_{{\mathbb{S}}^{m-1}}\left(\int_{0}^{+\infty}\tau^{m-1}\det^{\quad-\frac{1}{2}}\left(I-\sqrt{-1}\tau
A(w)\right)\exp\left\\{-\frac{\sqrt{-1}\tau}{2}\operatorname{trace}A(w)\right\\}\
d\tau\right)dw.$

The rest of the proof relies on an analysis of this integral. As a first step,
we show that the contribution of the tail of the inside integral in (2.4) is
negligible. Namely, we prove in Lemma 5.1 that for any
$w\in{\mathbb{S}}^{m-1}$, we have

(2.5)
$\int_{5\sqrt{m}}^{+\infty}\tau^{m-1}\left|\det^{\quad-\frac{1}{2}}\left(I-\sqrt{-1}\tau
A(w)\right)\right|\ d\tau\ \leq\ \frac{1}{20m}m^{m/2}e^{-3m}.$

In particular, this proves that the integral (2.4) converges absolutely and
that the integrals (2.4) and (2.3) are equal, up to a scaling factor that is
the surface area of the unit sphere
${\mathbb{S}}^{m-1}\subset{\mathbb{R}}^{m}$.

This allows us to consider the integration over the interval $[0,5\sqrt{m}]$
in the inner integral in (2.4). To analyze this integral, denote by
$\lambda_{1}(w),\ldots,\lambda_{n}(w)$ the eigenvalues of $A(w)$. A simple
calculation yields

$\displaystyle\det^{\quad-\frac{1}{2}}\left(I-\sqrt{-1}\tau
A(w)\right)\exp\left\\{-\frac{\sqrt{-1}\tau}{2}\operatorname{trace}A(w)\right\\}$
$\displaystyle=\exp\left\\{\frac{1}{2}\sum_{k=2}^{\infty}\frac{(\tau\sqrt{-1})^{k}}{k}\sum_{j=1}^{n}\lambda_{j}^{k}(w)\right\\},$

see the derivation in (5.1). Note that the summation starts from $k=2$. This
is achieved due to the first step in the argument allowing us to set
$\alpha_{i}=\frac{1}{2}\operatorname{trace}A_{i}$. Moreover,
$\sum_{j=1}^{n}\lambda_{j}^{2}(w)=1$ for all $w\in{\mathbb{S}}^{m-1}$ due to
orthonormality of the matrices $A_{1},\ldots,A_{m}$.

Next, we divide the points $w\in{\mathbb{S}}^{m-1}$ into tame and wild. For a
tame point, we show that the term corresponding to $k=2$ in the expression
above is dominating which would mean that the expression above is close to
$\exp\left\\{-\frac{\tau^{2}}{4}\right\\}$. To prove it, we need to control
$\sum_{j=1}^{n}\lambda_{j}^{k}(w)$ for all $k\geq 3$. However, as we show
below, a control for $k=3,4$ turns out to be sufficient. More precisely, we
classify a point $w\in{\mathbb{S}}^{m-1}$ as tame if

$\left|\sum_{j=1}^{n}\lambda_{j}^{3}(w)\right|\ \leq\
\frac{1}{25m^{3/2}}\quad\text{and}\quad\sum_{j=1}^{n}\lambda_{j}^{4}(w)\ \leq\
\frac{1}{625m^{2}}.$

The second inequality here is a bound on the 4-Schatten norm of $A(w)$:
$\|A(w)\|_{\mathrm{S_{4}}}\leq 1/(625m^{2})$. In contrast to it, the first
inequality bounds the third moment of the eigenvalues, and not the 3-Schatten
norm, as we have to exploit the cancellation of positive and negative
eigenvalues.

In Lemma 5.2, we prove that if $w\in{\mathbb{S}}^{m-1}$ is tame, then

(2.6)
$\begin{split}&\Re\thinspace\int_{0}^{5\sqrt{m}}\tau^{m-1}\det^{\quad-\frac{1}{2}}\left(I-\sqrt{-1}\tau
A(w)\right)\exp\left\\{-\frac{\sqrt{-1}\tau}{2}\operatorname{trace}A(w)\right\\}\
d\tau\\\ \geq\
&\frac{1}{2}\int_{0}^{5\sqrt{m}}\tau^{m-1}\exp\left\\{-\frac{\tau^{2}}{4}\right\\}\
d\tau\approx 2^{m-2}\Gamma\left(\frac{m}{2}\right).\end{split}$

We note that the value of (2.6) is much larger than the tail estimate (2.5).
Moreover, in Lemmas 4.1 and 4.2 we bound the expectations

(2.7) $\mathbb{E\thinspace}\left(\sum_{j=1}^{n}\lambda_{j}^{3}(w)\right)^{2}\
\leq\
\frac{120\eta}{m(m+2)(m+4)}\quad\text{and}\quad\mathbb{E\thinspace}\sum_{j=1}^{n}\lambda_{j}^{4}(w)\
\leq\ \frac{3\eta}{(m+2)m}.$

This is the point where the quantity
$\left\|\sum_{i=1}^{m}A_{i}^{2}\right\|_{\mathrm{op}}$ reveals itself. It
turns out that both expectations above can be controlled in terms of this
operator norm alone.

It follows then by the Markov inequality that a random
$w\in{\mathbb{S}}^{m-1}$ is tame with probability at least $7/8$, and hence
tame points $w\in{\mathbb{S}}^{m-1}$ contribute significantly to the integral
(2.4).

It remains to show that the contribution of wild points
$w\in{\mathbb{S}}^{m-1}$ cannot offset the contribution of tame points.

This relies on a concentration inequality for the 4-Schatten norm of matrices
$A(w)$ on the unit sphere ${\mathbb{S}}^{m-1}$, which we derive in Lemma 4.4.
This inequality is leveraged against the deterioration of the bounds on the
eigenvalues of $A(w)$ which occurs for the wild points. To this end, we
partition the set of wild points into a number of subsets according to the
size of $\|A(w)\|_{\mathrm{S_{4}}}$, and apply the concentration inequality to
prove that the contribution of the points in each layer to the integral (2.4)
is negligible.

This argument is carried out in Section 6.

In Sections 4 and 5, we do some preliminary work: we prove bounds (2.7) as
well as some other useful bounds on the eigenvalues of $A(w)$ in Section 4. In
Section 5 we derive (2.5) and show that a similar integral over the interval
$[0,5\sqrt{m}]$ can be controlled by $\|A(w)\|_{\mathrm{op}}$, which is in
turn bounded in terms of $\|A(w)\|_{\mathrm{S_{4}}}$.

##  3\. Proofs of Theorems 2.1 and 2.2

###  3.1. Enter Gaussian measure

We consider the standard Gaussian measure in ${\mathbb{R}}^{n}$ with density

$\frac{1}{(2\pi)^{n/2}}e^{-\|x\|^{2}/2}\quad\text{where}\quad\|x\|=\sqrt{\xi_{1}^{2}+\ldots+\xi_{n}^{2}}\quad\text{for}\quad
x=\left(\xi_{1},\ldots,\xi_{n}\right).$

Considering a quadratic form $q(x)=\langle Qx,x\rangle$ as a random variable,
we observe that

$\mathbb{E\thinspace}q=\operatorname{trace}Q,$

so that the equation $q(x)=\operatorname{trace}Q$ “holds on average”.

The proof of Theorems 2.1 and 2.2 is based on a Fourier transform formula.

######  Lemma 3.1.

Let $Q_{1},\ldots,Q_{m}$ be $n\times n$ real symmetric matrices and let

$q_{i}(x)=\frac{1}{2}\langle Q_{i}x,x\rangle\quad\text{for}\quad
i=1,\ldots,m,$

be the corresponding quadratic forms. Then for any real
$\alpha_{1},\ldots,\alpha_{m}$ and any real $\sigma>0$, we have

$\begin{split}&\frac{1}{(2\pi)^{n/2}}\int_{{\mathbb{R}}^{n}}\exp\left\\{-\frac{\sigma^{2}}{2}\sum_{i=1}^{m}\left(q_{i}(x)-\alpha_{i}\right)^{2}\right\\}e^{-\|x\|^{2}/2}\
dx\\\
=&\frac{1}{\sigma^{m}(2\pi)^{m/2}}\int_{{\mathbb{R}}^{m}}\det^{\quad-\frac{1}{2}}\left(I-\sqrt{-1}\sum_{i=1}^{m}\tau_{i}Q_{i}\right)\exp\left\\{-\sqrt{-1}\sum_{i=1}^{m}\alpha_{i}\tau_{i}\right\\}e^{-\|t\|^{2}/2\sigma^{2}}\
dt.\end{split}$

###### Proof.

As is well-known, for a positive definite matrix $Q$ and the corresponding
form

$q(x)=\frac{1}{2}\langle Qx,x\rangle$

we have

$\frac{1}{(2\pi)^{n/2}}\int_{{\mathbb{R}}^{n}}e^{-q(x)}\
dx=\det^{\quad-\frac{1}{2}}Q.$

Consequently, for $t\in{\mathbb{R}}^{m}$,
$t=\left(\tau_{1},\ldots,\tau_{m}\right)$, in a sufficiently small
neighborhood of $0$, we have

$\frac{1}{(2\pi)^{n/2}}\int_{{\mathbb{R}}^{n}}\exp\left\\{\sum_{i=1}^{m}\tau_{i}q_{i}(x)\right\\}e^{-\|x\|^{2}/2}\
dx=\det^{\quad-\frac{1}{2}}\left(I-\sum_{i=1}^{m}\tau_{i}Q_{i}\right).$

Since both sides of the formula are analytic in
$\tau_{1},\ldots,\tau_{m}\in{\mathbb{C}}$ for $\Re\tau_{1},\ldots,\Re\tau_{m}$
in a small neighborhood of $0$, we conclude that the above formula holds for
all such $\tau_{1},\ldots,\tau_{m}$ and that, in particular,

$\begin{split}&\frac{1}{(2\pi)^{n/2}}\int_{{\mathbb{R}}^{n}}\exp\left\\{\sqrt{-1}\sum_{i=1}^{m}\tau_{i}q_{i}(x)\right\\}e^{-\|x\|^{2}/2}\
dx\\\
=&\det^{\quad-\frac{1}{2}}\left(I-\sqrt{-1}\sum_{i=1}^{m}\tau_{i}Q_{i}\right)\end{split}$

for all real $\tau_{1},\ldots,\tau_{m}$.

Therefore,

(3.1)
$\begin{split}&\frac{1}{(2\pi)^{n/2}}\int_{{\mathbb{R}}^{n}}\exp\left\\{\sqrt{-1}\sum_{i=1}^{m}\tau_{i}\left(q_{i}(x)-\alpha_{i}\right)\right\\}e^{-\|x\|^{2}/2}\
dx\\\
=&\det^{\quad-\frac{1}{2}}\left(I-\sqrt{-1}\sum_{i=1}^{m}\tau_{i}Q_{i}\right)\exp\left\\{-\sqrt{-1}\sum_{i=1}^{m}\alpha_{i}\tau_{i}\right\\}\end{split}$

for all real $\tau_{1},\ldots,\tau_{m}$.

Next, we use a well-known formula: for $\sigma>0$ and any real (or complex)
$\alpha$, we have

$\frac{1}{\sigma\sqrt{2\pi}}\int_{-\infty}^{+\infty}\exp\left\\{\sqrt{-1}\alpha\tau\right\\}\exp\left\\{-\frac{\tau^{2}}{2\sigma^{2}}\right\\}\
d\tau=\exp\left\\{-\frac{\alpha^{2}\sigma^{2}}{2}\right\\}.$

Integrating both sides of (3.1) for $i=1,\ldots,m$ over
$\tau_{i}\in{\mathbb{R}}$ with density

$\frac{1}{\sigma\sqrt{2\pi}}\exp\left\\{-\frac{\tau_{i}^{2}}{2\sigma^{2}}\right\\},$

we get the desired formula. ∎

Now we are ready to prove Theorem 2.1.

###### Proof of Theorem 2.1.

By Lemma 3.1, for all $\sigma>0$, we have

(3.2)
$\begin{split}&\sigma^{m}\int_{{\mathbb{R}}^{n}}\exp\left\\{-\frac{\sigma^{2}}{2}\sum_{i=1}^{m}\left(q_{i}(x)-\alpha_{i}\right)^{2}\right\\}e^{-\|x\|^{2}/2}\
dx=\\\
&(2\pi)^{\frac{n-m}{2}}\int_{{\mathbb{R}}^{m}}\det^{\quad-\frac{1}{2}}\left(I-\sqrt{-1}\sum_{i=1}^{m}\tau_{i}Q_{i}\right)\exp\left\\{-\sqrt{-1}\sum_{i=1}^{m}\alpha_{i}\tau_{i}\right\\}e^{-\frac{\|t\|^{2}}{2\sigma^{2}}}\
dt.\end{split}$

As $\sigma\longrightarrow+\infty$, the right hand side of (3.2) converges to

$(2\pi)^{\frac{n-m}{2}}\int_{{\mathbb{R}}^{m}}\det^{\quad-\frac{1}{2}}\left(I-\sqrt{-1}\sum_{i=1}^{m}\tau_{i}Q_{i}\right)\exp\left\\{-\sqrt{-1}\sum_{i=1}^{m}\alpha_{i}\tau_{i}\right\\}\neq
0.$

Suppose that the system (1.1) has no solutions $x\in{\mathbb{R}}^{n}$. We
intend to obtain a contradiction by showing that the left hand side of (3.2)
converges to $0$ as $\sigma\longrightarrow+\infty$.

Let

$\gamma=(2\pi)^{\frac{n-m}{2}}\int_{{\mathbb{R}}^{m}}\left|\det^{\quad-\frac{1}{2}}\left(I-\sqrt{-1}\sum_{i=1}^{m}\tau_{i}Q_{i}\right)\right|\
dt\ <\ +\infty.$

Let us choose a $\rho>0$, to be adjusted later. Then

$\begin{split}&\sigma^{m}\int_{x\in{\mathbb{R}}^{n}:\
\|x\|>\rho}\exp\left\\{-\frac{\sigma^{2}}{2}\sum_{i=1}^{m}\left(q_{i}(x)-\alpha_{i}\right)^{2}\right\\}e^{-\|x\|^{2}/2}\
dx\\\ \leq\ &e^{-\rho^{2}/4}\sigma^{m}\int_{x\in{\mathbb{R}}^{n}:\
\|x\|>\rho}\exp\left\\{-\frac{\sigma^{2}}{2}\sum_{i=1}^{m}\left(q_{i}(x)-\alpha_{i}\right)^{2}\right\\}e^{-\|x\|^{2}/4}\
dx\\\ \leq\
&e^{-\rho^{2}/4}\sigma^{m}\int_{{\mathbb{R}}^{n}}\exp\left\\{-\frac{\sigma^{2}}{2}\sum_{i=1}^{m}\left(q_{i}(x)-\alpha_{i}\right)^{2}\right\\}e^{-\|x\|^{2}/4}\
dx\\\
=&e^{-\rho^{2}/4}2^{n/2}\sigma^{m}\int_{{\mathbb{R}}^{n}}\exp\left\\{-\frac{\sigma^{2}}{2}\sum_{i=1}^{m}\left(2q_{i}(x)-\alpha_{i}\right)^{2}\right\\}e^{-\|x\|^{2}/2}\
dx\\\
=&e^{-\rho^{2}/4}2^{n/2}\sigma^{m}\int_{{\mathbb{R}}^{n}}\exp\left\\{-{\frac{(2\sigma)^{2}}{2}}\sum_{i=1}^{m}\left(q_{i}(x)-\frac{\alpha_{i}}{2}\right)^{2}\right\\}e^{-\|x\|^{2}/2}\
dx\\\
=&e^{-\rho^{2}/4}2^{n/2}2^{-m}(2\sigma)^{m}\int_{{\mathbb{R}}^{n}}\exp\left\\{-{\frac{(2\sigma)^{2}}{2}}\sum_{i=1}^{m}\left(q_{i}(x)-\frac{\alpha_{i}}{2}\right)^{2}\right\\}e^{-\|x\|^{2}/2}\
dx.\end{split}$

From Lemma 3.1,

$\begin{split}&(2\sigma)^{m}\int_{{\mathbb{R}}^{n}}\exp\left\\{-\frac{(2\sigma)^{2}}{2}\sum_{i=1}^{m}\left(q_{i}(x)-\frac{\alpha_{i}}{2}\right)^{2}\right\\}e^{-\|x\|^{2}/2}\
dx\\\ \leq\
&(2\pi)^{\frac{n-m}{2}}\int_{{\mathbb{R}}^{m}}\left|\det^{\quad-\frac{1}{2}}\left(I-\sqrt{-1}\sum_{i=1}^{m}\tau_{i}Q_{i}\right)\right|\
dt=\gamma.\end{split}$

Summarizing,

$\begin{split}&\sigma^{m}\int_{x\in{\mathbb{R}}^{n}:\
\|x\|>\rho}\exp\left\\{-\frac{\sigma^{2}}{2}\sum_{i=1}^{m}\left(q_{i}(x)-\alpha_{i}\right)^{2}\right\\}e^{-\|x\|^{2}/2}\
dx\\\ \leq\ &e^{-\rho^{2}/4}2^{n/2}2^{-m}\gamma.\end{split}$

Given $\epsilon>0$, we choose $\rho(\epsilon)>0$ such that

$e^{-\rho^{2}(\epsilon)/4}2^{n/2}2^{-m}\gamma\ \leq\ \frac{\epsilon}{2},$

so that for all $\sigma>0$ we have

(3.3) $\sigma^{m}\int_{x\in{\mathbb{R}}^{n}:\
\|x\|>\rho(\epsilon)}\exp\left\\{-\frac{\sigma^{2}}{2}\sum_{i=1}^{m}\left(q_{i}(x)-\alpha_{i}\right)^{2}\right\\}e^{-\|x\|^{2}/2}\
dx\ \leq\ \frac{\epsilon}{2}.$

If the system (1.1) has no solution then for some $\delta(\epsilon)>0$, we
have

$\sum_{i=1}^{m}\left(q_{i}(x)-\alpha_{i}\right)^{2}\ \geq\
\delta(\epsilon)\quad\text{provided}\quad\|x\|\leq\rho(\epsilon)$

and hence

$\begin{split}&\sigma^{m}\int_{x\in{\mathbb{R}}^{n}:\
\|x\|\leq\rho(\epsilon)}\exp\left\\{-\frac{\sigma^{2}}{2}\sum_{i=1}^{m}\left(q_{i}(x)-\alpha_{i}\right)^{2}\right\\}\
dx\\\ \leq\
&\sigma^{m}\rho^{n}(\epsilon)\nu_{n}\exp\left\\{-\frac{\sigma^{2}\delta(\epsilon)}{2}\right\\},\end{split}$

where $\nu_{n}$ is the volume of the unit ball in ${\mathbb{R}}^{n}$.
Therefore, there is $\sigma_{0}(\epsilon)>0$ such that for all
$\sigma>\sigma_{0}(\epsilon)$, we have

(3.4) $\sigma^{m}\int_{x\in{\mathbb{R}}^{n}:\
\|x\|\leq\rho(\epsilon)}\exp\left\\{-\frac{\sigma^{2}}{2}\sum_{i=1}^{m}\left(q_{i}(x)-\alpha_{i}\right)^{2}\right\\}\
dx\ \leq\ \frac{\epsilon}{2}.$

Combining (3.3) and (3.4), we conclude that the limit of the left hand side of
(3.2) is $0$ as $\sigma\longrightarrow+\infty$, which is the desired
contradiction. ∎

The proof of Theorem 2.2 is similar.

###### Proof of Theorem 2.2.

Seeking a contradiction, suppose that the only solution to the system is
$x=0$. Then for some $\delta>0$ we have

(3.5) $\sum_{i=1}^{m}q_{i}^{2}(x)\ \geq\ \delta\quad\text{for all}\quad
x\in{\mathbb{R}}^{n}\quad\text{such that}\quad\|x\|=1.$

From Lemma 3.1, for any $\sigma>0$, we have

(3.6)
$\begin{split}&\sigma^{m}\int_{{\mathbb{R}}^{n}}\exp\left\\{-\frac{\sigma^{2}}{2}\sum_{i=1}^{m}q_{i}^{2}(x)\right\\}e^{-\|x\|^{2}/2}\
dx\\\
=&(2\pi)^{\frac{n-m}{2}}\int_{{\mathbb{R}}^{m}}\det^{\quad-\frac{1}{2}}\left(I-\sqrt{-1}\sum_{i=1}^{m}\tau_{i}Q_{i}\right)e^{-\frac{\|t\|^{2}}{2\sigma^{2}}}\
dt.\end{split}$

From (3.5), the left hand side of (3.6) is bounded above (we use polar
coordinates) by

$\omega_{n}\sigma^{m}\int_{0}^{+\infty}\exp\left\\{-\frac{\delta\sigma^{2}\tau^{2}}{2}\right\\}\tau^{n-1}e^{-\tau^{2}/2}\
d\tau,$

where $\omega_{n}$ is the surface area of the unit sphere in
${\mathbb{R}}^{n}$. Using the substitution $\xi=\sigma\tau$, we rewrite the
integral as

$\omega_{n}\sigma^{m-n}\int_{0}^{+\infty}\exp\left\\{-\frac{\delta\xi^{2}}{2}\right\\}\xi^{n-1}e^{-\xi^{2}/2\sigma^{2}}\
d\xi$

and observe that it converges to $0$ as $\sigma\longrightarrow+\infty$ (recall
that $m<n$). On the other hand, the right hand side of (3.6) converges to

$(2\pi)^{\frac{n-m}{2}}\int_{{\mathbb{R}}^{m}}\det^{\quad-\frac{1}{2}}\left(I-\sqrt{-1}\sum_{i=1}^{m}\tau_{i}Q_{i}\right)\neq
0,$

which is the desired contradiction. ∎

In the rest of the paper, we deduce Theorem 1.1 from Theorem 2.1 and Theorem
1.2 from Theorem 2.2.

##  4\. Controlling eigenvalues

###  4.1. Preliminaries

In the space of $n\times n$ real matrices we consider the standard inner
product, see Section 1.3. The corresponding Euclidean norm is called the
Hilbert-Schmidt or Frobenius norm:

$\|A\|_{\mathrm{HS}}=\sqrt{\langle
A,A\rangle}=\sqrt{\operatorname{trace}(A^{\ast}A)}.$

If, in addition, $A$ is symmetric with eigenvalues
$\lambda_{1},\ldots,\lambda_{n}$, we have

$\|A\|_{\mathrm{HS}}=\sqrt{\sum_{j=1}^{n}\lambda_{j}^{2}}$

while for the operator norm we have

$\|A\|_{\mathrm{op}}=\max_{j=1,\ldots,n}|\lambda_{j}|.$

We will also consider the 4-Schatten norm defined by

$\|A\|_{\mathrm{S_{4}}}=\left(\sum_{j=1}^{n}\lambda_{j}^{4}\right)^{1/4}.$

This is indeed a norm in the space of $n\times n$ symmetric matrices, see, for
example, Chapter 1 of [14]. In particular, we will use that

(4.1) $|\ \|A\|_{\mathrm{S_{4}}}-\|B\|_{\mathrm{S_{4}}}\ |\ \leq\
\|A-B\|_{\mathrm{S_{4}}}.$

Also, we observe that for a symmetric matrix $A$ with eigenvalues
$\lambda_{1},\ldots,\lambda_{n}$, we have

$\sum_{j=1}^{n}\lambda_{j}^{4}\ \leq\
\left(\max_{j=1,\ldots,n}\lambda_{j}^{2}\right)\sum_{j=1}^{n}\lambda_{j}^{2},$

from which it follows that

(4.2) $\|A\|_{\mathrm{S_{4}}}\ \leq\
\|A\|_{\mathrm{op}}^{1/2}\|A\|_{\mathrm{HS}}^{1/2}.$

Suppose that $B$ is a positive semidefinite symmetric matrix with eigenvalues
$\lambda_{1}.\ldots,\lambda_{n}$. Then

$\|B\|^{2}_{\mathrm{HS}}=\sum_{j=1}^{n}\lambda_{j}^{2}\ \leq\
\left(\max_{j=1,\ldots,n}\lambda_{j}\right)\sum_{j=1}^{n}\lambda_{j}=\|B\|_{\mathrm{op}}\left(\operatorname{trace}B\right).$

We will apply the inequality in the following situation: Let
$A_{1},\ldots,A_{m}$ be an orthonormal set of symmetric matrices, so that

$\langle
A_{i},A_{j}\rangle=\operatorname{trace}(A_{i}A_{j})=\begin{cases}1&\text{if\
}i=j,\\\ 0&\text{if\ }i\neq j.\end{cases}$

Then the matrix

$B=\sum_{i=1}^{m}A_{i}^{2}$

is symmetric positive semidefinite and hence we have

(4.3) $\left\|\sum_{i=1}^{m}A_{i}^{2}\right\|_{\mathrm{HS}}^{2}\ \leq\
m\left\|\sum_{i=1}^{m}A_{i}^{2}\right\|_{\mathrm{op}}.$

We also remark that $\langle A,B\rangle\geq 0$ for any two $n\times n$
symmetric positive semidefinite matrices.

We will use the following inequality. Let $A_{1},\ldots,A_{m}$ be an
orthonormal set of $n\times n$ symmetric matrices and let $B$ be another
$n\times n$, not necessarily symmetric, real matrix. Then

$\langle A_{i},B\rangle=\operatorname{trace}(A_{i}B)\quad\text{for}\quad
i=1,\ldots,m$

are the coordinates of the orthogonal projection of $B$ onto
$\operatorname{span}\left(A_{1},\ldots,A_{m}\right)$ and hence

(4.4) $\sum_{i=1}^{m}\operatorname{trace}^{2}(A_{i}B)\ \leq\
\|B\|_{\mathrm{HS}}^{2}.$

Finally, we will need moments of a random vector $w\in{\mathbb{S}}^{m-1}$,
$w=\left(\omega_{1},\ldots,\omega_{m}\right)$. Namely, for integer
$\alpha_{1},\ldots,\alpha_{m}\geq 0$, we have

(4.5)
$\mathbb{E\thinspace}\omega_{1}^{\alpha_{1}}\cdots\omega_{m}^{\alpha_{m}}=0\quad\text{provided
at least one $\alpha_{i}$ is odd}$

and

$\mathbb{E\thinspace}\omega_{1}^{\alpha_{1}}\cdots\omega_{m}^{\alpha_{m}}=\frac{\Gamma\left(\frac{m}{2}\right)\prod_{i=1}^{m}\Gamma\left(\beta_{i}+\frac{1}{2}\right)}{\Gamma^{m}\left(\frac{1}{2}\right)\Gamma\left(\beta_{1}+\ldots+\beta_{m}+\frac{m}{2}\right)}\quad\text{provided}\quad\alpha_{i}=2\beta_{i}\quad\text{are
even,}$

see, for example, [3]. In particular, we will use the following values:

(4.6)
$\begin{split}\mathbb{E\thinspace}\omega_{i}^{2}\omega_{j}^{2}=&\frac{1}{m(m+2)}\quad\text{for}\quad
1\leq i\neq j\leq m,\\\
\mathbb{E\thinspace}\omega_{i}^{4}=&\frac{3}{m(m+2)}\quad\text{for}\quad
i=1,\ldots,m,\\\
\mathbb{E\thinspace}\omega_{i}^{2}\omega_{j}^{2}\omega_{k}^{2}=&\frac{1}{m(m+2)(m+4)}\quad\text{for
distinct}\quad 1\leq i,j,k\leq m,\\\
\mathbb{E\thinspace}\omega_{i}^{2}\omega_{j}^{4}=&\frac{3}{m(m+2)(m+4)}\quad\text{for}\quad
1\leq i\neq j\leq m\quad\text{and}\\\
\mathbb{E\thinspace}\omega_{i}^{6}=&\frac{15}{m(m+2)(m+4)}\quad\text{for}\quad
i=1,\ldots,m.\end{split}$

In what follows, we fix an orthonormal set $A_{1},\ldots,A_{m}$ of $n\times n$
symmetric matrices. For a random $w\in{\mathbb{S}}^{m-1}$,
$w=\left(\omega_{1},\ldots,\omega_{m}\right)$, sampled from the Haar
probability measure in ${\mathbb{S}}^{m-1}$, we define

$A(w)=\sum_{i=1}^{m}\omega_{i}A_{i}$

and let $\lambda_{1}(w),\ldots,\lambda_{n}(w)$ be the eigenvalues of $A(w)$.
Here is our first estimate.

######  Lemma 4.1.

We have

$\mathbb{E\thinspace}\left(\sum_{j=1}^{n}\lambda_{j}^{3}(w)\right)^{2}\ \leq\
\frac{120}{(m+2)(m+4)}\left\|\sum_{i=1}^{m}A_{i}^{2}\right\|_{\mathrm{op}}.$

###### Proof.

We have

$\begin{split}&\sum_{j=1}^{n}\lambda_{j}^{3}(w)=\operatorname{trace}\left(\sum_{i=1}^{m}\omega_{i}A_{i}\right)^{3}=\sum_{(i,j,k)\text{\
distinct}}\omega_{i}\omega_{j}\omega_{k}\operatorname{trace}(A_{i}A_{j}A_{k})\\\
&\qquad+\sum_{(i,j):\ i\neq
j}\omega_{i}^{2}\omega_{j}\operatorname{trace}(A_{i}^{2}A_{j})+\sum_{(i,j):\
i\neq j}\omega_{i}\omega_{j}^{2}\operatorname{trace}(A_{i}A_{j}^{2})\\\
&\qquad+\sum_{(i,j):\ i\neq
j}\omega_{i}^{2}\omega_{j}\operatorname{trace}(A_{i}A_{j}A_{i})+\sum_{i=1}^{m}\omega_{i}^{3}\operatorname{trace}A_{i}^{3}\\\
=&\sum_{(i,j,k)\text{\
distinct}}\omega_{i}\omega_{j}\omega_{k}\operatorname{trace}(A_{i}A_{j}A_{k})+3\sum_{(i,j):\
i\neq
j}\omega_{i}^{2}\omega_{j}\operatorname{trace}(A_{i}^{2}A_{j})+\sum_{i=1}^{m}\omega_{i}^{3}\operatorname{trace}A_{i}^{3}.\end{split}$

Using (4.5) and (4.6), we write

$\mathbb{E\thinspace}\left(\sum_{j=1}^{n}\lambda^{3}(w)\right)^{2}=\frac{T_{1}+27T_{2}+15T_{3}+18T_{4}+9T_{5}}{m(m+2)(m+4)},$

where

$\begin{split}T_{1}=&\sum_{\begin{subarray}{c}(i,j,k)\text{\ distinct}\\\
(i_{1},j_{1},k_{1})\text{\ is a permutation of\
}(i_{,}j,k)\end{subarray}}\operatorname{trace}(A_{i}A_{j}A_{k})\operatorname{trace}(A_{i_{1}}A_{j_{1}}A_{k_{1}})\\\
T_{2}=&\sum_{(i,j):\ i\neq j}\operatorname{trace}^{2}(A_{i}^{2}A_{j})\\\
T_{3}=&\sum_{i=1}^{m}\operatorname{trace}^{2}(A_{i}^{3})\\\
T_{4}=&\sum_{(i,j):\ i\neq
j}\operatorname{trace}(A_{i}^{2}A_{j})\operatorname{trace}(A_{j}^{3})\quad\text{and}\\\
T_{5}=&\sum_{(i,j,k)\text{\
distinct}}\operatorname{trace}(A_{i}^{2}A_{j})\operatorname{trace}(A_{k}^{2}A_{j}).\end{split}$

Next, we bound $T_{1}$, $T_{2}$, $T_{3}$, $T_{4}$ and $T_{5}$.

Applying (4.4) with $B=A_{j}A_{k}$, we obtain

$\sum_{i=1}^{m}\operatorname{trace}^{2}(A_{i}A_{j}A_{k})\ \leq\
\|A_{j}A_{k}\|_{\mathrm{HS}}^{2}=\operatorname{trace}(A_{k}A_{j}^{2}A_{k})=\operatorname{trace}(A_{j}^{2}A_{k}^{2})$

and hence

$\sum_{(i,j,k)\text{\ distinct}}\operatorname{trace}^{2}(A_{i}A_{j}A_{k})\
\leq\ \sum_{(j,k):\ j\neq k}\operatorname{trace}(A_{j}^{2}A_{k}^{2})\ \leq\
\left\|\sum_{i=1}^{m}A_{i}^{2}\right\|_{\mathrm{HS}}^{2}.$

By the Cauchy - Schwarz inequality, for every permutation $\sigma$ of
$\\{1,2,3\\}$, we obtain

$\begin{split}&\left|\sum_{(i_{1},i_{2},i_{3})\text{\
distinct}}\operatorname{trace}\left(A_{i_{1}}A_{i_{2}}A_{i_{3}}\right)\operatorname{trace}\left(A_{i_{\sigma(1)}}A_{i_{\sigma(2)}}A_{i_{\sigma(3)}}\right)\right|\
\leq\ \sum_{(i,j,k)\text{\
distinct}}\operatorname{trace}^{2}(A_{i}A_{j}A_{k})\\\
&\qquad\leq\left\|\sum_{i=1}^{m}A_{i}^{2}\right\|^{2}_{\mathrm{HS}}\end{split}$

and hence

$|T_{1}|\ \leq\ 6\left\|\sum_{i=1}^{m}A_{i}^{2}\right\|_{\mathrm{HS}}^{2}.$

Applying (4.4) with $B=A_{i}^{2}$, we conclude that

$\sum_{j=1}^{m}\operatorname{trace}^{2}(A_{i}^{2}A_{j})=\sum_{j=1}^{m}\operatorname{trace}^{2}(A_{j}A_{i}^{2})\
\leq\ \|A_{i}^{2}\|^{2}_{\mathrm{HS}}$

and hence

$|T_{2}|\ \leq\ \sum_{i=1}^{m}\left\|A_{i}^{2}\right\|^{2}_{\mathrm{HS}}\
\leq\ \left\|\sum_{i=1}^{m}A_{i}^{2}\right\|^{2}_{\mathrm{HS}},$

where the last inequality follows since the matrices
$A_{1}^{2},\ldots,A_{m}^{2}$ are symmetric positive semidefinite and hence

$\langle A_{i}^{2},A_{j}^{2}\rangle\geq 0\quad\text{for all}\quad i,j.$

Applying the Cauchy - Schwarz inequality, we obtain

(4.7) $|\operatorname{trace}A_{i}^{3}|=|\langle A_{i},A_{i}^{2}\rangle|\ \leq\
\|A_{i}\|_{\mathrm{HS}}\|A_{i}^{2}\|_{\mathrm{HS}}=\|A_{i}^{2}\|_{\mathrm{HS}}$

and hence

$|T_{3}|\ \leq\ \sum_{i=1}^{m}\|A_{i}\|^{2}_{\mathrm{HS}}\ \leq\
\left\|\sum_{i=1}^{m}A_{i}^{2}\right\|^{2}_{\mathrm{HS}}.$

To bound $T_{4}$ and $T_{5}$ we combine some of the previously obtained
estimates.

Applying the Cauchy - Schwarz inequality, (4.4) with
$B=\sum_{i=1}^{m}A_{i}^{2}$ and (4.7), we obtain

$\begin{split}&\left|\sum_{j=1}^{m}\sum_{i=1}^{m}\operatorname{trace}(A_{i}^{2}A_{j})\operatorname{trace}(A_{j}^{3})\right|=\left|\sum_{j=1}^{m}\operatorname{trace}\left(A_{j}\sum_{i=1}^{m}A_{i}^{2}\right)\operatorname{trace}(A_{j}^{3})\right|\\\
&\qquad\leq\left|\sum_{j=1}^{m}\operatorname{trace}^{2}\left(A_{j}\sum_{i=1}^{m}A_{i}^{2}\right)\right|^{1/2}\left|\sum_{j=1}^{m}\operatorname{trace}^{2}(A_{j}^{3})\right|^{1/2}\\\
&\qquad\leq\left\|\sum_{i=1}^{m}A_{i}^{2}\right\|_{\mathrm{HS}}\left(\sum_{j=1}^{m}\left\|A_{j}^{2}\right\|^{2}_{\mathrm{HS}}\right)^{1/2}\
\leq\ \left\|\sum_{i=1}^{m}A_{i}^{2}\right\|^{2}_{\mathrm{HS}}.\end{split}$

Therefore, using (4.7), we get

$|T_{4}|=\left|\sum_{j=1}^{m}\sum_{i=1}^{m}\operatorname{trace}(A_{i}^{2}A_{j})\operatorname{trace}(A_{j}^{3})-\sum_{i=1}^{m}\operatorname{trace}^{2}(A_{i}^{3})\right|\
\leq\ 2\left\|\sum_{i=1}^{m}A_{i}^{2}\right\|^{2}_{\mathrm{HS}}.$

It remains to bound $T_{5}$. We have

$\begin{split}T_{5}=&\sum_{j=1}^{m}\sum_{\begin{subarray}{c}(i,k):\\\ i\neq
j,k\neq
j\end{subarray}}\operatorname{trace}(A_{i}^{2}A_{j})\operatorname{trace}(A_{k}^{2}A_{j})-\sum_{j=1}^{m}\sum_{i:\
i\neq j}\operatorname{trace}^{2}(A_{i}^{2}A_{j})\\\
=&\sum_{j=1}^{m}\left(\sum_{i:\ i\neq
j}\operatorname{trace}(A_{i}^{2}A_{j})\right)^{2}-T_{2}.\end{split}$

Since

$0\ \leq\ T_{2}\ \leq\
\left\|\sum_{i=1}^{m}A_{i}^{2}\right\|^{2}_{\mathrm{HS}},$

we have

$|T_{5}|\ \leq\ \max\left\\{\sum_{j=1}^{m}\left(\sum_{i:i\neq
j}\operatorname{trace}(A_{i}^{2}A_{j})\right)^{2},\quad\left\|\sum_{i=1}^{m}A_{i}^{2}\right\|^{2}_{\mathrm{HS}}\right\\}.$

Now,

$\begin{split}&\left(\sum_{i:\ i\neq
j}\operatorname{trace}(A_{i}^{2}A_{j})\right)^{2}=\left(-\operatorname{trace}(A_{j}^{3})+\sum_{i=1}^{m}\operatorname{trace}(A_{i}^{2}A_{j})\right)^{2}\\\
&\qquad=\operatorname{trace}^{2}(A_{j}^{3})-2\operatorname{trace}(A_{j}^{3})\sum_{i=1}^{m}\operatorname{trace}(A_{i}^{2}A_{j})+\left(\sum_{i=1}^{m}\operatorname{trace}(A_{i}^{2}A_{j})\right)^{2}\\\
&\qquad=\operatorname{trace}^{2}(A_{j}^{3})-2\operatorname{trace}(A_{j}^{3})\operatorname{trace}\left(A_{j}\sum_{i=1}^{m}A_{i}^{2}\right)+\operatorname{trace}^{2}\left(A_{j}\sum_{i=1}^{m}A_{i}^{2}\right)\end{split}$

and hence

$\begin{split}&\sum_{j=1}^{m}\left(\sum_{i:i\neq
j}\operatorname{trace}(A_{i}^{2}A_{j})\right)^{2}\\\
&\qquad=\sum_{j=1}^{m}\operatorname{trace}^{2}(A_{j}^{3})-2\sum_{j=1}^{m}\operatorname{trace}(A_{j}^{3})\operatorname{trace}\left(A_{j}\sum_{i=1}^{m}A_{i}^{2}\right)+\sum_{j=1}^{m}\operatorname{trace}^{2}\left(A_{j}\sum_{i=1}^{m}A_{i}^{2}\right)\end{split}$

By (4.7), we get

$\sum_{j=1}^{m}\operatorname{trace}^{2}(A_{j}^{3})\ \leq\
\sum_{j=1}^{m}\|A_{j}^{2}\|^{2}_{\mathrm{HS}}\ \leq\
\left\|\sum_{i=1}^{m}A_{i}^{2}\right\|^{2}_{\mathrm{HS}}.$

Then, from the the Cauchy - Schwarz inequality, (4.7) and (4.4) with
$B=\sum_{i=1}^{m}A_{i}^{2}$, we get

$\begin{split}&\left|\sum_{j=1}^{m}\operatorname{trace}(A_{j}^{3})\operatorname{trace}\left(A_{j}\sum_{i=1}^{m}A_{i}^{2}\right)\right|\
\leq\
\left(\sum_{j=1}^{m}\operatorname{trace}^{2}(A_{j}^{3})\right)^{1/2}\left(\sum_{j=1}^{m}\operatorname{trace}^{2}\left(A_{j}\sum_{i=1}^{m}A_{i}^{2}\right)\right)^{1/2}\\\
&\quad\leq\left\|\sum_{i=1}^{m}A_{i}^{2}\right\|_{\mathrm{HS}}^{2}\end{split}$

and from (4.4)

$\sum_{j=1}^{m}\operatorname{trace}^{2}\left(A_{j}\sum_{i=1}^{m}A_{i}^{2}\right)\
\leq\ \left\|\sum_{i=1}^{m}A_{i}^{2}\right\|^{2}_{\mathrm{HS}}.$

Thus

$|T_{5}|\ \leq\ 4\left\|\sum_{i=1}^{m}A_{i}^{2}\right\|^{2}_{\mathrm{HS}}.$

Summarizing,

$\mathbb{E\thinspace}\left(\sum_{j=1}^{n}\lambda_{j}^{3}(w)\right)^{2}\ \leq\
\frac{120}{m(m+2)(m+4)}\left\|\sum_{i=1}^{m}A_{i}^{2}\right\|^{2}_{\mathrm{HS}}\
\leq\
\frac{120}{(m+2)(m+4)}\left\|\sum_{i=1}^{m}A_{i}^{2}\right\|_{\mathrm{op}},$

where the last inequality follows by (4.3). ∎

Next, we bound the 4th moment of the eigenvalues.

######  Lemma 4.2.

We have

$\mathbb{E\thinspace}\left(\sum_{j=1}^{n}\lambda_{j}^{4}(w)\right)\ \leq\
\frac{3}{m+2}\left\|\sum_{i=1}^{m}A_{i}^{2}\right\|_{\mathrm{op}}.$

###### Proof.

Using (4.5) and (4.6), we write

$\begin{split}&\mathbb{E\thinspace}\left(\sum_{j=1}^{n}\lambda_{j}^{4}(w)\right)=\mathbb{E\thinspace}\operatorname{trace}\left(\sum_{i=1}^{m}\omega_{i}A_{i}\right)^{4}\\\
&\quad=\mathbb{E\thinspace}\left(\sum_{(i,j):\ i\neq
j}\omega_{i}^{2}\omega_{j}^{2}\operatorname{trace}(A_{i}A_{j}A_{i}A_{j})\right)+\mathbb{E\thinspace}\left(\sum_{(i,j):\
i\neq
j}\omega_{i}^{2}\omega_{j}^{2}\operatorname{trace}(A_{i}^{2}A_{j}^{2})\right)\\\
&\qquad\qquad+\mathbb{E\thinspace}\left(\sum_{(i,j):\ i\neq
j}\omega_{i}^{2}\omega_{j}^{2}\operatorname{trace}(A_{i}A_{j}^{2}A_{i})\right)+\mathbb{E\thinspace}\left(\sum_{i=1}^{m}\omega_{i}^{4}\operatorname{trace}(A_{i}^{4})\right)\\\
&\quad=\frac{T_{1}+2T_{2}+3T_{3}}{m(m+2)},\end{split}$

where

$\begin{split}T_{1}=&\sum_{(i,j):\ i\neq
j}\operatorname{trace}(A_{i}A_{j}A_{i}A_{j}),\\\ T_{2}=&\sum_{(i,j):\ i\neq
j}\operatorname{trace}(A_{i}^{2}A_{j}^{2})\quad\text{and}\\\
T_{3}=&\sum_{i=1}^{m}\operatorname{trace}(A_{i}^{4}).\end{split}$

We bound $T_{1}$, $T_{2}$ and $T_{3}$.

Applying the Cauchy - Schwarz inequality, we get

$\begin{split}&|T_{1}|=\left|\sum_{(i,j):\ i\neq
j}\operatorname{trace}(A_{i}A_{j}A_{i}A_{j})\right|=\left|\sum_{(i,j):\ i\neq
j}\langle A_{j}A_{i},A_{i}A_{j}\rangle\right|\ \leq\ \sum_{(i,j):\ i\neq
j}\|A_{j}A_{i}\|_{\mathrm{HS}}\|A_{i}A_{j}\|_{\mathrm{HS}}\\\
&\qquad=\sum_{(i,j):\ i\neq
j}\operatorname{trace}(A_{i}^{2}A_{j}^{2})=T_{2}.\end{split}$

On the other hand,

$\begin{split}T_{2}=\sum_{(i,j):\ i\neq
j}\operatorname{trace}(A_{i}^{2}A_{j}^{2})=\operatorname{trace}\left(\sum_{i=1}^{m}A_{i}^{2}\right)^{2}-\sum_{i=1}^{m}\operatorname{trace}(A_{i}^{4})=\left\|\sum_{i=1}^{m}A_{i}^{2}\right\|^{2}_{\mathrm{HS}}-T_{3}.\end{split}$

Therefore,

$|T_{1}+2T_{2}+3T_{3}|\leq|T_{1}|+2T_{2}+3T_{3}\ \leq\
3T_{2}+3T_{3}=3\left\|\sum_{i=1}^{m}A_{i}^{2}\right\|^{2}_{\mathrm{HS}}$

The proof now follows by (4.3). ∎

Next, we prove some uniform bounds.

######  Lemma 4.3.

For all $w\in{\mathbb{S}}^{m-1}$, we have

  1. (1)

$\|A(w)\|_{\mathrm{op}}\ \leq\
\left\|\sum_{i=1}^{m}A_{i}^{2}\right\|^{1/2}_{\mathrm{op}}\quad\text{and}$

  2. (2)

$\sum_{j=1}^{n}\lambda_{j}^{4}(w)\ \leq\
\left\|\sum_{i=1}^{m}A_{i}^{2}\right\|_{\mathrm{op}}.$

###### Proof.

Repeatedly applying the Cauchy - Schwarz inequality, for any vector
$x\in{\mathbb{R}}^{n}$ such that $\|x\|=1$, we obtain

$\begin{split}|\langle A(w)x,x\rangle|=&\left|\sum_{i=1}^{m}\omega_{i}\langle
A_{i}x,x\rangle\right|\ \leq\ \left(\sum_{i=1}^{m}\langle
A_{i}x,x\rangle^{2}\right)^{1/2}\ \leq\ \left(\sum_{i=1}^{m}\langle
A_{i}x,A_{i}x\rangle\right)^{1/2}\\\
=&\left\langle\left(\sum_{i=1}^{m}A_{i}^{2}\right)x,x\right\rangle^{1/2}\
\leq\ \left\|\sum_{i=1}^{m}A_{i}^{2}\right\|^{1/2}_{\mathrm{op}},\end{split}$

and Part (1) follows. Note that here we did not use that $A_{1},\ldots,A_{m}$
is an orthonormal set.

To prove Part (2), we bound

$\sum_{j=1}^{n}\lambda_{j}^{4}(w)\ \leq\
\left(\max_{j=1,\ldots,n}\lambda_{j}^{2}(w)\right)\sum_{j=1}^{n}\lambda_{j}^{2}(w)=\left\|A(w)\right\|^{2}_{\mathrm{op}}\|A(w)\|^{2}_{\mathrm{HS}}.$

Using that $A_{1},\ldots,A_{m}$ is an orthonormal set, we obtain

(4.8)
$\|A(w)\|^{2}_{\mathrm{HS}}=\operatorname{trace}(A^{2}(w))=\sum_{i,j=1}^{m}\omega_{i}\omega_{j}\operatorname{trace}(A_{i}A_{j})=\sum_{i=1}^{m}\omega_{i}^{2}=1.$

The proof now follows by Part (1). ∎

Finally, we need a concentration inequality on the unit sphere
${\mathbb{S}}^{m-1}$ for the $4$-Schatten norm of $A(w)$.

######  Lemma 4.4.

For $\delta\geq 0$, we have

$\begin{split}&\mathbb{P\thinspace}\left\\{w\in{\mathbb{S}}^{m-1}:\
\left\|A(w)\right\|_{\mathrm{S_{4}}}\ \geq\
\left(\frac{3}{m+2}\left\|\sum_{i=1}^{m}A_{i}^{2}\right\|_{\mathrm{op}}\right)^{1/4}+\delta\right\\}\\\
&\quad\leq\
\exp\left\\{-\frac{\delta^{2}(m-1)}{2\left\|\sum_{i=1}^{m}A_{i}^{2}\right\|_{\mathrm{op}}^{1/2}}\right\\}.\end{split}$

###### Proof.

We apply a measure concentration inequality on the sphere
${\mathbb{S}}^{m-1}$. Let

$\operatorname{dist}(x,y)=\arccos\langle x,y\rangle$

be the geodesic distance between two points $x,y\in{\mathbb{S}}^{m-1}$ and let
$f:{\mathbb{S}}^{m-1}\longrightarrow{\mathbb{R}}$ be a 1-Lipschitz function,
so that

$|f(x)-f(y)|\ \leq\ \operatorname{dist}(x,y)\quad\text{for all}\quad
x,y\in{\mathbb{S}}^{m-1}.$

Then for $c=\mathbb{E\thinspace}f$ and $\delta>0$ we have

$\mathbb{P\thinspace}\left\\{w\in{\mathbb{S}}^{m-1}:\ f(w)\ \geq\
c+\delta\right\\}\ \leq\ \exp\left\\{-\frac{\delta^{2}(m-1)}{2}\right\\},$

see, for example, Section 5.1 of [10].

Let us define a function $g:{\mathbb{R}}^{m}\longrightarrow{\mathbb{R}}$ by

$g(x)=\|A(x)\|_{\mathrm{S_{4}}},\quad\text{where}\quad
A(x)=\sum_{i=1}^{m}\xi_{i}A_{i}\quad\text{for}\quad
x=\left(\xi_{1},\ldots,\xi_{m}\right).$

Then from (4.1) and Part 2 of Lemma 4.3, for all $x,y\in{\mathbb{S}}^{m-1}$,
we have

$\begin{split}|g(x)-g(y)|\ \leq\
&\|A(x)-A(y)\|_{\mathrm{S_{4}}}=\|A(x-y)\|_{\mathrm{S_{4}}}\ \leq\
\left\|\sum_{i=1}^{m}A_{i}^{2}\right\|^{1/4}_{\mathrm{op}}\|x-y\|\\\ \leq\
&\left\|\sum_{i=1}^{m}A_{i}^{2}\right\|^{1/4}_{\mathrm{op}}\operatorname{dist}(x,y).\end{split}$

Therefore, for the expectation $c=\mathbb{E\thinspace}g$ on the unit sphere
${\mathbb{S}}^{m-1}$, we have

$\mathbb{P\thinspace}\left\\{w\in{\mathbb{S}}^{m-1}:\ g(w)\ \geq
c+\delta\right\\}\ \leq\
\exp\left\\{-\frac{\delta^{2}(m-1)}{2\left\|\sum_{i=1}^{m}A_{i}^{2}\right\|^{1/2}_{\mathrm{op}}}\right\\}\quad\text{for}\quad\delta\geq
0.$

By Lemma 4.2 and the Hölder inequality, we get

$c=\mathbb{E\thinspace}\left(\sum_{j=1}^{n}\lambda_{j}^{4}(w)\right)^{1/4}\
\leq\ \left(\mathbb{E\thinspace}\sum_{j=1}^{n}\lambda_{j}^{4}(w)\right)^{1/4}\
\leq\
\left(\frac{3}{m+2}\left\|\sum_{i=1}^{m}A_{i}^{2}\right\|_{\mathrm{op}}\right)^{1/4},$

and the proof follows. ∎

##  5\. Estimating integrals

Recall that we have an orthonormal set $A_{1},\ldots,A_{m}$ of $n\times n$
symmetric real matrices. For $w\in{\mathbb{S}}^{m-1}$,
$w=\left(\omega_{1},\ldots,\omega_{m}\right)$, we define the matrix

$A(w)=\sum_{i=1}^{m}\omega_{i}A_{i}.$

As follows by (4.8), we have

$\|A(w)\|_{\mathrm{HS}}=1.$

In this section, we consider the integral

$\int_{0}^{+\infty}\tau^{m-1}\det^{\quad-\frac{1}{2}}\left(I-\sqrt{-1}\tau
A\right)\exp\left\\{-\frac{\sqrt{-1}\tau}{2}\operatorname{trace}A\right\\}\
d\tau,$

where $A$ is an $n\times n$ symmetric matrix satisifying
$\|A\|_{\mathrm{HS}}=1$ and possibly some other constraints. In particular, we
will be interested in the situation when

$\|A\|_{\mathrm{op}}=O\left(\frac{1}{\sqrt{m}}\right).$

We will be comparing this integral with

$\int_{0}^{+\infty}\tau^{m-1}\exp\left\\{-{\frac{\tau^{2}}{4}}\right\\}\
d\tau=2^{m-1}\Gamma\left(\frac{m}{2}\right)\
\sim\left(\frac{2}{e}\right)^{m/2}m^{m/2}.$

First, we bound the tail.

######  Lemma 5.1.

Let $A$ be an $n\times n$ real symmetric matrix such that

$\|A\|_{\mathrm{HS}}=1\quad\text{and}\quad\|A\|_{\mathrm{op}}\ \leq\
\frac{1}{10\sqrt{m}}.$

Then for $m\geq 2$,

$\int_{5\sqrt{m}}^{+\infty}\tau^{m-1}\left|\det^{\quad-\frac{1}{2}}\left(I-\sqrt{-1}\tau
A\right)\right|\ d\tau\ <\ \frac{1}{20m}m^{m/2}e^{-3m}.$

###### Proof.

Let $\lambda_{1},\ldots,\lambda_{n}$ be the eigenvalues of $A$, so that

$\sum_{j=1}^{n}\lambda_{j}^{2}=1\quad\text{and}\quad|\lambda_{j}|\ \leq\
\frac{\alpha}{\sqrt{m}}\quad\text{for}\quad j=1,\ldots,n$

(we will choose $\alpha=0.1$ at the end). Then

$\left|\det^{\quad-\frac{1}{2}}\left(I-\sqrt{-1}\tau
I\right)\right|=\prod_{j=1}^{n}\left|1-\sqrt{-1}\tau\lambda_{j}\right|^{-\frac{1}{2}}=\prod_{j=1}^{n}\left(1+\lambda_{j}^{2}\tau^{2}\right)^{-\frac{1}{4}}.$

Let

$\xi_{j}=\lambda_{j}^{2}\tau^{2}\quad\text{for}\quad j=1,\ldots,n.$

Since the minimum of the log-concave function $\prod_{j=1}^{n}(1+\xi_{j})$ on
the convex polyhedron defined by the equation

$\sum_{j=1}^{n}\xi_{j}=\tau^{2}$

and inequalities

$0\ \leq\ \xi_{j}\ \leq\ \frac{\alpha^{2}\tau^{2}}{m}\quad\text{and}\quad
j=1,\ldots,n$

is attained at its vertex where all but possibly one coordinate are either $0$
or $\alpha^{2}\tau^{2}/m$, we have

$\prod_{j=1}^{n}\left(1+\lambda_{j}^{2}\tau^{2}\right)^{-\frac{1}{4}}\ \leq\
\left(1+\frac{\alpha^{2}\tau^{2}}{m}\right)^{\frac{\alpha^{2}-m}{4\alpha^{2}}}.$

Hence

$\begin{split}&\int_{\frac{\sqrt{m}}{2\alpha}}^{+\infty}\tau^{m-1}\left|\det^{\quad-\frac{1}{2}}\left(I-\sqrt{-1}\tau
A\right)\right|\ d\tau\ \leq\
\int_{\frac{\sqrt{m}}{2\alpha}}^{+\infty}\tau^{m-1}\left(1+\frac{\alpha^{2}\tau^{2}}{m}\right)^{\frac{\alpha^{2}-m}{4\alpha^{2}}}\
d\tau\\\
&\quad=\frac{m^{m/2}}{\alpha^{m}}\int_{{1/2}}^{+\infty}s^{m-1}(1+s^{2})^{\frac{\alpha^{2}-m}{4\alpha^{2}}}\
ds\ \leq\
\frac{m^{m/2}}{\alpha^{m}}\int_{1/2}^{+\infty}(1+s^{2})^{\frac{m-1}{2}}(1+s^{2})^{\frac{\alpha^{2}-m}{4\alpha^{2}}}(2s)\
ds\\\
&\quad=\frac{m^{m/2}}{\alpha^{m}}\int_{1/2}^{+\infty}(1+s^{2})^{\frac{-m(1-2\alpha^{2})-\alpha^{2}}{4\alpha^{2}}}(2s)\
ds\\\
&\quad=\frac{m^{m/2}}{\alpha^{m}}\frac{4\alpha^{2}}{(1-2\alpha^{2})m-3\alpha^{2}}\left(\frac{4}{5}\right)^{\frac{(1-2\alpha^{2})m-3\alpha^{2}}{4\alpha^{2}}}\end{split}$

Substituting $\alpha=0.1$, we get

$\begin{split}&\int_{5\sqrt{m}}^{+\infty}\tau^{m-1}\left|\det^{\quad-\frac{1}{2}}\left(I-\sqrt{-1}\tau
A\right)\right|\ d\tau\ \leq\
m^{m/2}10^{m}\frac{0.04}{0.98m-0.03}\left(\frac{4}{5}\right)^{(24.5)m-0.75}\\\
&\quad<\ \frac{1}{20m}10^{m}m^{m/2}\left(\frac{4}{5}\right)^{(24.5)m}\ <\
\frac{1}{20m}m^{m/2}e^{-3m}.\end{split}$

∎

Next, we estimate the integral on the initial interval.

######  Lemma 5.2.

Let $A$ be an $n\times n$ real symmetric matrix such that

$\|A\|_{\mathrm{HS}}=1\quad\text{and}\quad\|A\|_{\mathrm{op}}\ \leq\
\frac{1}{10\sqrt{m}}$

and let $\lambda_{1},\ldots,\lambda_{n}$ be the eigenvalues of $A$. Then, for
$m\geq 1$,

  1. (1)

We have

$\begin{split}&\int_{0}^{5\sqrt{m}}\tau^{m-1}\left|\det^{\quad-\frac{1}{2}}\left(I-\sqrt{-1}\tau
A\right)\right|\ d\tau\\\ &\quad\leq\
\exp\left\\{\frac{625m^{2}}{8}\sum_{j=1}^{n}\lambda_{j}^{4}\right\\}\int_{0}^{5\sqrt{m}}\tau^{m-1}\exp\left\\{-{\frac{\tau^{2}}{4}}\right\\}\
d\tau.\end{split}$

  2. (2)

Suppose, in addition, that

$\left|\sum_{j=1}^{n}\lambda_{j}^{3}\right|\ \leq\
\frac{1}{25m^{3/2}}\quad\text{and}\quad\sum_{j=1}^{n}\lambda_{j}^{4}\ \leq\
\frac{1}{625m^{2}}.$

Then

$\begin{split}&\Re\int_{0}^{5\sqrt{m}}t^{m-1}\det^{\quad-\frac{1}{2}}(I-\sqrt{-1}\tau
A)\exp\left\\{-\frac{\sqrt{-1}\tau}{2}\operatorname{trace}A\right\\}\ d\tau\\\
&\quad\geq\
\frac{1}{2}\int_{0}^{5\sqrt{m}}\tau^{m-1}\exp\left\\{-{\frac{\tau^{2}}{4}}\right\\}\
d\tau.\end{split}$

###### Proof.

Since in the interval $0\leq\tau\leq 5\sqrt{m}$, we have

$|\tau\lambda_{j}|\ \leq\ \frac{1}{2}\quad\text{for}\quad j=1,\ldots,n,$

we can expand

(5.1) $\displaystyle\det^{\quad-\frac{1}{2}}\left(I-\sqrt{-1}\tau
A\right)\exp\left\\{-\frac{\sqrt{-1}\tau}{2}\operatorname{trace}A\right\\}$
$\displaystyle\quad=\exp\left\\{-\frac{1}{2}\sum_{j=1}^{n}\ln(1-\sqrt{-1}\tau\lambda_{j})-\frac{\sqrt{-1}\tau}{2}\sum_{j=1}^{n}\lambda_{j}\right\\}$
$\displaystyle\quad=\exp\left\\{\frac{1}{2}\sum_{k=2}^{\infty}\frac{(\tau\sqrt{-1})^{k}}{k}\sum_{j=1}^{n}\lambda_{j}^{k}\right\\}$
$\displaystyle\quad=\exp\left\\{h(\tau)+\sqrt{-1}g(\tau)\right\\},$

where

$h(\tau)=\sum_{s=1}^{\infty}(-1)^{s}\frac{\tau^{2s}}{4s}\sum_{j=1}^{n}\lambda_{j}^{2s}\quad\text{and}\quad
g(\tau)=\sum_{s=1}^{\infty}(-1)^{s}\frac{\tau^{2s+1}}{4s+2}\sum_{j=1}^{n}\lambda_{j}^{2s+1}.$

We have

$\sum_{j=1}^{n}\lambda_{j}^{2}=\|A\|^{2}_{\mathrm{HS}}=1$

and for $s\geq 1$, we have

$\sum_{j=1}^{n}\lambda_{j}^{2(s+1)}\ \leq\
\left(\max_{j=1,\ldots,n}\lambda_{j}^{2}\right)\sum_{j=1}^{n}\lambda_{j}^{2s}\
\leq\ \frac{1}{100m}\sum_{j=1}^{n}\lambda_{j}^{2s}.$

Consequently, for $0\leq\tau\leq 5\sqrt{m}$, we have

$\sum_{j=1}^{n}(\tau\lambda_{j})^{2(s+1)}\ \leq\
\frac{\tau^{2}}{100m}\sum_{j=1}^{n}(\tau\lambda_{j})^{2s}\ \leq\
\frac{1}{4}\sum_{j=1}^{n}(\tau\lambda_{j})^{2s}.$

Hence the terms of $h(\tau)$ alternate in sign and decrease in the absolute
value, from which we deduce that

(5.2) $-{\frac{\tau^{2}}{4}}\ \leq\ h(\tau)\ \leq\
-{\frac{\tau^{2}}{4}}+\frac{\tau^{4}}{8}\sum_{j=1}^{n}\lambda_{j}^{4}\quad\text{for}\quad
0\ \leq\ \tau\ \leq\ 5\sqrt{m}.$

Part (1) now follows from the upper bound in (5.2).

To prove Part (2), we bound $g(\tau)$ assuming that

$\left|\sum_{j=1}^{n}\lambda_{j}^{3}\right|\ \leq\
\frac{\alpha}{m^{3/2}}\quad\text{and}\quad\sum_{j=1}^{n}\lambda_{j}^{4}\ \leq\
\frac{\beta}{m^{2}}$

(we substitute $\alpha=1/25$ and $\beta=1/625$ at the end). For $s\geq 2$, we
have

$\sum_{j=1}^{n}|\lambda_{j}|^{2s+1}\ \leq\
\left(\max_{j=1,\ldots,n}|\lambda_{j}|\right)^{2s-3}\cdot\sum_{j=1}^{n}\lambda_{j}^{4}\
\leq\ \frac{\beta}{10^{2s-3}m^{s+\frac{1}{2}}}.$

Therefore, in the interval $0\leq\tau\leq 5\sqrt{m}$, we have

$\left|\sum_{j=1}^{n}(\tau\lambda_{j})^{3}\right|\ \leq\
125\alpha\quad\text{and}\quad\left|\sum_{j=1}^{n}(\tau\lambda_{j})^{2s+1}\right|\
\leq\ \frac{625\beta}{2^{2s-3}}\quad\text{for}\quad s\geq 2.$

Therefore, in the interval $0\leq\tau\leq 5\sqrt{m}$, we have

$|g(\tau)|\ \leq\
\frac{125\alpha}{6}+\sum_{s=2}^{\infty}\frac{625\beta}{(4s+2)2^{2s-3}}\ \leq\
\frac{125\alpha}{6}+\frac{1250\beta}{30}.$

Substituting

$\alpha=\frac{1}{25}\quad\text{and}\quad\beta=\frac{1}{625},$

we conclude that

$|g(\tau)|\ \leq\ \frac{5}{6}+\frac{1}{15}=\frac{27}{30}\ <\
\frac{\pi}{3}\quad\text{for all}\quad 0\leq\tau\leq 5\sqrt{m}.$

The proof now follows from the lower bound in (5.2). ∎

The last lemma of this section contains some estimates for our benchmark
integral.

######  Lemma 5.3.

For $m\geq 2$, we have

  1. (1)

$\int_{0}^{+\infty}\tau^{m-1}\exp\left\\{-{\frac{\tau^{2}}{4}}\right\\}\
d\tau\ \geq\
m^{m/2}\sqrt{\frac{\pi}{m}}\left(\frac{2}{e}\right)^{m/2}\quad\text{and}$

  2. (2)

$\begin{split}&\int_{5\sqrt{m}}^{+\infty}\tau^{m-1}\exp\left\\{-{\frac{\tau^{2}}{4}}\right\\}\
d\tau\\\ &\quad\leq\
\sqrt{\frac{2\pi}{m-1}}2^{m}m^{m/2}\exp\left\\{-\frac{25(m-1)}{8}\right\\}.\end{split}$

###### Proof.

We have

$\begin{split}\int_{0}^{+\infty}\tau^{m-1}\exp\left\\{-{\frac{\tau^{2}}{4}}\right\\}\
d\tau=2^{m-1}\int_{0}^{+\infty}s^{\frac{m-2}{2}}\exp\\{-s\\}\
ds=2^{m-1}\Gamma\left(\frac{m}{2}\right).\end{split}$

To prove Part (1), we use the standard inequality

$\Gamma(x)\ \geq\ \sqrt{2\pi}x^{x-\frac{1}{2}}e^{-x}\quad\text{for}\quad x\geq
1.$

To prove Part (2), we bound

$\begin{split}&\int_{5\sqrt{m}}^{+\infty}\tau^{m-1}\exp\left\\{-{\frac{\tau^{2}}{4}}\right\\}\
d\tau=2^{m}m^{m/2}\int_{5/2}^{+\infty}s^{m-1}\exp\left\\{-ms^{2}\right\\}\
ds\\\ &\quad\leq\
2^{m}m^{m/2}\int_{5/2}^{+\infty}\exp\left\\{-(m-1)\left(s^{2}-\ln
s\right)\right\\}\ ds\\\ &\quad\leq\
2^{m}m^{m/2}\int_{5/2}^{+\infty}\exp\left\\{-\frac{(m-1)s^{2}}{2}\right\\}\
ds=\frac{2^{m}m^{m/2}}{\sqrt{m-1}}\int_{\frac{5\sqrt{m-1}}{2}}^{+\infty}\exp\left\\{-\frac{\tau^{2}}{2}\right\\}\
d\tau\\\ &\quad\leq\
\sqrt{\frac{2\pi}{m-1}}2^{m}m^{m/2}\exp\left\\{-\frac{25(m-1)}{8}\right\\},\end{split}$

where in the last inequality we use the standard Gaussian probability tail
estimate

$\frac{1}{\sqrt{2\pi}}\int_{a}^{+\infty}e^{-\tau^{2}/2}\ d\tau\ \leq\
e^{-a^{2}/2}\quad\text{for}\quad a\geq 0.$

∎

##  6\. Proofs of Theorems 1.1 and 1.2

###### Proof of Theorem 1.1.

We choose

$\eta=10^{-6}.$

Let $A_{1},\ldots,A_{m}$ be an orthonormal basis of the subspace
$\operatorname{span}\left(Q_{1},\ldots,Q_{m}\right)$ in the space of $n\times
n$ symmetric matrices and let

$a_{i}(x)=\langle A_{i}x,x\rangle\quad\text{for}\quad i=1,\ldots,m$

be the corresponding quadratic forms. Since the quadratic forms
$q_{1},\ldots,q_{m}$ are linear combinations of the forms $a_{1},\ldots,a_{m}$
and vice versa, the system

$q_{i}(x)=\operatorname{trace}Q_{i}\quad\text{for}\quad i=1,\ldots,m$

has a solution if and only if the system

$a_{i}(x)=\operatorname{trace}A_{i}\quad\text{for}\quad i=1,\ldots,m$

has a solution $x$. To establish the existence of a solution of the latter
system, we use Theorem 2.1, for which we consider the integral

(6.1)
$\int_{{\mathbb{R}}^{m}}\det^{\quad-\frac{1}{2}}\left(I-\sqrt{-1}\sum_{i=1}^{m}\tau_{i}A_{i}\right)\exp\left\\{-\frac{\sqrt{-1}}{2}\sum_{i=1}^{m}\tau_{i}\operatorname{trace}A_{i}\right\\}\
dt.$

Our goal is to prove that the integral (6.1) converges absolutely to a non-
zero value.

Let ${\mathbb{S}}^{m-1}\subset{\mathbb{R}}^{m}$ be the unit sphere endowed
with the Haar probability measure. For $w\in{\mathbb{S}}^{m-1}$,
$w=\left(\omega_{1},\ldots,\omega_{m}\right)$, let

$A(w)=\sum_{i=1}^{m}\omega_{i}A_{i}.$

Then by (4.8) and Lemma 4.3 for every $w\in{\mathbb{S}}^{m-1}$, we have

$\|A(w)\|_{\mathrm{HS}}=1\quad\text{and}\quad\|A\|_{\mathrm{op}}=\sqrt{\frac{\eta}{m}}\
<\ \frac{1}{10\sqrt{m}}.$

It follows from Lemma (5.1) that

$\int_{0}^{+\infty}\tau^{m-1}\left|\det^{\quad-\frac{1}{2}}\left(I-\sqrt{-1}\tau
A(w)\right)\right|\ d\tau\ <\ +\infty.$

Hence the integral (6.1) indeed converges absolutely and, up to a non-zero
factor (the surface area of the sphere ${\mathbb{S}^{m-1}}$) can be written as
an absolutely converging integral

(6.2)
$\mathbb{E\thinspace}\left(\int_{0}^{+\infty}\det^{\quad-\frac{1}{2}}\left(I-\sqrt{-1}\sum_{i=1}^{m}\tau
A(w)\right)\exp\left\\{-\frac{\sqrt{-1}\tau}{2}\operatorname{trace}A(w)\right\\}\
d\tau\right)$

where the expectation is taken with respect to the Haar measure on
${\mathbb{S}}^{m-1}$. Hence our goal is to prove that the integral (6.2) is
non-zero. We intend to prove that the real part of the integral is positive.

Let $\lambda_{1}(w),\ldots,\lambda_{n}(w)$ be the eigenvalues of $A(w)$. By
Lemma 4.1,

$\mathbb{E\thinspace}\left(\sum_{j=1}^{n}\lambda_{j}^{3}(w)\right)^{2}\ \leq\
\frac{120\eta}{m(m+2)(m+4)}\ <\ \frac{3}{25000m^{3}}.$

Therefore, by the Markov inequality,

(6.3) $\mathbb{P\thinspace}\left\\{w:\
\left|\sum_{j=1}^{n}\lambda_{j}^{3}(w)\right|\ >\
\frac{1}{25m^{3/2}}\right\\}\ \leq\ \frac{3}{40}.$

By Lemma 4.2,

$\mathbb{E\thinspace}\left(\sum_{j=1}^{n}\lambda_{j}^{4}(w)\right)\ \leq\
{\frac{3\eta}{m(m+2)}}\ <\ \frac{3}{10^{6}m^{2}}.$

Hence, using the Markov inequality again, we get

(6.4) $\mathbb{P\thinspace}\left\\{w:\sum_{j=1}^{n}\lambda_{j}^{4}(w)\ >\
\frac{1}{625m^{2}}\right\\}\ \leq\ \frac{3}{1600}.$

We represent ${\mathbb{S}}^{m-1}$ as a disjoint union

${\mathbb{S}}^{m-1}=\Omega_{0}\cup\Omega_{1}\cup\Omega_{2},$

where

$\Omega_{0}=\left\\{w\in{\mathbb{S}}^{m-1}:\quad\left|\sum_{j=1}^{n}\lambda_{j}^{3}(w)\right|\
\leq\ \frac{1}{25m^{3/2}}\quad\text{and}\quad\sum_{j=1}^{n}\lambda_{j}^{4}(w)\
\leq\ \frac{1}{625m^{2}}\right\\},$
$\Omega_{1}=\left\\{w\in{\mathbb{S}}^{m-1}:\quad\left|\sum_{j=1}^{n}\lambda_{j}^{3}(w)\right|\
>\ \frac{1}{25m^{3/2}}\quad\text{and}\quad\sum_{j=1}^{n}\lambda_{j}^{4}(w)\
\leq\ \frac{1}{625m^{2}}\right\\}\quad\text{and}$
$\Omega_{2}=\left\\{w\in{\mathbb{S}}^{m-1}:\quad\sum_{j=1}^{n}\lambda_{j}^{4}(w)\
>\ \frac{1}{625m^{2}}\right\\}.$

From (6.3) and (6.4), we have

$\mathbb{P\thinspace}(\Omega_{0})\ \geq\ \frac{7}{8}$

and hence from Part (2) of Lemma 5.2,

(6.5)
$\begin{split}&\Re\int_{\Omega_{0}}\left(\int_{0}^{5\sqrt{m}}\det^{\quad-\frac{1}{2}}\left(I-\sqrt{-1}\sum_{i=1}^{m}\tau
A(w)\right)\exp\left\\{-\frac{\sqrt{-1}\tau}{2}\operatorname{trace}A(w)\right\\}\
d\tau\right)\ dw\\\ &\quad\geq\
\frac{7}{16}\int_{0}^{5\sqrt{m}}\tau^{m-1}\exp\left\\{-{\frac{\tau^{2}}{4}}\right\\}\
d\tau,\end{split}$

where $dw$ is the Haar measure in ${\mathbb{S}}^{m-1}$.

From (6.3), we have

$P(\Omega_{1})\ \leq\ \frac{3}{40}$

and hence Part (1) of Lemma 5.2 yields

(6.6)
$\begin{split}&\int_{\Omega_{1}}\left(\int_{0}^{5\sqrt{m}}\tau^{m-1}\left|\det^{\quad-\frac{1}{2}}\left(I-\sqrt{-1}\tau
A(w)\right)\right|\ d\tau\right)\ dw\\\
&\quad\leq\frac{3}{40}\exp\left\\{\frac{1}{8}\right\\}\int_{0}^{5\sqrt{m}}\tau^{m-1}\exp\left\\{-{\frac{\tau^{2}}{4}}\right\\}\
d\tau\\\
&\quad<0.1\int_{0}^{5\sqrt{m}}\tau^{m-1}\exp\left\\{-{\frac{\tau^{2}}{4}}\right\\}\
d\tau.\end{split}$

For integer $k\geq 1$, let

$\Omega_{2}^{k}=\left\\{w\in{\mathbb{S}}^{m-1}:\quad\frac{k}{5\sqrt{m}}\ <\
\|A(w)\|_{\mathrm{S_{4}}}\ \leq\ \frac{k+1}{5\sqrt{m}}\right\\}.$

Then from Part (2) of Lemma 4.3, we have

$\Omega_{2}=\bigcup_{k=1}^{5(\eta m)^{1/4}}\Omega_{2}^{k}.$

By Lemma 4.4, taking into account that $\eta=10^{-6}$, we get

$\begin{split}&\mathbb{P\thinspace}\left(\Omega_{2}^{k}\right)\ \leq\
\mathbb{P\thinspace}\left\\{w\in{\mathbb{S}}^{m-1}:\
\|A(w)\|_{\mathrm{S_{4}}}\ \geq\
\left(\frac{3\eta}{m(m+2)}\right)^{1/4}+\frac{k}{6\sqrt{m}}\right\\}\\\
&\quad\leq\ \exp\left\\{-\frac{k^{2}(m-1)}{72\sqrt{\eta
m}}\right\\}.\end{split}$

In view of Part (1) of Lemma 5.2,

$\begin{split}&\int_{\Omega_{2}^{k}}\left(\int_{0}^{5\sqrt{m}}\tau^{m-1}\left|\det^{\quad-\frac{1}{2}}\left(I-\sqrt{-1}\tau
A\right)\right|\ d\tau\right)\ dw\\\
&\quad\leq\exp\left\\{\frac{(k+1)^{4}}{8}-\frac{k^{2}(m-1)}{72\sqrt{\eta
m}}\right\\}\int_{0}^{5\sqrt{m}}\tau^{m-1}\exp\left\\{-{\frac{\tau^{2}}{4}}\right\\}\
d\tau.\end{split}$

Since

$k\ \leq\ 5(\eta m)^{1/4},$

we have

$\frac{(k+1)^{4}}{8}\ \leq\ 2k^{4}\ \leq 50k^{2}(\eta m)^{1/2}$

and

$\frac{(k+1)^{4}}{8}-\frac{k^{2}(m-1)}{72\sqrt{\eta m}}\ \leq\
\frac{k^{2}\sqrt{m}}{20}-6k^{2}\sqrt{m}\ <\ -5k^{2}.$

Hence

(6.7)
$\begin{split}&\int_{\Omega_{2}}\left(\int_{0}^{5\sqrt{m}}\tau^{m-1}\left|\det^{\quad-\frac{1}{2}}\left(I-\sqrt{-1}\tau
A\right)\right|\ d\tau\right)\ dw\\\ &\quad<\
\left(\sum_{k=1}^{\infty}\exp\left\\{-5k^{2}\right\\}\right)\int_{0}^{5\sqrt{m}}\tau^{m-1}\exp\left\\{-{\frac{\tau^{2}}{4}}\right\\}\
d\tau\\\ &\quad<\
0.01\int_{0}^{5\sqrt{m}}\tau^{m-1}\exp\left\\{-{\frac{\tau^{2}}{4}}\right\\}\
d\tau.\end{split}$

Summarizing, from (6.5), (6.6) and (6.7), we get

$\begin{split}&\left|\mathbb{E\thinspace}\int_{0}^{5\sqrt{m}}\det^{\quad-\frac{1}{2}}\left(I-\sqrt{-1}\sum_{i=1}^{m}\tau
A(w)\right)\exp\left\\{-\frac{\sqrt{-1}\tau}{2}\operatorname{trace}A(w)\right\\}\
d\tau\right|\\\ &\quad>\
\frac{1}{4}\int_{0}^{5\sqrt{m}}\tau^{m-1}\exp\left\\{-{\frac{\tau^{2}}{4}}\right\\}\
d\tau\end{split}$

and hence by Lemma 5.1, the absolute value of the expectation (6.2) is at
least

$\frac{1}{4}\int_{0}^{5\sqrt{m}}\tau^{m-1}\exp\left\\{-{\frac{\tau^{2}}{4}}\right\\}-\frac{1}{20m}m^{m/2}e^{-3m}.$

Then by Lemma 5.3, the absolute value of the expectation (6.2) is at least

$m^{m/2}\left(\sqrt{\frac{\pi}{16m}}\left(\frac{2}{e}\right)^{m/2}-\sqrt{\frac{\pi}{m-1}}2^{m}\exp\left\\{-\frac{25(m-1)}{8}\right\\}-\frac{1}{20m}e^{-3m}\right),$

which is positive for $m\geq 3$. ∎

###### Proof of Theorem 1.2.

The proof is identical, except we use Theorem 2.2 instead of Theorem 2.1. ∎

## References

  * [1] A. Barvinok, Feasibility testing for systems of real quadratic equations, Discrete $\&$ Computational Geometry 10 (1993), no. 1, 1–13.
  * [2] A. Barvinok, A Course in Convexity, Graduate Studies in Mathematics, 54, American Mathematical Society, Providence, RI, 2002.
  * [3] A. Barvinok, Estimating $L^{\infty}$ norms by $L^{2k}$ norms for functions on orbits, Foundations of Computational Mathematics 2 (2002), no. 4, 393–412.
  * [4] S. Basu, Computing the top Betti numbers of semialgebraic sets defined by quadratic inequalities in polynomial time, Foundations of Computational Mathematics 8 (2008), no. 1, 45–80.
  * [5] S. Basu, R. Pollack and M.-F. Roy, Algorithms in Real Algebraic Geometry, second edition, Algorithms and Computation in Mathematics, 10, Springer-Verlag, Berlin, 2006\.
  * [6] D. Bienstock, A note on polynomial solvability of the CDT problem, SIAM Journal on Optimization 26 (2016), no. 1, 488–498.
  * [7] P. Bürgisser, Average Euler characteristic of random real algebraic varieties, Comptes Rendus Mathématique. Académie des Sciences. Paris 345 (2007), no. 9, 507–512.
  * [8] D. Grigoriev and D.V. Pasechnik, Polynomial-time computing over quadratic maps. I. Sampling in real algebraic sets, Computational Complexity 14 (2005), no. 1, 20–52.
  * [9] D. Yu. Grigor’ev and N.N. Vorobjov, Jr., Solving systems of polynomial inequalities in subexponential time, Journal of Symbolic Computation, 5 (1988), no. 1-2, 37–64.
  * [10] M. Ledoux, The Concentration of Measure Phenomenon, Mathematical Surveys and Monographs, 89, American Mathematical Society, Providence, RI, 2001.
  * [11] A. Lerario and E. Lundberg, Gap probabilities and Betti numbers of a random intersection of quadrics, Discrete $\&$ Computational Geometry, 55(2016), no. 2, 462–496.
  * [12] L. Liberti, C. Lavor, N. Maculan and A. Mucherino, Euclidean distance geometry and applications, SIAM Review 56 (2014), no. 1, 3–69.
  * [13] P.A. Parrilo, Semidefinite optimization, in: Semidefinite Optimization and Convex Algebraic Geometry, MOS-SIAM Series on Optimization, 13, SIAM, Philadelphia, PA, 2013, pp. 3–46.
  * [14] T. Tao, Topics in Random Matrix Theory, Graduate Studies in Mathematics, 132, American Mathematical Society, Providence, RI, 2012.
  * [15] A. Wehrl, General properties of entropy, Reviews of Modern Physics 50 (1978), no. 2, 221–260.


# Language-Based Audio Retrieval with Converging Tied Layers and Contrastive
Loss

###### Abstract

In this paper, we tackle the new Language-Based Audio Retrieval task proposed
in DCASE 2022111https://dcase.community/challenge2022/task-language-based-
audio-retrieval. Firstly, we introduce a simple, scalable architecture which
ties both the audio and text encoder together. Secondly, we show that using
this architecture along with contrastive loss allows the model to
significantly beat the performance of the baseline model. Finally, in addition
to having an extremely low training memory requirement, we are able to use
pretrained models as it is without needing to finetune them. We test our
methods and show that using a combination of our methods beats the baseline
scores significantly.

##  1 Introduction

The Language-Based Audio Retrieval task is a new form of cross modal learning
[1] which aims to rank a list of audio clips according to their relevance
given a query caption. These query captions [2] are descriptive natural
language sentences annotated by humans, and they describe the acoustic events
happening in both foreground and background of the audio clip. Being able to
model and interpret the relationship between audio clips and a text sequence
is helpful towards many applications. Language-Based Audio Retrieval can be
applied to many practical applications in real life, such as acoustic
monitoring and human-computer interaction [1].

The Language-Based Audio Retrieval task is formulated in this way. The audio
clips and the query caption is passed to an audio encoder and text encoder
respectively. From the two encoders, output audio embeddings corresponding to
audio clips and a output text embedding corresponding to the query caption are
obtained. To determine the relevance between the audio clip and query caption,
a similarity measure is used to calculate similarity scores between the output
text embedding of the query caption and the output audio embedding of each
audio clip. Using these similarity scores, we can calculate the top 10 average
precision, and the top 1, top 5, and top 10 recall scores.

The baseline system proposed for Language-Based Audio Retrieval in DCASE2022
uses a dual encoder structure with two disjoint pathways to produce the output
audio and text embeddings. The CRNN model [3, 4] was used as the audio encoder
while the pretrained word2vec [5] model was used as the text encoder. The
model is trained using the Triplet ranking Loss [6] to maximize the distance
between the anchor sample and the negative sample, while minimizing the
distance between the anchor sample and the positive sample. During inference,
the output audio and text embeddings are extracted from the encoders. Then,
the dot product is used as the similarity measure to determine the relevance
of the audio clips to the query caption. We argue that training to maximize
the similarity between the output embeddings of two disjoint and separate
encoders for audio and text in Language-Based Audio Retrieval is non-trivial.
We find that we can increase efficiency and performance by tying the audio and
text encoder together and sharing their parameters. In addition to having a
tied model to produce output embeddings, we find that using contrastive loss
is instrumental in getting the model to converge and perform well. Finally, we
show compare the computational footprint of our methods and show the
efficiency of our method.

Our contributions are as follows:

  1. 1.

We introduce Converging Tied Layers and show that using Converging Tied Layers
for Language-Based Audio Retrieval is an efficient and straightforward method.

  2. 2.

We examine the importance of using contrastive loss and observe that
contrastive loss is crucial for using transformers effectively.

  3. 3.

We demonstrate that using Converging Tied Layers and contrastive loss
outperforms the baseline method by a significant factor,

##  2 Related Work

###  2.1 Datasets

The Clotho Dataset v2.1 consists of 6974 15 to 30 seconds long audio samples.
Each audio clip has 5 corresponding 8 to 20 words long human-annotated
captions that describe the acoustic events happening in the audio. During
training, the ground truth captions for that audio are used as the positive
samples and the ground truth captions for the other audios are used as the
negative samples. During evaluation, all of the audio clips are passed to the
model to rank each audio’s similarity to the query caption. Another dataset is
the Audio Grounding dataset has also been used by [4] for Audio and Caption
Retrieval. Though there are many other audio captioning datasets where
Language-Based Audio Retrieval can be applied to, to our knowledge active work
is ongoing only on the Clotho dataset and Audio Grounding dataset.

In this work, we focus only on the Clotho Dataset v2.1 as proposed in the
DCASE2022 challenge222https://dcase.community/challenge2022/task-language-
based-audio-retrieval, henceforth referred to as the Clotho Dataset.

###  2.2 Model Architectures

Prior work so far uses disjoint audio and text encoders to produce a vector
representation of the inputs. The baseline model [3] presented in DCASE 2022
uses 2 disjoint audio and text models to encode the audio clip and text from
the Clotho Dataset v2.1. The input audio is encoded by a Convolutional
Recurrent Neural Network (CRNN) [3] and is trained from scratch. For the input
text sequence, a pretrained word2vec [5]
model333https://code.google.com/archive/p/word2vec/ already trained on the
Google News dataset [7] is used to encode the text sequence to obtain a text
vector representation. The pretrained word2vec is not finetuned. [3] also uses
a similar approach for the Audio Grounding Dataset.

###  2.3 Contrastive Loss

During the advent of large scale pretrained language models[8, 9], many
authors focused on different predictive objectives such as masked language
modelling [8, 9] for pretraining. Over time, the focus shifted to a different
form of using contrastive loss to learn more informative multimodal embedding
spaces. There has been several variations of contrastive loss [10, 11, 12]. In
this work, we use the contrastive objective from CLIP [10, 11].

The CLIP contrastive objective extracts feature representations of the
different input modalities from the model and projects these representation to
a contrastive embedding space via a linear projection. The projected
representations are then normalized. The cosine similarities between every
possible pairwise representations of different modalities in the same batch
are calculated to obtain logits for both text and audio. Finally, the
contrastive loss is the average of the two cross entropy loss applied to the
text and audio logits with their labels being their respective index in the
batch.

Fig. 1: a) Baseline system. A CRNN is trained for the audio encoder while a
word2vec model pretrained on Google News is used without any finetuning. b)
Proposed system. Both audio embeddings and text embeddings are used with
frozen weights without any finetuning. We use CNN10, CNN14 for the audio
embeddings and BERT, RoBERTa for the text embeddings. Both embeddings are
passed to the tied model which is trained on both Triplet Ranking Loss and
Contrastive Loss. Shaded red boxes in the figure refers to models with frozen
parameters (not finetuned) while green boxes refers to layers/models with
trainable parameters. Fig. 2: Evaluation process: The logmel spectrogram of
each audio clip in the evaluation set is encoded to obtain its corresponding
vector representation. The query caption is likewise encoded to obtain the
sentence vector representation. The similarity metric is then applied between
each audio representation and the sentence representation to obtain a list of
similarity values. These values are then ranked to obtain the relevance of
each audio clip to the query caption.

##  3 Proposed Method

Our proposed model consists of two main parts. The first component refers to
the use of pretrained audio and text encoders as audio and text embeddings.
There is no finetuning of these embeddings and the weights of these encoders
are frozen. The second component is the Converging Tied layers. These layers
are shared between the audio and text input. Unlike prior work [4], where the
output embeddings are extracted via two disjoint and seperate models, we use
the same layers to produce both audio and text embeddings. We visualize this
in Figure 1 and 2.

###  3.1 Pretrained Embeddings

There is a plethora of pretrained models available publicly. These pretrained
models are often used for transfer learning to another related domain [13],
hence there is a need for finetuning. In our case, we find that it is
sufficient to simply use these pretrained models as it is without finetuning.
Therefore, there is a very low computational footprint from these embeddings.
However, we also performed some experiments where we finetuned on these
pretrained embeddings and we found that doing so yields a minimal performance
boost.

$\begin{array}[]{l}Emb_{A}=\text{pool}_{mean}(Encoder\textsubscript{A}(x_{A}))\\\
Emb_{T}=Encoder\textsubscript{T}(x_{T})\\\ \end{array}$ (1)

We use the CNN10 and CNN14 models already pretrained on audio tagging as the
audio encoder to produce audio embeddings, $Emb_{A}$. For the text embeddings,
we use BERT and RoBERTa as the text encoder to produce text embeddings,
$Emb_{T}$. Unless otherwise stated, these pretrained embeddings are frozen and
not finetuned, thereby minimizing the training time.

###  3.2 Converging Tied layers

The Converging Tied Layers take in both the audio embedding, $Emb_{A}$, and
text embedding, $Emb_{T}$, and project these embeddings to a common subspace.
We first pass both $Emb_{A}$ and $Emb_{T}$ through a linear layer for each
modality to project these embeddings to the same dimensionality. The projected
audio and text embeddings, $R_{A^{\prime}}$ and $R_{T^{\prime}}$, are then
passed through several shared layer to obtain the final vector representations
of the audio and text inputs, $R_{A}$ and $R_{T}$. While we defaulted to
transformer encoder layers due to its ability to encode contextual
information, we also experimented with simple feedforward layers.

$\begin{array}[]{l}R_{A^{\prime}}=\text{FFN}_{A}(Emb_{A})\\\
R_{T^{\prime}}=\text{FFN}_{T}(Emb_{T})\\\
R_{A}=\text{pool}_{mean}(\text{Transformer}_{tied}(R_{A^{\prime}}))\\\
R_{T}=\text{pool}_{mean}(\text{Transformer}_{tied}(R_{T^{\prime}}))\par\end{array}$
(2)

These tied layers share parameters across text and audio inputs and produces
both the audio and text vector representations. We hypothesize that using a
shared embedding subspace allows the model to perform better on the ranking
task, as opposed to having two disjoint encoders with two disjoint embedding
subspace.

####  3.2.1 Contrastive Loss

In addition to the Triplet Ranking Loss used, we also use a supplementary
Contrastive Loss jointly train the model. We find that using the Contrastive
loss is instrumental in helping the model converge. We use the same
contrastive loss as that in CLIP [10, 11, 12].

$\begin{array}[]{l}L=L_{Ranking}+L_{contrastive}\\\ \end{array}$ (3)

The model is trained to minimize both the triplet ranking loss, $L_{Ranking}$,
from positive and negative examples in the minibatch, and the contrastive
loss, $L_{contrastive}$, from the predicting the correct pair in the batch
[12].

##  4 Experimental Details

###  4.1 Data

We use Clotho dataset v2.1 for all our experiments as mentioned in Section
2.1. We extract log mel spectrogram with 64 Mel-bands, sampling rate 44100,
and hop length of 441. This is identical to the settings of the previous
baseline.

###  4.2 Training and Evaluation

Our training hyperparameters and settings are as follows. We use a batch size
of 32 with no gradient accumulation steps for 150 epochs with early stopping
based on the validation performance. We use a learning rate of $1\times
10^{-3}$ without any weight decay along with a learning rate scheduler which
reduces the learning rate with a factor of 0.1 when the performance plateaus
for 5 epochs. For the audio embeddings, we initialized the weights of the
pretrained CNN10 and CNN14 model444Publicly available at
https://github.comqiuqiangkongaudioset_tagging_cnn. For the text embeddings,
we used the pretrained BERT and RoBERTa model provided by Hugging
Face555huggingface.co/docs/transformers. Unless explicitly stated, these
pretrained embeddings are frozen in our experiments and the weights are not
updated.

For inference, the dot product between the vector representations of the audio
clips in the evaluation set and the vector representation of each query
caption in the evaluation set is used as the similarity measure to determine
the relevance of the audio clip to the query caption. The metrics used to
gauge performance are mean average precision at 10, and top 1, top 5 and top
10 recall.

##  5 Experimental Results and Analysis

We provide a summary of our best models and methods in Table 1. In the
following sections, we will analyse and provide some ablation studies of our
methods along with more comphrensive results. As mentioned in Section 4.2, the
pretrained weights of the audio and text embeddings are frozen unless
otherwise stated.

EncoderA | EncoderT | Tied Model | R1 | R5 | R10 | mAP10
---|---|---|---|---|---|---
CRNN | word2vec | - | 0.03 | 0.11 | 0.19 | 0.07
CNN10 | RoBERTabase | 4L 96dim Transformer | 0.10 | 0.29 | 0.41 | 0.18
CNN10 | RoBERTabase | 2L 192dim Transformer | 0.11 | 0.30 | 0.42 | 0.19
CNN10 | RoBERTabase | 4L 96dim Transformer | 0.11 | 0.32 | 0.45 | 0.2

Table 1: Comparison of our best 3 models against the baseline model (1st row).
Bold (4th row) indicates our best performing model. Italics (3rd and 4th row)
indicate that the model is fully trainable and no weights are frozen.

###  5.1 Importance of the Contrastive loss

EncoderA | EncoderT | Tied Model | R1 | R5 | R10 | mAP10
---|---|---|---|---|---|---
CRNN | word2vec | - | 0.03 | 0.11 | 0.19 | 0.07
CNN10 | RoBERTabase | 2L 192dim Linear | 0.00 | 0.00 | 0.01 | 0
CNN10 | RoBERTalarge | 2L 192dim Linear | 0.00 | 0.00 | 0.01 | 0
CNN10 | BERTbase | 2L 192dim Linear | 0.01 | 0.05 | 0.10 | 0.03
CNN10 | BERTlarge | 2L 192dim Linear | 0.00 | 0.00 | 0.01 | 0

Table 2: Models trained without contrastive loss. Without contrastive loss,
the model fails to perform well.

As mentioned in Section 3.2.1, we use a supplementary contrastive loss in
addition to the Triplet Ranking Loss. We find that without the contrastive
loss, the model is unable to converge and performs very badly. Our results are
shown in Table 2. For all other experiments, we defaulted to using contrastive
loss as supplementary objective.

###  5.2 Impact of using trainable or frozen pretrained embeddings

EncoderA | EncoderT | Tied Model | R1 | R5 | R10 | mAP10
---|---|---|---|---|---|---
CRNN | word2vec | - | 0.03 | 0.11 | 0.19 | 0.07
CNN10 | BERTlarge | 2L 192dim Transformer | 0.06 | 0.20 | 0.31 | 0.12
CNN10 | BERTbase | 2L 192dim Transformer | 0.07 | 0.23 | 0.34 | 0.14
CNN10 | RoBERTalarge | 2L 192dim Transformer | 0.08 | 0.24 | 0.37 | 0.15
CNN14 | RoBERTabase | 2L 192dim Transformer | 0.09 | 0.26 | 0.37 | 0.16
CNN10 | RoBERTabase | 2L 192dim Transformer | 0.10 | 0.28 | 0.40 | 0.18
CNN10 | RoBERTabase | 2L 192dim Transformer | 0.11 | 0.30 | 0.42 | 0.19

Table 3: Comparison of the choice of pretrained embeddings for the audio and
text embeddings. Italics (last row) indicate that the model is fully trainable
and no weights are frozen.

We compare the effectiveness of using pretrained embedding. Results are shown
in Table 3. We experimented with using CNN10/CNN14 [14] as the audio
embeddings and Bert/RoBERTa as the text embeddings. Using either trainable or
frozen pretrained embeddings with the Converging Tied Layers both surpass the
baseline performance significantly. We also note that trainable pretrained
embeddings do perform marginally better than their frozen counterparts at the
cost of more computational power and memory.

RoBERTa consistently performs significantly better than BERT, even though
their model sizes are similar. This is expected as RoBERTa [9] outperforms
BERT on many Natural Language Processing benchmarks such as GLUE [15], RACE
[16], SQuaD [17]. Therefore, RoBERTa is regarded as a better and more robust
model. This indicates that initialization of the embeddings is important and
any information stored in pretrained embeddings helps the model perform better
for audio retrieval. We also observe that smaller variants of the pretrained
audio and embeddings perform significantly better than their larger variants.
For instance, BERTbase and RoBERTabase perform better than BERTlarge and
RoBERTalarge with around 0.03 difference in mAP10.

###  5.3 Tied Transformers layers vs Tied Linear layers

EncoderA | EncoderT | Tied Model | R1 | R5 | R10 | mAP10
---|---|---|---|---|---|---
CRNN | word2vec | - | 0.03 | 0.11 | 0.19 | 0.07
CNN14 | RoBERTabase | 2L 192dim Linear | 0.03 | 0.15 | 0.24 | 0.08
CNN14 | RoBERTabase | 2L 300dim Linear | 0.03 | 0.14 | 0.24 | 0.08
CNN14 | RoBERTabase | 2L 192dim Linear | 0.03 | 0.14 | 0.23 | 0.08
CNN14 | RoBERTabase | 2L 192dim Transformer | 0.09 | 0.26 | 0.37 | 0.16

Table 4: Comparison of the choice of Converging Tied Layers. Converging Tied
Linear layers consistently gets outperformed by Converging Tied Transformers
layers.

We explore the choice of the type of layer to use for Converging Tied Layers.
Results are shown in Table 4. Transformers are known for being able to encode
contextual information [18] while linear layers provide a transformation
between features. In our experiments, Converging Tied Linear layers
consistently gets outperformed by Converging Tied Transformers layers. This
confirms our hypothesis that using the transformer encoder layers as the
choice for Converging Tied layers allows the model to better interpolate
contextual information from both the audio embedding and text embedding to a
common subspace.

##  6 Conclusion

This work introduces the use of Converging Tied layers and the importance of
contrastive loss for Language Basd Audio Retrieval. We show that Converging
Tied layers is a straightforward and efficient method that allows for minimal
training. We examined and analysed several design choices such as the choice
for converging tied layers and also the preference for smaller embeddings.
With our methods, we surpass the baseline model significantly on all metrics.

## References

  * [1] Huang Xie, Okko Räsänen, Konstantinos Drossos, and Tuomas Virtanen,  “Unsupervised audio-caption aligning learns correspondences between individual sound events and textual phrases,”  Accepted at ICASSP, 2022.
  * [2] Konstantinos Drossos, Samuel Lipping, and Tuomas Virtanen,  “Clotho: An Audio Captioning Dataset,”  arXiv:1910.09387 [cs, eess], Oct. 2019,  arXiv: 1910.09387.
  * [3] Xuenan Xu, Heinrich Dinkel, Mengyue Wu, and Kai Yu,  “A CRNN-GRU based reinforcement learning approach to audio captioning,”  in Proc. Detect. Classif. Acoust. Scenes Events Work. (DCASE), 2020, pp. 225–229.
  * [4] Xuenan Xu, Heinrich Dinkel, Mengyue Wu, and Kai Yu,  “Text-to-audio grounding: Building correspondence between captions and sound events,”  in ICASSP 2021 - 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2021, pp. 606–610.
  * [5] Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean,  “Efficient estimation of word representations in vector space,” 2013\.
  * [6] Jane Bromley, Isabelle Guyon, Yann LeCun, Eduard Säckinger, and Roopak Shah,  “Signature verification using a ”siamese” time delay neural network,”  in Proc. 6th Int. Conf. Neural Inf. Process. Syst. (NIPS), 1993, pp. 737–744.
  * [7] Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg Corrado, and Jeffrey Dean,  “Distributed representations of words and phrases and their compositionality,” 2013.
  * [8] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova,  “Bert: Pre-training of deep bidirectional transformers for language understanding,” 2019.
  * [9] Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov,  “Roberta: A robustly optimized bert pretraining approach,” 2019.
  * [10] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever,  “Learning transferable visual models from natural language supervision,” 2021.
  * [11] Andrey Guzhov, Federico Raue, Jörn Hees, and Andreas Dengel,  “Audioclip: Extending clip to image, text and audio,” 2021.
  * [12] Yuhao Zhang, Hang Jiang, Yasuhide Miura, Christopher D. Manning, and Curtis P. Langlotz,  “Contrastive learning of medical visual representations from paired images and text,” 2020.
  * [13] Andrew Koh, Fuzhao Xue, and Eng Siong Chng,  “Automated audio captioning using transfer learning and reconstruction latent space similarity regularization,” 2021.
  * [14] Qiuqiang Kong, Yin Cao, Turab Iqbal, Yuxuan Wang, Wenwu Wang, and Mark D. Plumbley,  “Panns: Large-scale pretrained audio neural networks for audio pattern recognition,” 2020.
  * [15] Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R. Bowman,  “Glue: A multi-task benchmark and analysis platform for natural language understanding,” 2018.
  * [16] Guokun Lai, Qizhe Xie, Hanxiao Liu, Yiming Yang, and Eduard Hovy,  “Race: Large-scale reading comprehension dataset from examinations,” 2017.
  * [17] Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang,  “Squad: 100,000+ questions for machine comprehension of text,” 2016\.
  * [18] Alexei Baevski, Henry Zhou, Abdelrahman Mohamed, and Michael Auli,  “wav2vec 2.0: A framework for self-supervised learning of speech representations,” 2020.