# Fully-dynamic-to-incremental reductions with known deletion order (e.g.
sliding window)

Binghui Peng111Supported by NSF CCF-1703925, IIS-1838154, CCF-2106429 and
CCF-2107187.
Columbia University
<EMAIL_ADDRESS>Aviad Rubinstein222Supported by NSF CCF-1954927, and a
David and Lucile Packard Fellowship.
Stanford University
<EMAIL_ADDRESS>
###### Abstract

Dynamic algorithms come in three main flavors: incremental (insertions-only),
decremental (deletions-only), or fully dynamic (both insertions and
deletions). Fully dynamic is the holy grail of dynamic algorithm design; it is
obviously more general than the other two, but is it strictly harder?

Several works managed to reduce fully dynamic to the incremental or
decremental models by taking advantage of either specific structure of the
incremental/decremental algorithms (e.g. [HK99, HdLT01, BKS12, ADK+16, BS80,
OL81, OvL81]), or specific order of insertions/deletions (e.g. [AW14, HKNS15,
KPP16]). Our goal in this work is to get a black-box fully-to-incremental
reduction that is as general as possible. We find that the following
conditions are necessary:

  * •

The incremental algorithm must have a worst-case (rather than amortized)
running time guarantee.

  * •

The reduction must work in what we call the deletions-look-ahead model, where
the order of deletions among current elements is known in advance. A notable
practical example is the “sliding window” (FIFO) order of updates.

Under those conditions, we design:

  * •

A simple, practical, amortized-fully-dynamic to worst-case-incremental
reduction with a $\log(T)$-factor overhead on the running time, where $T$ is
the total number of updates.

  * •

A theoretical worst-case-fully-dynamic to worst-case-incremental reduction
with a $\operatorname*{{polylog}}(T)$-factor overhead on the running time.

##  1 Introduction

A dynamic algorithm is a data structure that maintains certain properties
(e.g. shortest paths) of a ground set that is subject to a sequence of updates
(e.g. insertions/deletions of edges), and the goal is to minimize the (total)
update time. A fully dynamic algorithm supports both insertions and deletions
of the ground set elements, while an incremental algorithm restricts the
updates to be insertion-only and a decremental algorithm handles deletion
operations only.

A fully dynamic algorithm clearly benefits from handling more general updates,
but the at the same time, it is expected to be much harder than
incremental/decremental algorithms. Meanwhile, several existing works have
exploited special structure ([HK99, HdLT01, BKS12, ADK+16, BS80, OL81, OvL81])
or specific order of update sequence ([AW14, HKNS15, KPP16]) and reduce fully
dynamic to incremental or decremental algorithm. This motivates one to ask

Can a generic reduction transform an incremental algorithm into one that
handles both insertions and deletions?

Perhaps surprisingly, we find that once the order of deletions of current
elements is known to the algorithm (deletions-look-ahead), one can translate
an incremental algorithm with worst case guarantee to a fully dynamic
algorithm with worst case guarantee, with only polylogarithmic overhead.

######  Theorem 1.1 (Reduction, worst case to worst case).

Let $T\geq 1$ be the total number of updates. Suppose there exists a dynamic
algorithm in the incremental setting with query time $\Gamma_{q}$ and worst
case update time $\Gamma_{u}$, then there is a dynamic algorithm for
deletions-look-ahead setting with query time $\Gamma_{q}$ and worst case
update time333We believe that the update time can be improved at least to
$O(\Gamma_{u}\log(T)\log\log(T))$ at the expense of a more complicated
algorithm. $O(\Gamma_{u}\log^{2}(T))$.

Our reduction requires the incremental algorithm to have worst case (rather
than amortized) runtime guarantee, and most importantly, the relative order of
deletions of current elements must be known.444Equivalently, one can assume
there exists an oracle that outputs the deletion order of existing ground set
elements. The latter assumption is satisfied by well-studied models including
sliding window (FIFO) model [ELVZ17, EMMZ22, DGIM02, BDM+20, WZ22], where only
most recent insertion updates are of interests, as well as offline/look-ahead
model [KMW98, SM10, vdBNS19, CGH+20, AW14], where the entire sequence of
updates is known in advance. These models are of interests to both theoretical
and empirical community [HHS22]. Furthermore, the sliding window model is
often used as a benchmark for empirical investigation of fully dynamic
algorithms (e.g. [WLFT18, LMNF+20, HN21]). To complement our results, we also
prove that both conditions are indeed indispensable for a black box reduction
(see Section 5).

If one only aims for algorithms with amortized runtime guarantee, we have a
reduction with improved update time. We believe it could be of independent
interests due to its simplicity and could be beneficial for empirical
implementation.

######  Theorem 1.2 (Reduction, amortized to worst case).

Let $T\geq 1$ be the total number of updates. Suppose there exists a dynamic
algorithm for incremental setting with query time $\Gamma_{q}$ and worst case
update time $\Gamma_{u}$, then there is a dynamic algorithm for deletions-
look-ahead setting with query time $\Gamma_{q}$ and amortized update time
$O(\Gamma_{u}\cdot\log(T))$.

On the technical side, Theorem 1.2 exploits the ideas of rewinding the
incremental algorithm (e.g. [AW14, HKNS15, KPP16]), and in particular achieves
only logarithmic overhead by rewinding $2^{i}$ insertions every
$\Theta(2^{i})$ updates (e.g. [HK99, HdLT01, BKS12, ADK+16]). To achieve the
worst case guarantee, Theorem 1.1 additionally requires amortizing this
rewinding of $2^{i}$ insertions over $\Theta(2^{i})$ updates; this is a little
trickier because we have to start re-inserting elements in advance before all
the elements we would want to insert have arrived.

We demonstrate the power of our reduction in Section 4 by providing
applications on dynamic submodular maximization, dynamic Depth first search
(DFS) tree and dynamic All-Pair Shortest-Paths (APSP).

#### Related work

A systematic study of black box reduction for dynamic algorithms has been
initiated by the seminal work of [BS80], which shows how to make a static data
structure support insertions for “decomposable search problem”. The ideas of
rewinding incremental algorithm and the logarithmic scheduling have been
studied in different problem specific context [AW14, HKNS15, KPP16, HK99,
HdLT01, BKS12, ADK+16, BS80, OL81, OvL81, DS91, Cha12]. Our deletion-look-
ahead model has also been considered in the computational geometry literature,
and it is one variant of the semi-online model (see [DS91] for a detailed
discussion). The work of [Cha12] is closely related to us, it presents a
worst-case to amortized-case reduction, when the exact deletion time is known.
The result is (almost) equivalent to Theorem 1.2.555We thank Timothy Chan for
pointing out this connection after we published the first version. It differs
from Theorem 1.1 as our reduction is worst-case to worst-case.

#### Notation

Let $[n]=\\{1,2,\ldots,n\\}$ and
$[n_{1}:n_{2}]=\\{n_{1},n_{1}+1,\ldots,n_{2}\\}$. For any ground set elements
$e_{1}$ and $e_{2}$, we say $e_{1}$ is younger than $e_{2}$ if $e_{1}$ would
be deleted earlier than $e_{2}$. An element is of rank $r$ if it is the $r$-th
youngest of the current elements. For an ordered set $A$, we use
$A[n_{1}:n_{2}]$ to denote the youngest $n_{1}$-th to $n_{2}$-th elements of
$A$. For any $t\in[T]$, let $k(t)$ be the largest integer such that $t$ is
exactly a multiple of $2^{k(t)}$. In our pseudocode, Insert refers to the
insertion procedure of the incremental algorithm (hence taking $O(\Gamma_{u})$
time), while adding/removing elements to a set $A$ operates only over the the
set (hence taking $O(1)$ time).

##  2 Reduction – Amortized to worst case

We start by providing the amortized to worst case reduction and prove Theorem
1.2. It also serves as a warm up for the worst case to worst case reduction.
Our key idea is to re-order current elements in reverse order of deletions,
this ensures a deletion update takes only $O(\Gamma_{u})$ time by rewinding
the computation. Of course, maintaining the reverse order could be expensive
as the new-coming element could be deleted last (e.g. the sliding window
model). Instead, we only maintain a partial reverse order – we re-insert the
last $O(2^{i})$ elements in reverse order in every $2^{i}$ updates. This
suffices to handle fully-dynamic updates and brings $O(\log(T))$ computation
overhead on average.

The reduction is formally depicted in Algorithm 1. The current elements are
distributed to $m+1=\lceil\log_{2}T\rceil+1$ buckets $B_{0},\ldots,B_{m}$. At
the $t$-th update ($t\in[T]$), the algorithm first handles the update
(insertion or deletion) on $B_{0}$ and it is guaranteed by our algorithm that
a deletion occurs on $B_{0}$. The algorithm then rewinds the computation to
$B=B_{m}\ldots B_{k(t)+2}$ (Line 3) and then Insert elements of
$B_{0}\cup\cdots\cup B_{k(t)+1}$ in the reverse order (Line 8). Algorithm 1
re-arranges buckets as follows: It keeps buckets $B_{m},\ldots,B_{k(t)+2}$
unchanged, it puts the youngest $[2^{i}:2^{i+1}-1]$ elements in $B$ to bucket
$B_{i}$ ($i\in[0:k(t)]$) and the remaining elements to $B_{k(t)+1}$ (see Line
6 – 7).

Algorithm 1 Reduction – Amortized to worst case

1:Initialize $B_{i}\leftarrow\emptyset$ ($i\in[0:m]$) $\triangleright$
$m=\lceil\log_{2}T\rceil$

2:for $t=1,2,\ldots,T$ do

3: Rewind the computation to $B_{m}\ldots B_{k(t)+2}$

4: Add/remove the element in $B_{0}$ $\triangleright$ Deletion is guaranteed
to occur in $B_{0}$

5: $B\leftarrow B_{0}\cup\cdots\cup B_{k(t)+1}$

6: $B_{i}\leftarrow B[2^{i}:2^{i+1}-1]$ ($i\in[0:k(t)]$) $\triangleright$
$B_{i}$ contains the youngest $[2^{i}:2^{i+1}-1]$ elements

7: $B_{k(t)+1}\leftarrow B\setminus(B_{0}\cup\cdots\cup B_{k(t)})$

8: Insert $B_{k(t)+1},\ldots,B_{0}$ $\triangleright$ Elements are inserted in
reverse order of deletion

9:end for

For any $t\in[T]$, let $E_{t}$ be all existing elements at the end of $t$-th
update, and let $E_{t,r}$ be the youngest $r$ elements in $E_{t}$ (when there
are less than $r$ elements in $E_{t}$, we take $E_{t,r}=E_{t}$). The following
lemma formalizes the main invariant for Algorithm 1.

######  Lemma 2.1.

At the end of $t$-th update ($t\in[T]$), one has

  * •

$|B_{0}\cup\cdots\cup B_{k(t)+1}|\leq 2^{k(t)+2}+2^{k(t)}$;

  * •

$E_{t,2^{i+1}-1}\subseteq B_{0}\cup\cdots\cup B_{i}$ for any $i\in[0:k(t)]$.

###### Proof.

For the first claim, at the end of $(t-2^{k(t)})$-th update, Line 6 of
Algorithm 1 guarantees that $|B_{i}|\leq 2^{i}$ holds for any $i\in[0:k(t)+1]$
as $(t-2^{k(t)})$ is a multiple of $2^{k(t)+1}$. Since there are at most
$2^{k(t)}$ insertions between the $(t-2^{k(t)})$-th and $t$-th update, we have

$|B_{0}\cup\cdots\cup B_{k(t)+1}|\leq 2^{k(t)}+\sum_{i=0}^{k(t)+1}2^{i}\leq
2^{k(t)+2}+2^{k(t)}.$

We prove the second claim by induction. The case of $t=1$ holds trivially and
suppose the induction holds up to $t-1$. Then we know that

$E_{t-2^{k(t)},2^{k(t)+2}-1}\subseteq B_{0}\cup\cdots\cup B_{k(t)+1}$

at the end of $(t-2^{k(t)})$-th update as $(t-2^{k(t)})$ is a multiple of
$2^{k(t)+1}$. As a consequence, one has

$E_{t-2^{k(t)}}\setminus E_{t-2^{k(t)},2^{k(t)+2}-1}\cap
E_{t,2^{k(t)+1}-1}=\emptyset$

as there are at most $2^{k(t)}$ deletions between the $(t-2^{k(t)})$-th and
$t$-th update, and $2^{k(t)+2}-1-2^{k(t)}\geq 2^{k(t)+1}-1$. At the same time,
new elements arrive between the $(t-2^{k(t)})$-th and $t$-th update and they
are all contained in $B_{0}\cup\cdots\cup B_{k(t)+1}$, hence, we conclude that
$E_{t,2^{k(t)+1}-1}\subseteq B_{0}\cup\cdots\cup B_{k(t)+1}$. By Line 6 of
Algorithm 1, we have $E_{t,2^{i+1}-1}\subseteq B_{0}\cup\cdots\cup B_{i}$ for
any $i\in[0:k(t)]$. We conclude the proof here. ∎

The correctness of Algorithm 1 follows immediately from the correctness of the
incremental algorithm because the set $B_{0}$ always contains the youngest
element. It remains to bound the amortized running time.

######  Lemma 2.2.

The amortized update time of Algorithm 1 is at most
$O(\Gamma_{u}\cdot\log(T))$.

###### Proof.

Line 4 takes constant time since $B_{0}$ has constant size. By Lemma 2.1,
$|B_{0}\cup\cdots\cup B_{k(t)+1}|\leq 2^{k(t)+2}+2^{k(t)}$, the rewinding step
(Line 3) takes at most $O(2^{k(t)}\Gamma_{u})$ time and we make $O(2^{k(t)})$
calls to Insert at Line 8. The allocation step (Line 6) takes no more than
$O(2^{t(k)})$ time, since the bucket $B_{i}$ has already been sorted
($i\in[0:k(t)+1]$) and it remains to merge them. The total update time equals

$\sum_{t=1}^{T}O(2^{k(t)}\Gamma_{u})=\sum_{k=0}^{m}O(2^{k}\Gamma_{u})\cdot
T/2^{k}=O(\Gamma_{u}\cdot T\log(T)).$

We conclude the proof here. ∎

######  Remark 2.3 (Implementation of rewinding).

We work in the RAM model and perform reversible computation. One simple way of
implementing reversible computation (e.g. [Ben73]) is to write down the change
to memory cell in every step. The forward computation time only slows down by
a constant factor and the backward (rewind) computation time equals the
forward computation time. In practice for specific problems there may be
faster ways to implement rewinding.

##  3 Reduction – Worst case to worst case

We next dedicate to prove Theorem 1.1, which translates the worst case
guarantee from the incremental model to the deletions-look-ahead model. The
major difference with the amortized reduction is that one cannot re-order/re-
insert a large block of elements at once. A natural idea is to prepare the re-
order/re-insertion in advance and split the cost. This brings new challenges
as (unknown) future insertions/deletions interleave with the preparation step
and one does not know the exact set of elements beforehand. To resolve it, we
maintain multiple threads, and each thread further divides the preparation
step into epochs of geometrically decreasing size.

The high-level idea is presented in Algorithm 2 with implementation details
deferred to the proof of Lemma 3.2. Algorithm 2 maintains $m+1$ threads and
$m+1$ buckets $B_{0},\ldots,B_{m}$. During the execution of the algorithm, all
existing elements are distributed over $B_{0},\ldots,B_{m}$, and ideally, the
$i$-th bucket $B_{i}$ should be of size $O(2^{i})$ and $B_{0}\cup\cdots\cup
B_{i}$ should contain the youngest $\Omega(2^{i})$ elements. This guarantees
the insertion/deletion of an element can be resolved in $O(\Gamma_{u})$ time
since one only needs to re-insert elements in $B_{0}$.

The crucial part is to maintain the ordered buckets $B_{0},\ldots,B_{m}$, for
which Algorithm 2 maintains $m$ threads; the $i$-th thread ($i\in[m]$)
prepares the re-order/re-insertion ahead of $2^{i}$ updates. Precisely, the
$i$-th thread re-starts every $2^{i+1}$ updates and operates over the upcoming
$2^{i}$ updates (Line 12 – 28). It first rewinds the computation status to
$B_{m}\ldots B_{i}$ (Line 14), which is prepared by the $(i+k(\tau))$-th
thread and then re-inserts elements of $B_{0}\cup\cdots\cup B_{i-1}$ (Line 16
– 24). Concretely, the re-insertion procedure is further divided into $i$
epochs, where epoch $j$ ($j\in[i-1]$) lasts for $2^{j}$ updates and epoch $0$
lasts for $2$ updates. Let $t(i,\tau,j):=2^{i}\tau+\sum_{r=j+1}^{i-1}2^{r}$
denote the end of epoch $j+1$ in the $(\tau/2+1)$-th outer-for-loop-iteration
of the $i$-th thread. During epoch $j$, the $i$-th thread leaves alone the
youngest $2^{j+2}$ elements at the beginning of epoch $j$ to $B^{(i)}$ and
Insert the remaining elements $B_{j}^{(i)}$ over the upcoming $2^{j}$ updates
(i.e. $[t(i,\tau,j)+1:t(i,\tau,j)+2^{j}]$-th update, see Line 18). Meanwhile,
the set $B^{(i)}$ is updated and elements are added and removed (Line 20).
Finally, at the end of $t$-th update ($t\in[T]$ and $k(t)\geq 1$), Algorithm 2
resets $B_{j}$ to $B_{j}^{(k(t))}$ for every $j\in[0:k(t)-1]$ (Line 26) and
this step takes $O(\log T)$ time as we only change the pointer of $B_{j}$.

Algorithm 2 Reduction – Worst case to worst case
$\triangleright$ Variables with superscript (i) internal to Thread($i$)
$\triangleright$ Thread($i$) only uses information from bigger threads (aka
Thread($j$) for $j>i$)
$\triangleright$ In particular, Thread($i$)’s Insert and rewind do not affect
the state seen by bigger threads
$\triangleright$ The output of the algorithm is maintained by Thread($0$)

1:Initialize $B_{i}\leftarrow\emptyset$ and run $\textsc{Thread}(i)$
($i\in[0:m]$) $\triangleright$ $m=\lceil\log_{2}T\rceil$

2:

3:procedure Thread($0$)

4: for $t=1,2,\ldots,T$ do

5: Add/remove the element in $B_{0}$ $\triangleright$ $t$-th update (deletions
guaranteed to be from $B_{0}$)

6: Rewind the computation to $B_{m}\ldots B_{1}$ $\triangleright$ State
prepared by Thread($k(t-1)$)

7: Insert $B_{0}$

8: end for

9:end procedure

10:

11:procedure Thread($i$) $\triangleright$ $i\in[1:m]$

12: for $\tau=0,2,4,\ldots,\lfloor T/2^{i}\rfloor$ do $\triangleright$ Restart
every $2^{i+1}$ updates

13: $B^{(i)}\leftarrow B_{0}\cup\cdots\cup B_{i-1}$

14: Rewind the computation to $B_{m}\ldots B_{i}$ $\triangleright$ State
prepared by Thread($i+k(\tau)$)

15:

16: for $j=i-1,i-2,\ldots,1$ do $\triangleright$ $j$-th epoch, amortized over
$2^{j}$ updates

17: $B_{j}^{(i)}\leftarrow B^{(i)}[2^{j+2}+1:]$ $\triangleright$ Oldest
$\Theta(2^{j})$ elements in $B^{(i)}$

18: Insert $B_{j}^{(i)}$

19: $B^{(i)}\leftarrow B^{(i)}\backslash B_{j}^{(i)}$

20: Add/remove elements in $B^{(i)}$ $\triangleright$ Updates
$[t(i,\tau,j)+1:t(i,\tau,j)+2^{j}]$

21: end for

22: Add/remove elements of $B^{(i)}$ in the remaining 2 updates
$\triangleright$ Epoch $0$

23: $B_{0}^{(i)}\leftarrow B^{(i)}$

24: Insert $B_{0}^{(i)}$

25:

26: $B_{j}\leftarrow B_{j}^{(i)}$ ($\forall j\in[0:i-1]$)

27: Do nothing for $2^{i}$ updates

28: end for

29:end procedure

Recall $E_{t,r}$ denotes the youngest $r$ elements and $E_{t}$ denotes all
elements at the end of $t$-th update. We use $B_{t,j}$ and $B_{t,j}^{(i)}$ to
denote the status of $B_{j}$ and $B_{j}^{(i)}$ at the end of $t$-th update. We
first formalize the main invariant for Algorithm 2.

######  Lemma 3.1.

For any thread $i\in[m]$, outer-for-loop-iteration
$\tau\in\\{0,2,\ldots,T/2^{i}\\}$, at the end of the $(2^{i}\tau)$-th update,
we have

  * •

$E_{2^{i}\tau,2^{j+2}}\subseteq B_{2^{i}\tau,0}\cup\cdots\cup
B_{2^{i}\tau,j}$,

  * •

$|B_{2^{i}\tau,j}|\leq 3\cdot 2^{j+1}$

holds for any $j\in[i-1]$. For $j=0$, we have $|B_{2^{i}\tau,0}|\leq 12$ and
$E_{2^{i}\tau,4}\subseteq B_{2^{i}\tau,0}$.

###### Proof.

We prove the first bullet by an induction on $i$ (in the reverse order). The
base case of $i=m$ holds trivially as all buckets are empty at the beginning.

Suppose the induction holds up to the $(i+1)$-th thread. For any outer-for-
loop-iteration $\tau\in\\{2,\ldots,T/2^{i}\\}$, at the end of $2^{i}\tau$-th
update, the buckets $B_{0},\ldots,B_{i-1}$ are reset by the $(i+k(\tau))$-th
thread, hence, it suffices to prove $E_{2^{i}\tau,2^{j+2}}\subseteq
B_{2^{i}\tau,0}^{(i+k(\tau))}\cup\cdots\cup B_{2^{i}\tau,j}^{(i+k(\tau))}$
($\forall j\in[i-1]$). By the inductive hypothesis of the $(i+k(\tau))$-th
thread, we know that

$E_{2^{i}\tau-2^{i+k(\tau)},2^{i+k(\tau)+1}}\subseteq
B_{2^{i}\tau-2^{i+k(\tau)}}^{(i+k(\tau))}=B_{2^{i}\tau-2^{i+k(\tau)},0}\cup\cdots\cup
B_{2^{i}\tau-2^{i+k(\tau)},i+k(\tau)-1},$

that is, the youngest $2^{i+k(\tau)+1}$ are contained in $B^{(i+k(\tau))}$
initially. We prove the desired claim by contradiction and assume for some
$j\in[0:i-1]$, there exists an element $e$ such that $e\in
E_{2^{i}\tau,2^{j+2}}$ but $e\notin
B_{2^{i}\tau,0}^{(i+k(\tau))}\cup\cdots\cup B_{2^{i}\tau,j}^{(i+k(\tau))}$.
This can only happen if (1) the element $e$ is inserted before epoch $j+1$;
and (2) it is removed from $B^{(i+k(\tau))}$ at some epoch $\gamma\geq j+1$.
The reason for (1) is that elements inserted on/after epoch $j+1$ would
ultimately be included in $B_{2^{i}\tau,0}^{(i+k(\tau))}\cup\cdots\cup
B_{2^{i}\tau,j}^{(i+k(\tau))}$; the reason for (2) is similar.

Since the element $e$ is removed from $B^{(i+k(\tau))}$ at epoch $\gamma$, we
have that

$e\notin E_{t(i+k(\tau),\tau/2^{k(\tau)}-1,\gamma)}\setminus
E_{t(i+k(\tau),\tau/2^{k(\tau)}-1,\gamma),2^{\gamma+2}}.$

There are at most $2+\sum_{r=1}^{\gamma}2^{r}=2^{\gamma+1}$ deletions since
epoch $\gamma$, the rank of $e$ can be improved to at most
$2^{\gamma+2}-2^{\gamma+1}=2^{\gamma+1}$, hence we have $e\notin
E_{2^{i}\tau}\setminus E_{2^{i}\tau,2^{\gamma+1}}$ and therefore $e\notin
E_{2^{i}\tau}\setminus E_{2^{i}\tau,2^{j+2}}$ ($\gamma\geq j+1$), this
contradicts with the assumption.

For the second bullet, for any $i\in[m]$ and $\tau\in\\{2,\ldots,T/2^{i}\\}$,
consider the $(i+k(\tau))$-th thread. After executing Line 19 in the
$(j+1)$-th epoch of Algorithm 2, we have that

$|B^{(i+k(\tau))}_{t(i+k(\tau),\tau/2^{k(\tau)}-2^{j+1},j)}|\leq 2^{j+3}$

For the rest of the epoch, there can be at most $2^{j+1}$ insertions, hence:

$|B^{(i+k(\tau))}_{t(i+k(\tau),\tau/2^{k(\tau)},j)}|\leq 2^{j+3}+2^{j+1}$

Finally, after executing Line 17 in the $j$-th epoch, we have:

$|B^{(i+k(\tau))}_{t(i+k(\tau),\tau/2^{k(\tau)},j),j}|\leq
2^{j+3}+2^{j+1}-2^{j+2}=3\cdot 2^{j+1}.$

We have proved the first claim for $j\in[i-1]$, the case of $j=0$ follows
similarly.∎

We next bound the worst case update time.

######  Lemma 3.2.

The update time per operation is at most $O(\Gamma_{u}\cdot\log^{2}(T))$.

###### Proof.

By Lemma 3.1, the size of $B_{0}$ is $O(1)$ and it contains the youngest $2$
elements, hence the rewinding and Insert step (Line 7) can be performed in
$O(\Gamma_{u})$ time per update. The major overhead comes from maintaining $m$
threads, and we bound the runtime of each thread separately.

For any thread $i$ and outer-for-loop-iteration
$\tau\in\\{0,2,\ldots,T/2^{i}\\}$, due to Line 17 of Algorithm 2, we have

$|B_{t(i,\tau,j-1),j}^{(i)}|\leq|B_{t(i,\tau,j)}^{(i)}|\leq
2^{j+3}+2^{j+1}\quad\forall j\in[i-2]$

and by Lemma 3.1,

$|B_{t(i,\tau,i-2),i-1}^{(i)}|\leq|B_{2^{\tau}i,0}\cup\cdots\cup
B_{2^{\tau}i,i-1}|\leq\sum_{r=0}^{i-1}3\cdot 2^{r+1}\leq 3\cdot 2^{i+1}.$

We analyse the update time step by step.

We first come to the rewinding step (Line 14). Unlike the amortized case, we
cannot simply rewind by the reversible computation since we maintain multiple
threads that need to access the state of the incremental algorithm with
different sets of elements, in parallel. Instead, when we call Insert of each
block $B_{j}^{(i)}$, we maintain a dictionary that records the location/value
of changed memory cell. The construction of dictionary only incurs constant
overhead. By doing this, during the execution of Algorithm 2, one can access
any memory cell by looking up to at most $O(\log(T))$ dictionaries (note the
lookup path is known to Algorithm 2) and find the last time it has been
changed. Naively, looking up the memory updates in each dictionary takes
$O(\log(\Gamma_{u}T))$ time. This brings an $O((\log(T)\log(\Gamma_{u}T)))$
total overhead for every operation of Insert. Except for this, Line 14
essentially comes for free.

A more careful implementation leads to only $O(\log(T))$ overhead. We maintain
an additional data structure, which links each memory cell of the incremental
algorithm to $m+1$ lists, where the $i$-th list records the changes made by
the $i$-th thread in chronological order. The maintenance of the data
structure slows down the forward computation of Insert by a constant factor.
At the same time, in order to search the content of a memory cell, we only
need to search through the lists (note again the look-up path is known), which
takes $O(1)$ time per list and $O(\log(T))$ in total. Hence, it brings an
$O((\log(T))$ total overhead for every operation of Insert.

Algorithm 2 updates $B^{(i)}$ and $B_{j}^{(i)}$ at the beginning of epoch $j$
(Lines 17 and 19). We do not rewrite, but instead, we copy $B^{(i)}$ and
$B_{j}^{(i)}$ to new memory cells. Since both sets are of size $O(2^{j})$, the
copy operation can be done in the first $\frac{1}{4}\cdot 2^{j}$ updates
during epoch $j$ and has $O(\log(T))$ cost per update using Binomial heap.

Algorithm 2 calls at most $O(2^{j})$ times Insert during epoch $j$ (Line 18).
Since elements in $B_{j}^{(i)}$ are known at the beginning so these operations
can be averaged over the following $3/4\cdot 2^{j}$ updates of epoch $j$ and
take $O(\Gamma_{u}\log(T))$ time per update.

The set $B^{(i)}$ receives new elements as well as removes old elements in
epoch $j$ (Line 20). We buffer the changes in the first $\frac{1}{4}\cdot
2^{j}$ updates (as the “new” set $B^{(i)}$ is not yet ready) and add/remove
elements during the following $3/4\cdot 2^{j}$ updates. The size of $B^{(i)}$
is $O(2^{j})$ during epoch $j$, so the update cost is $O(\log(T))$ per update.

Finally, we note (1) Lines 22 – 24 takes only $O(\Gamma_{u}\log(T))$ time in
total; (2) Line 13 can be done similarly to Line 17; (3) Line 26 resets
$B_{j}$ ($j\in[0:i-1]$) by changing the pointer, so it incurs only $O(\log T)$
cost.

Overall, Algorithm 2 has worst case update time $O(\Gamma_{u}\log(T))$ per
thread and $O(\Gamma_{u}\cdot\log^{2}(T))$ in total. ∎

###### Proof of Theorem 1.1.

The worst case guarantee has already been established in Lemma 3.2, it remains
to prove the correctness of Algorithm 2.

By Lemma 3.1, the youngest $2$ elements are always contained in $B_{0}$, hence
insertions/deletions are operated correctly, i.e., the removal step (Line 5)
indeed removes element in $B_{0}$. It remains to prove each thread operates
normally, i.e., for any thread $i$ and outer-for-loop-iteration $\tau$, the
removal operation would only remove elements in $B^{(i)}$ during epoch $j$
($j\in[i-1]$). It suffices to prove that $E_{t(i,\tau,j),2^{j+2}}\in
B^{(i)}_{t(i,\tau,j)}$. We prove by induction. This is true in epoch $i-1$ by
Lemma 3.1. Suppose it holds to epoch $j+1$, i.e.,
$E_{t(i,\tau,j+1),2^{j+3}}\in B^{(i)}_{t(i,\tau,j+1)}$, since there are at
most $2^{j+1}$ deletions in epoch $j+1$, we have that
$E_{t(i,\tau,j+1),2^{j+2}}\in B^{(i)}_{t(i,\tau,j)}$. We complete the proof
here. ∎

##  4 Application

We provide a few applications of our reduction.

###  4.1 Submodular maximization

#### Dynamic submodular maximization

In a submodular maximization problem, there is a ground set $N=[n]$ and a set
function $f:N\rightarrow\mathbb{R}^{+}$. The function is said to be monotone
if $f(A)\geq f(B)$ for any $B\subseteq A\subseteq N$ and it is said to be
submodular if $f(A\cup\\{u\\})-f(A)\leq f(B\cup\\{u\\})-f(B)$ for any
$B\subseteq A\subseteq N$ and element $u$. The task of submodular maximization
under a cardinality constraint refers to $\max_{S\subseteq[n],|S|=k}f(S)$ for
some parameter $1\leq k\leq n$, and the task of submodular maximization under
a matroid constraint $\mathcal{M}$ refers to
$\max_{S\subseteq\mathcal{M}}f(S)$. Finally, in a dynamic submodular
maximization problem, the ground set can be inserted and deleted, and the goal
is to maintain a good solution set $S$.

[FLNF+22] provides an $0.3178$-approximation algorithm (with a matroid
constraint) under streaming setting, and one can adapt it to a dynamic
algorithm with worst case update time under incremental setting.

######  Theorem 4.1 (Adapt from [FLNF+22]).

For any $n,k>0$, under the incremental update, there exists a dynamic
algorithm that maintains an $0.3178$-approximate solution for monotone
submodular maximization under a matroid constraint of rank $k$ and makes
$\operatorname{poly}(k,\log n)$ queries per iteration.

The sliding window model is of interests to the community [ELVZ17]. The
algorithm of [ELVZ17] maintains an $1/2$-approximation solution with
polylogarithmic updates time for dynamic submodular maximization under
cardinality constraints. Our reduction gives the first constant approximation
algorithm for a matroid constraint.

######  Theorem 4.2 (Dynamic submodular maximization).

For any $n,k>0$, there exists a dynamic algorithm that achieves
$0.3178$-approximation for the problem of submodular maximization under a
matroid constraint using $\operatorname{poly}(k,\log n)$ queries per update
under the sliding window model.

###  4.2 Depth first search (DFS) tree

#### Dynamic DFS

Given an undirected graph $G=(V,E)$ with $|V|=n,|E|=m$, the task is to
maintain a depth first search (DFS) tree under edge insertion/deletion. In the
incremental model, [BCCK16] obtains a dynamic algorithm with $O(n(\log
n)^{3})$ worst case update time, and it is improved to $O(n)$ by [CDW+18].
While in the fully dynamic model, the current best known algorithm [BCCK16]
has $\widetilde{O}(\sqrt{mn})$ update time.

######  Theorem 4.3 ([BCCK16, CDW+18]).

Given a graph $G=(V,E)$, with $|V|=n$, $|E|=m$. There is a dynamic algorithm
that maintains a DFS tree with $O(n)$ update time in the incremental model.

Using our reduction, one can immediately obtain

######  Theorem 4.4 (Dynamic DFS).

Given a graph $G=(V,E)$, with $|V|=n$, $|E|=m$. There is a dynamic algorithm
that maintains a DFS tree with $\widetilde{O}(n)$ worst case update time in
the offline model.

###  4.3 All-Pair Shortest-Paths (APSP)

#### Dynamic APSP

The APSP problem has been a central topic of graph algorithm. In a dynamic
APSP problem, there is a undirected weighted graph $G=(V,E)$ ($|V|=n,|E|=m$)
that subjects to edge insertion and deletion, The goal of the algorithm is to
maintain an estimate $\delta(u,v)$ for every pair of node $u,v\in V$ that
approximates the shortest path distance between $u$ and $v$. In the
incremental setting, [CGH+20] obtains an $O(1)$-approximate algorithm with
$n^{o(1)}$ worst case update time.

######  Theorem 4.5 (Theorem 3.1 in [CGH+20]).

Let $G=(V,E)$ be a undirected weighted graph, there exists an incremental
deterministic All-Pair Shortest-Paths algorithm that maintains $O(1)$
approximate shortest path in $n^{o(1)}$ worst case update time.

The offline model is of interest and it is already pointed out in [CGH+20]
that their data structure can be adapted to the offline model (but in a
problem specific way). With Theorem 1.1 in hand, we can recover Theorem 4.8 of
[CGH+20].

######  Theorem 4.6 (Dynamic APSP).

Let $G=(V,E)$ be a undirected weighted graph, there exists a deterministic
All-Pair Shortest-Paths algorithm that maintains $O(1)$ approximate shortest
path in $n^{o(1)}$ worst case update time under the offline model.

##  5 Impossibility of general reduction

We prove both conditions (worst case guarantee and known deletion order) are
indeed necessary to obtain a black box reduction.

#### Worst case guarantee is necessary

A black box reduction is generally impossible if one only has amortized
guarantee of incremental model. An example is the dynamic submodular
maximization problem, where unconditional lower bound is known.

######  Theorem 5.1.

Let $T\geq 1$ be the total number of updates. There exists a problem such that
it is possible to have a dynamic algorithm with amortized update time
$\Gamma_{u}$ in the incremental model, but any algorithm in the deletions-
look-ahead model takes at
$\Omega\left(\frac{T}{\log^{4}(T)}\right)\cdot\Gamma_{u}$ amortized update
time.

###### Proof.

Let $[n]$ be the ground set and the total number of update be $T=O(n)$. By
Theorem 1.3 of [CP22], there exists an algorithm with
$O(\log(k/\epsilon)/\epsilon^{2})$ amortized query complexity and maintains an
$(1-1/e-\epsilon)$-approximate solution for dynamic submodular maximization.
While in the fully dynamic model (with known deletion order), by Theorem 1.2
of [CP22], no algorithm could maintain an $0.584$-approximation with
$o(n/k^{3})$ amortized queries whenever $k=\Omega(\log n)$. Taking $k=C\log n$
for some constant $C>0$ exhibits a $\Omega(T/\log^{4}(T))$ separation. ∎

#### Known deletion order is necessary

If the deletion order is not known in advance, there exists a separation
between the fully-dynamic and incremental model.

######  Theorem 5.2.

Let $T\geq 1$ be the total number of updates. There exists a problem such that
it is possible to have a dynamic algorithm with worst case update time $O(1)$
in the incremental model, but any algorithm in the fully dynamic model has
amortized running time $\Omega\left(\frac{T}{\log(T)}\right)$.

###### Proof.

Let $N=[n]$ be the ground set element and $T=2n$ be the total number of
updates. We first formalize the oracle model. For any subset of elements
$A\subseteq N$, let $S(A)\in S$ be the transcript on $A$ and
$Q(A)\in\\{0,1\\}$ be the answer to Query. There exists an oracle $O:S\times
N\rightarrow S\times\\{0,1\\}$, it takes input of a transcript $S(A)\in S$ and
an element $e\in N$, and returns the next transcript $S(A\cup\\{e\\})\in S$
and the answer $Q(A\cup\\{e\\})\in\\{0,1\\}$, i.e.,

$O(S(A),e)=(S(A\cup\\{e\\}),Q(A\cup\\{e\\})).$

The oracle outputs empty when the input is invalid and we assume the oracle
takes unit time.

It is clear that it takes only $1$ oracle call per update in the incremental
model. For the fully dynamic model, consider the update sequence of first
inserting all elements in $N$ and delete them in random order. We prove
$\Omega(n^{2}/\log n)$ oracle calls are necessary. For any $t\in[0:n/100\log
n]$, let $N_{t}$ be the set of elements remain after deleting $4t\log n$
elements and $N_{0}=N$. It suffices to prove the algorithm needs to make at
least $\Omega(n)$ oracle queries between $N_{t}$ and $N_{t+1}$. Suppose the
algorithm has the transcript $S(A_{1}),\ldots S(A_{\ell(t)})$ at the beginning
of the $(n+4t\log n)$-th update, where $A_{i}\subseteq[N_{t}]$ and
$|A_{i}|\geq n/2$ ($i\in[\ell(t)]$). We know that $\ell(t)\leq n^{2}$. After
deleting the next $4\log n$ elements (at random), the probability that
$A_{i}\subseteq N_{t+1}$ is at most $1/n^{4}$. Taking an union bound, with
probability at least $1-1/n^{2}$, none of the set satisfies $A_{i}\subseteq
N_{t+1}$. Then we conclude that to get the transcript of $S(N_{t+1})$, the
algorithm needs at least $|N_{t+1}|-n/2=\Omega(n)$ queries. We conclude the
proof here. ∎

## Acknowledgement

A.R. is grateful to Amir Abboud and Soheil Behnezhad for inspiring
conversations. A.R. and B.P would like to thank Timothy Chan for explaining
the interesting connections to related work from computational geometry.

## References

  * [ADK+16] Ittai Abraham, David Durfee, Ioannis Koutis, Sebastian Krinninger, and Richard Peng.  On fully dynamic graph sparsifiers.  In Irit Dinur, editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 335–344. IEEE Computer Society, 2016.
  * [AW14] Amir Abboud and Virginia Vassilevska Williams.  Popular conjectures imply strong lower bounds for dynamic problems.  In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 434–443. IEEE Computer Society, 2014.
  * [BCCK16] Surender Baswana, Shreejit Ray Chaudhury, Keerti Choudhary, and Shahbaz Khan.  Dynamic dfs in undirected graphs: breaking the o (m) barrier.  In Proceedings of the twenty-seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 730–739. SIAM, 2016.
  * [BDM+20] Vladimir Braverman, Petros Drineas, Cameron Musco, Christopher Musco, Jalaj Upadhyay, David P Woodruff, and Samson Zhou.  Near optimal linear algebra in the online and sliding window models.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 517–528. IEEE, 2020.
  * [Ben73] Charles H Bennett.  Logical reversibility of computation.  IBM journal of Research and Development, 17(6):525–532, 1973.
  * [BKS12] Surender Baswana, Sumeet Khurana, and Soumojit Sarkar.  Fully dynamic randomized algorithms for graph spanners.  ACM Trans. Algorithms, 8(4):35:1–35:51, 2012.
  * [BS80] Jon Louis Bentley and James B Saxe.  Decomposable searching problems i. static-to-dynamic transformation.  Journal of Algorithms, 1(4):301–358, 1980.
  * [CDW+18] Lijie Chen, Ran Duan, Ruosong Wang, Hanrui Zhang, and Tianyi Zhang.  An improved algorithm for incremental dfs tree in undirected graphs.  In 16th Scandinavian Symposium and Workshops on Algorithm Theory, 2018.
  * [CGH+20] Li Chen, Gramoz Goranci, Monika Henzinger, Richard Peng, and Thatchaphol Saranurak.  Fast dynamic cuts, distances and effective resistances via vertex sparsifiers.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1135–1146. IEEE, 2020.
  * [Cha12] Timothy M Chan.  Three problems about dynamic convex hulls.  International Journal of Computational Geometry and Applications, 22(4):341–364, 2012.
  * [CP22] Xi Chen and Binghui Peng.  On the complexity of dynamic submodular maximization.  In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 1685–1698, 2022.
  * [DGIM02] Mayur Datar, Aristides Gionis, Piotr Indyk, and Rajeev Motwani.  Maintaining stream statistics over sliding windows.  SIAM journal on computing, 31(6):1794–1813, 2002.
  * [DS91] David Dobkin and Subhash Suri.  Maintenance of geometric extrema.  Journal of the ACM (JACM), 38(2):275–298, 1991.
  * [ELVZ17] Alessandro Epasto, Silvio Lattanzi, Sergei Vassilvitskii, and Morteza Zadimoghaddam.  Submodular optimization over sliding windows.  In Proceedings of the 26th International Conference on World Wide Web, pages 421–430, 2017.
  * [EMMZ22] Alessandro Epasto, Mohammad Mahdian, Vahab Mirrokni, and Peilin Zhong.  Improved sliding window algorithms for clustering and coverage via bucketing-based sketches.  In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3005–3042. SIAM, 2022.
  * [FLNF+22] Moran Feldman, Paul Liu, Ashkan Norouzi-Fard, Ola Svensson, and Rico Zenklusen.  Streaming submodular maximization under matroid constraints.  In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022.
  * [HdLT01] Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup.  Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity.  J. ACM, 48(4):723–760, 2001.
  * [HHS22] Kathrin Hanauer, Monika Henzinger, and Christian Schulz.  Recent advances in fully dynamic graph algorithms–a quick reference guide.  ACM Journal of Experimental Algorithms (JEA), 2022.
  * [HK99] Monika Rauch Henzinger and Valerie King.  Randomized fully dynamic graph algorithms with polylogarithmic time per operation.  J. ACM, 46(4):502–516, 1999.
  * [HKNS15] Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak.  Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture.  In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 21–30. ACM, 2015.
  * [HN21] Monika Henzinger and Alexander Noe.  Random rank-based, hierarchical or trivial: Which dynamic graph algorithm performs best in practice?  arXiv preprint arXiv:2108.04564, 2021.
  * [KMW98] Sanjeev Khanna, Rajeev Motwani, and Randall H Wilson.  On certificates and lookahead in dynamic graph problems.  Algorithmica, 21(4):377–394, 1998.
  * [KPP16] Tsvi Kopelowitz, Seth Pettie, and Ely Porat.  Higher lower bounds from the 3sum conjecture.  In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1272–1287. SIAM, 2016.
  * [LMNF+20] Silvio Lattanzi, Slobodan Mitrović, Ashkan Norouzi-Fard, Jakub M Tarnawski, and Morteza Zadimoghaddam.  Fully dynamic algorithm for constrained submodular optimization.  Advances in Neural Information Processing Systems, 33:12923–12933, 2020.
  * [OL81] Mark H Overmars and Jan van Leeuwen.  Dynamization of decomposable searching problems yielding good worst-case bounds.  In Theoretical Computer Science, pages 224–233. Springer, 1981\.
  * [OvL81] Mark H Overmars and Jan van Leeuwen.  Two general methods for dynamizing decomposable searching problems.  Computing, 26(2):155–166, 1981.
  * [SM10] Piotr Sankowski and Marcin Mucha.  Fast dynamic transitive closure with lookahead.  Algorithmica, 56(2):180–197, 2010.
  * [vdBNS19] Jan van den Brand, Danupon Nanongkai, and Thatchaphol Saranurak.  Dynamic matrix inverse: Improved algorithms and matching conditional lower bounds.  In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 456–480. IEEE, 2019.
  * [WLFT18] Yanhao Wang, Yuchen Li, Ju Fan, and Kian-Lee Tan.  Location-aware influence maximization over dynamic social streams.  ACM Transactions on Information Systems (TOIS), 36(4):1–35, 2018\.
  * [WZ22] David P Woodruff and Samson Zhou.  Tight bounds for adversarially robust streams and sliding windows via difference estimators.  In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 1183–1196. IEEE, 2022.


# Approximately Hadamard matrices
and Riesz bases in random frames

Xiaoyu Dong  and  Mark Rudelson  Department of Mathematics, University of
Michigan, 530 Church St., Ann Arbor, MI 48109, U.S.A.  {xydong,
<EMAIL_ADDRESS>
###### Abstract.

An $n\times n$ matrix with $\pm 1$ entries which acts on $\mathbb{R}^{n}$ as a
scaled isometry is called Hadamard. Such matrices exist in some, but not all
dimensions. Combining number-theoretic and probabilistic tools we construct
matrices with $\pm 1$ entries which act as approximate scaled isometries in
$\mathbb{R}^{n}$ for all $n\in\mathbb{N}$. More precisely, the matrices we
construct have condition numbers bounded by a constant independent of $n$.

Using this construction, we establish a phase transition for the probability
that a random frame contains a Riesz basis. Namely, we show that a random
frame in $\mathbb{R}^{n}$ formed by $N$ vectors with independent identically
distributed coordinate having a non-degenerate symmetric distribution contains
many Riesz bases with high probability provided that $N\geq\exp(Cn)$. On the
other hand, we prove that if the entries are subgaussian, then a random frame
fails to contain a Riesz basis with probability close to $1$ whenever
$N\leq\exp(cn)$, where $c<C$ are constants depending on the distribution of
the entries.

###### 2000 Mathematics Subject Classification:

60B20

Research supported in part by NSF grant DMS 2054408 and by a fellowship from
the Simons Foundation.

##  1\. Introduction and main results

Let $n<N$ be natural numbers. A set of vectors
$X_{1},\ldots,X_{N}\in\mathbb{R}^{n}$ is called a _frame_ if

(1.1) $K(n,N)\left\|x\right\|_{2}^{2}\leq\sum_{j=1}^{N}\left\langle
x,X_{j}\right\rangle^{2}\leq RK(n,N)\left\|x\right\|_{2}^{2}$

for all $x\in\mathbb{R}^{n}$. Here $R\geq 1$ is an absolute constant called
the frame constant, and $K(n,N)>0$ is some function of $n$ and $N$. The
notation $\left\|x\right\|_{2}$ stands for the Euclidean norm of the vector
$x=(x_{1},\ldots,x_{n})$:

$\left\|x\right\|_{2}=\left(\sum_{j=1}^{n}x_{j}^{2}\right)^{1/2}.$

In the last 40 years, frame theory became a well-developed area of applied
mathematics, see [4], [5], [6], and the references therein. A frame can
intuitively be regarded as overcomplete basis in $\mathbb{R}^{n}$. Because of
this property, frames became a valuable tool in signal transmission. A signal
which is viewed as an $n$-dimensional vector can be encoded by the sequence of
its inner products with the frame vectors. If this sequence is transmitted
over a communication line, then the original signal can be reconstructed even
if part of the coefficients is lost or corrupted in the process of
transmission. Moreover, this encoding is robust, which means that if the inner
products are evaluated with some noise, then the reconstructed version will be
close to the original one with the error depending on the noise magnitude.

One of the most popular classes of frames in algorithmic applications is the
set of random frames. Such frames became also the method of choice in
compressed sensing where one needs to reconstruct a low complexity signal from
a small number of linear measurements, see, e.g., [21]. For example, if
complexity is measured as the size of the support, and the support itself is
unknown, the random frames provide robust recovery with optimal or almost
optimal theoretical guarantees.

To construct a random frame, consider a random vector $X\in\mathbb{R}^{n}$
with centered uncorrelated coordinates of unit variance. In other words,
assume that $\operatorname{\mathbb{E}}X=0$ and
$\operatorname{\mathbb{E}}XX^{\top}=I_{n}$. Let vectors $X_{1},\ldots,X_{N}$
be independent copies of $X$. The Law of Large Numbers implies that

$\lim_{N\to\infty}\frac{1}{N}\sum_{j=1}^{N}X_{j}X_{j}^{\top}=I_{n}\quad\text{a.s.}$

and thus, with probability close to $1$,

$(1-\varepsilon)\left\|x\right\|_{2}^{2}\leq\sum_{j=1}^{N}\left\langle
x,X_{j}\right\rangle^{2}\leq(1+\varepsilon)\left\|x\right\|_{2}^{2}$

for all $x\in\mathbb{R}^{n}$ provided that $N=N(\varepsilon)$ is sufficiently
large.

Another, trivial way to construct a frame is to take several bases in
$\mathbb{R}^{n}$ and concatenate them. This allows an exact reconstruction of
the transmitted signal if the number of corrupted coordinates is relatively
small. Indeed, one can reconstruct the original vector from the set of
transmitted coordinates for each basis separately and keep the copy which is
repeated many times. While in practice the random frames perform better than
such concatenated bases, it leads to a question whether a random frame
contains a copy or copies of a nice basis. More precisely, a sequence of $n$
vectors $v_{1},\ldots,v_{n}\in\mathbb{R}^{n}$ is called a Riesz basis if it
possesses the frame property (1.1). This property ensures that the
reconstruction is robust, i.e., that the reconstructed vector is close to the
original one if the coordinates are distorted by adding a small noise. These
considerations lead to a natural question of determining the values of $N$ for
which a random frame $\\{X_{1},\ldots,X_{N}\\}\subset\mathbb{R}^{n}$ contains
one or many Riesz bases with high probability.

This problem can be conveniently translated to the language of random
matrices. Namely, for an $n\times N$ matrix $A$, define its singular values as

$s_{\max}(A)=s_{1}(A)\geq s_{2}(A)\geq\cdots\geq s_{n}(W)=s_{\min}(A)\geq 0,$

where $s_{j}(A)=\sqrt{\lambda_{j}(AA^{\top})}$, and
$\lambda_{1}(AA^{\top}),\ldots,\lambda_{n}(AA^{\top})$ are eigenvalues of
$AA^{\top}$ arranged in the decreasing order. Also, define the condition
number of $A$ as

$\kappa(A)=\frac{s_{\max}(A)}{s_{\min}(A)}$

using the convention that $\kappa(A)=\infty$ whenever $s_{\min}(A)=0$. With
this notation, the frame property (1.1) can be rewritten as
$\kappa(A_{n,N})\leq C$ where $A_{n,N}$ is the $n\times N$ matrix with columns
$X_{1},\ldots,X_{N}$. Thus, the problem of existence of a Riesz basis in a
random frame can be recast as the question of existence of one or many well-
conditioned square $n\times n$ submatrices of an $n\times N$ random matrix
$A_{n,N}$ with i.i.d. entries. Our first main result shows that the
probability of finding such a submatrix undergoes a phase transition when $N$
is exponential in terms of $n$. Since the upper and the lower bound hold under
somewhat different assumptions, we formulate them separately.

Denote by $[N]$ the set $\\{1,\ldots,N\\}$. Let $A$ be an $n\times N$ matrix.
If $I\subset[N]$, denote by $A_{I}$ the submatix of $A$ whose columns belong
to $I$. The following theorem shows that if $N$ is exponential in $n$, then
with high probability, the $n\times N$ random matrix has many square
submatrices with uniformly bounded condition numbers. In the language of
frames, it means that a random frame with exponentially many vectors contains
a large number of Riesz bases whose frame constants are uniformly bounded.

######  Theorem 1.1.

Let $A$ be an $n\times N$ matrix with i.i.d. symmetric non-degenerate entries.
Then there exist constants $c,C,\alpha,\beta>0$ depending on the distribution
of entries of $A$ with the following property.
Assume that

$N\geq\exp(Cn).$

Then there exists

$L\geq\exp(cn)$

such that

$\displaystyle\mathbb{P}\big{(}\text{\rm exist disjoint subsets
}I_{1},\ldots,I_{L}\text{\rm\ of }[N]\text{\rm\ with }\big{.}$
$\displaystyle\qquad\big{.}|I_{j}|=n\text{\rm\ and
}\kappa(A_{I_{j}})<\alpha\text{\rm\ for all }j\in[L]\big{)}$
$\displaystyle\geq 1-\exp\left(-\exp(\beta n)\right).$

The strategy of proving Theorem 1.1 relies on using a certain deterministic
$n\times n$ matrix $V$ having a bounded condition number. Denote by
$\text{Col}_{j}(M)$ the $j$-th column of the matrix $M$. We partition the set
of integers $[N]$ into $n$ subsets $I_{1},\ldots,I_{n}$ of approximately the
same size and show that with high probability, the set
$\\{\text{Col}_{i}(A)\\}_{i\in I_{j}}$ contains many columns close to
$\text{Col}_{j}(V)$. Condition on the event that such columns exist and form
an $n\times n$ matrix $B$ taking one column from each set. Then conditionally
this matrix can be viewed as a noisy version of the matrix $V$. This allows to
show that with high probability, the matrix $B$ has a bounded condition number
as well.

The key to this strategy is a successful choice of the pattern matrix $V$.
Since we strive to prove Theorem 1.1 under minimal assumptions, the choice of
$V$ becomes a non-trivial task. Indeed, the requirement that a column of $A$
can be close to a column of $V$ with a non-negligible probability forces us to
look for matrices $V$ whose entries are in the support of the distribution of
an entry of $A$. The latter can be as small as two points, $a$ and $-a$
because of the symmetry assumption. Thus, we need to to construct $V$ as a
scaled copy of a matrix with $\pm 1$ entries. Such matrices are known in some
cases. For instance, the condition number of any Hadamard matrix is one. An
$n\times n$ matrix $H$ is called Hadamard if $n^{-1/2}H$ is an isometry. The
earliest result on the existence of Hadamard matrices was probably proved by
Sylvester [20] who showed that Hadamard matrices exist for dimension $2^{k}$
where $k$ is any nonnegative integer (these matrices are now called Wash since
their rows are Walsh functions). Hadamard matrices is a well-studied subject,
and a number of constructions of such matrices are available, see e.g., the
books [1], [12], and the references therein. In particular, Wallis [23] proved
that if $p>3$ is an integer, then there exists an Hadamard matrix of order
$2^{t}p$, where $t=\left\lfloor{2{{\log}_{2}}(p-3)}\right\rfloor$. Craigen [7]
improved Wallis’s result by showing that for any odd number $p$, there exists
an Hadamard matrix of order $2^{t}p$, where
$t=4\left\lceil{\frac{1}{6}{{\log}_{2}}((p-1)/2)}\right\rceil+2$. Recently, de
Launey [10] studied the asymptotic existence of Hadamard matrices and
concluded that for any $\epsilon>0$, the set of odd numbers $k$ for which
there is a Hadamard matrix of order $k2^{2+[{\epsilon{{\log}_{2}}(k)}]}$
always has positive density in the set of natural numbers. Yet, the dimensions
in which Hadamard matrices were constructed are rare.

This leads us to a task of constructing _approximately Hadamard matrices_ ,
i.e., matrices with $\pm 1$ entries and bounded condition numbers. Some
constructions of matrices with properties simlar to Hadamard’s are available.
For example, Banica, Nechita, and Życzkowski [2] defined an almost Hadamard
matrix to be a $N$ dimensional real square matrix $H$, such that $H/\sqrt{N}$
is orthogonal, and is a local maximum of the $\ell_{1}$-norm of the entries on
the orthogonal group $O(N)$. They showed the existence of almost Hadamard
matrices under some special assumptions. There is also a notion of quasi-
Hadamard matrix [2, 15], which is defined as a square matrix with $\\{-1,1\\}$
entries that maximizes the absolute value of the determinant, but there are
only very limited results on the existence of those matrices. In summary, no
existing construction is directly related to our purpose.

The second main result of the paper is the following theorem asserting the
existence of an approximately Hadamard matrix in all dimensions.

######  Theorem 1.2.

There exist constants $0<c<C$ such that for any $n\in\mathbb{N}$, one can find
an $n\times n$ matrix $V$ with $\pm 1$ entries satisfying

$c\sqrt{n}\leq s_{\min}(V)\leq s_{\max}(V)\leq C\sqrt{n}.$

The proof of Theorem 1.2 relies on Vinogradov’s theorem from analytic number
theory and combines number-theoretic and probabilistic ideas. The details are
presented in Section 2. After Theorem 1.2 is proved, we prove Theorem 1.1 in
Section 3.

The conclusion of Theorem 1.1 holds under minimal assumptions on the
distribution of entries. If we assume that the entries of the matrix are sub-
gaussian, then the bound of Theorem 1.1 becomes sharp. Recall that a random
variable $X$ is called subgaussian if there is $a>0$ such that

$\operatorname{\mathbb{E}}\exp\left(\frac{X^{2}}{a^{2}}\right)\leq 2.$

If $X$ is subgaussian then the smallest number $a$ having this property is
called the subgaussian norm of $X$ and denoted $\left\|X\right\|_{\psi_{2}}$.
Subgaussian random variables form a large family containing many naturally
arising ones, see, e.g. [22].

The next theorem shows that finding a submatrix with a bounded condition
number requires an exponential number of columns for matrices with subgaussian
entries.

######  Theorem 1.3.

Let $X$ be a centered subgaussian random variable. Then there exist
$C,c,\tilde{c},t_{0}>0$ depending only on
$\frac{\left\|X\right\|_{\psi_{2}}}{\left\|X\right\|_{2}}$ with the following
property. Let $t>t_{0}$, and assume that

$N\leq\exp\left(\frac{\tilde{c}}{t^{4}}n\right).$

Let $A$ be an $n\times N$ matrix whose entries are independent copies of $X$.
Then

$\mathbb{P}\left(\exists I\subset[N]\ |I|=n\text{ and
}\kappa(A_{I})<t\right)\leq\exp\left(-c\frac{n^{2}}{t^{4}}\right).$

We prove Theorem 1.3 in Section 4. Its proof is easier than that of Theorem
1.1 and relies on the Hanson-Wright inequality [19].

### Acknowledgment.

The second author is grateful to Marcin Bownik for helpful discussions and
bringing his attention to the problem. Part of this work was done when the
second author visited the Weizmann Institute of Science. He is grateful to the
Institute for its hospitality. The authors thank a referee for thoroughly
checking the manuscript and correcting many typos.

##  2\. Approximately Hadamard matrices

In this section we construct an $n\times n$ matrix with $\pm 1$ entries whose
scaled copy acts on $\mathbb{R}^{n}$ as an approximate isometry. More
precisely, for any sufficiently large $n$, we construct an $n\times n$ matrix
$V$ such that its condition number $\kappa(V)$ is bounded by an absolute
constant.

We use standard matrix norms below. Namely, $\left\|A\right\|$ stands for the
operator norm of an $n\times m$ matrix $A=(a_{i,j})$, and
$\left\|A\right\|_{\operatorname{HS}}$ stands for its Hilbert-Schmidt or
Frobenius norm:

$\left\|A\right\|=\max_{\left\|x\right\|_{2}=1}\left\|Ax\right\|_{2},\quad\text{and}\quad\left\|A\right\|_{\operatorname{HS}}=\left(\sum_{i=1}^{n}\sum_{j=1}^{m}a_{i,j}^{2}\right)^{1/2}.$

We will apply an above mentioned result of Wallis [23] showing that Hadamard
matrices exist in dimensions close to $n^{3}$.

######  Lemma 2.1.

There is $l_{0}\in\mathbb{N}$ such that for any $l>l_{0}$, there exists an
Hadamard matrix of dimension $m(l)$ with

$m(l)=2^{2\lceil\log_{2}(l-3)\rceil}l.$

We will need the following corollary.

######  Corollary 2.2.

For any $\varepsilon>0$, there exists $N(\varepsilon)$ such that for any
$n>N_{0}(\varepsilon)$, one can find an even number
$m\in[(1-\varepsilon)n,(1+\varepsilon)n]$ for which there exists an Hadamard
matrix of size $m\times m$.

###### Proof.

For any $n>12$, there exists a unique $k\in\mathbb{N}$ such that
$2^{2k}(2^{k-1}+3)<n\leq 2^{2(k+1)}(2^{k}+3)$. Assume first that
$2^{2k}(2^{k-1}+3)<n\leq 2^{2k}(2^{k}+3)$. Set

$m=2^{2k}\left\lceil\frac{n}{2^{2k}}\right\rceil.$

By Lemma 2.1, there exists an Hadamard matrix of size $m\times m$. Since

$1\leq\frac{m}{n}=\frac{\lceil 2^{-2k}n\rceil}{2^{-2k}n},$

and $2^{-2k}n\geq 2^{k-1}+3>(n/2)^{1/3}$, the result follows if we choose
$N(\varepsilon)$ sufficiently large.

Since the tensor product of Hadamard matrices is an Hadamard matrix, and there
are Hadamard matrices of sizes $2\times 2$ and $4\times 4$, there exist
Hadamard matrices of sizes $2m(l)$ and $4m(l)$ for all $l>l_{0}$. This allows
completing the proof of the corollary in the remaining cases when
$2^{2k+1}(2^{k-1}+3)<n\leq 2^{2k+1}(2^{k}+3)$ and $2^{2k+2}(2^{k-1}+3)<n\leq
2^{2k+2}(2^{k}+3)$. ∎

The aim of this section is to construct _approximately Hadamard_ matrices in
any dimension, i.e. matrices whose condition number is $O(1)$. To this end, we
use a construction of approximately Hadamard matrices of a prime size.

Let $q\in\mathbb{N}$ be an odd prime number. For $k\in\mathbb{Z}_{q}$, denote

$e_{q}(k)=\exp\left(2\pi i\frac{k}{q}\right).$

Define the Fourier transform on $\mathbb{Z}_{q}$ setting

$\hat{v}(j)=\sum_{k\in\mathbb{Z}_{q}}v(k)e_{q}(jk)$

for a vector $v\in\mathbb{C}^{\mathbb{Z}_{q}}$ and $j\in\mathbb{Z}_{q}$.

######  Lemma 2.3.

Let $q$ be an odd prime number. Then there exists a vector
$u_{q}\in\\{-1,1\\}^{\mathbb{Z}_{q}}$ such that

$\big{|}|\hat{u}_{q}(j)|-\sqrt{q}\big{|}\leq\sqrt{q}\delta_{q}\quad\text{for
any }j\in\mathbb{Z}_{q}$

with $\delta_{q}=Cq^{-1/4}\sqrt{\log q}$.

###### Proof.

The construction closely follows the one in [23, Proposition 3.2], which in
turn originates in [16, Theorem 9.2].

Let $v:\mathbb{Z}_{q}\to\\{-1,1\\}$ be the Legendre symbol (quadratic
character mod $q$). More precisely, let

$Q=\\{k\in\mathbb{Z}_{q}:\ k=j^{2}(\text{mod }q)\text{ for some
}j\in\mathbb{Z}_{q}\\}\setminus\\{0\\}$

be the set of quadratic residues, and set

$v(k)=\begin{cases}1,&\text{if }k\in Q;\\\ -1,&\text{if
}k\in\mathbb{Z}_{q}\setminus(Q\cup\\{0\\});\\\ 0,&\text{if }k=0.\end{cases}$

Then by a standard result on the Gauss sum, see e.g., [13, Proposition 6.3.2.;
p.71], we have

$|\hat{v}(j)|=\begin{cases}\sqrt{q},&\text{if
}j\in\mathbb{Z}_{q}\setminus\\{0\\}\\\ 0,&\text{if }j=0.\end{cases}$

The difference between $v$ and the desired function $u_{q}$ is that $v(0)=0$
and $\hat{v}(0)=0$. We will perturb $v$ replacing some of its coordinates by
$-1$ to change the value of $\hat{v}(0)$ as required while keeping the other
Fourier coefficients close to their original values. To this end, consider a
sequence of i.i.d. random variables $\\{X_{k}\\}_{k\in Q}$ such that

$\mathbb{P}(X_{k}=-1)=q^{-1/2}\quad\text{and}\quad\mathbb{P}(X_{k}=1)=1-q^{-1/2}.$

Set

$u_{q}(k)=\begin{cases}X_{k},&\text{if }k\in Q;\\\ -1,&\text{if
}k\in\mathbb{Z}_{q}\setminus Q;\\\ \end{cases}$

Then $u_{q}:\mathbb{Z}_{q}\to\\{-1,1\\}$, so we only have to check the values
of the Fourier coefficients. Let us start with the expectations. We have

$\displaystyle\operatorname{\mathbb{E}}\hat{u_{q}}(0)=\operatorname{\mathbb{E}}\hat{u_{q}}(0)-\hat{v}(0)$
$\displaystyle=\sum_{k\in
Q}(\operatorname{\mathbb{E}}X_{k}-1)-1=-2q^{-1/2}|Q|-1$
$\displaystyle={q^{-1/2}}-{q^{1/2}}-1,$ and
$\displaystyle\operatorname{\mathbb{E}}\hat{u_{q}}(j)-\hat{v}(j)$
$\displaystyle=\sum_{k\in
Q}(\operatorname{\mathbb{E}}X_{k}-1)e_{q}(jk)-1=\sum_{k\in
Q}(-2q^{-1/2})e_{q}(jk)-1$

for all $j\in\mathbb{Z}_{q}\setminus\\{0\\}$. Evaluation of the last sum is
standard, see [8, Ch. 2], or [13, Ch. 6]. Namely,

$\displaystyle\left|1+2\sum_{k\in Q}e_{q}(jk)\right|^{2}$
$\displaystyle=\left|\sum_{k\in\mathbb{Z}_{q}}e_{q}(jk^{2})\right|^{2}=\sum_{k,l\in\mathbb{Z}_{q}}e_{q}(jk^{2})\overline{e_{q}(jl^{2})}$
$\displaystyle=\sum_{k,l\in\mathbb{Z}_{q}}e_{q}\big{(}j(k+l)(k-l)\big{)}=q,$

where the last equality follows if we fix $k+l$ and sum over $k-l$ first.
Thus,

$\left|\operatorname{\mathbb{E}}\hat{u_{q}}(j)-\hat{v}(j)\right|\leq
2+q^{-1/2}\quad\text{for any }j\in\mathbb{Z}_{q}\setminus\\{0\\},$

and so $\big{|}|\operatorname{\mathbb{E}}\hat{u_{q}}(j)|-\sqrt{q}\big{|}\leq
3$ for all $j\in\mathbb{Z}_{q}$.

The quantity $\hat{u_{q}}(j)-\operatorname{\mathbb{E}}\hat{u_{q}}(j)$ is a
linear combination of i.i.d. centered random variables
$X_{k}-\operatorname{\mathbb{E}}X_{k},\ k\in Q$ with coefficients $e_{q}(jk)$
whose absolute value is bounded by $1$. Therefore, Bernstein’s inequality
yields

$\mathbb{P}\left(|\hat{u_{q}}(j)-\operatorname{\mathbb{E}}\hat{u_{q}}(j)|>t\right)\leq
2\exp\left(-c\min(t^{2}q^{-1/2},t)\right)$

for all $t>0$ and $j\in\mathbb{Z}_{q}$. Setting $t=Cq^{1/4}\sqrt{\log q}$ and
taking the union bound over $j\in\mathbb{Z}_{q}$, we obtain

$\mathbb{P}\left(|\hat{u_{q}}(j)-\operatorname{\mathbb{E}}\hat{u_{q}}(j)|\leq
Cq^{1/4}\sqrt{\log q}\text{ for all }j\in\mathbb{Z}_{q}\right)\geq 1-q^{-1}>0$

if the constant $C>0$ is chosen sufficiently large. The lemma follows. ∎

######  Corollary 2.4.

Let $q$ be an odd prime number. There exists a $q\times q$ matrix $U_{q}$ with
$\pm 1$ entries such that

$\sqrt{q}(1-\delta_{q})\leq s_{\min}(U_{q})\leq
s_{\max}(U_{q})\leq\sqrt{q}(1+\delta_{q})$

with $\delta_{q}=Cq^{-1/4}\sqrt{\log q}$.

###### Proof.

Represent $\mathbb{Z}_{q}$ as $\\{1,\ldots,q\\}$, and let
$u_{q}:\\{1,\ldots,q\\}\to\\{-1,1\\}$ be the vector defined in Lemma 2.3. Let
$U_{q}$ be the circulant matrix with the first row $u_{q}$. A circulant matrix
is diagonal in the Fourier basis, see e.g., [9, Theorem 3.2.1; p. 72].
Therefore, the singular values of $U_{q}$ are the absolute values of its
eigenvalues which are the Fourier coefficients of the generating vector
$u_{q}$. The result follows from Lemma 2.3. ∎

######  Remark 2.5.

Corollary 2.4 implies that the matrix $U_{q}$ satisfies

(2.1) $\displaystyle\left\|U_{q}(U_{q})^{\top}-qI_{q}\right\|\leq
3\delta_{q}q.$

Inequality (2.1) will be used later in the proof of Theorem 1.2.

With this auxiliary construction in place, we can prove the main result of
this section, namely Theorem 1.2.

###### Proof of Theorem 1.2.

The proof of this theorem combines a deterministic construction of number-
theoretic nature with a probabilistic argument. Without loss of generality, we
can assume that $n$ is larger than some number $n_{0}$ chosen in advance.
Indeed, after the statement of the theorem is proved for $n\geq n_{0}$, we can
adjust the constants $c$ and $C$ appropriately to make it hold for all
$n\in\mathbb{N}$.

We start with the case when $n$ is even. Let $\varepsilon>0$ be a number to be
chosen later. A combination of the Prime Number Theorem and Vinogradov’s sum
of three primes theorem [18], yields that there exists $N=N(\varepsilon)$ such
that any even $n>N$ has a decomposition

(2.2) $n=q_{1}+q_{2}+q_{3}+q_{4}\text{ with }(1-\varepsilon)\frac{n}{4}\leq
q_{j}\leq(1+\varepsilon)\frac{n}{4},$

where $q_{1},\ldots,q_{4}$ are prime numbers. Indeed, by the Prime Number
Theorem, there exists a prime number $q_{1}$ such that
$(1-\varepsilon/2)\frac{n}{4}\leq q_{1}\leq(1+\varepsilon/2)\frac{n}{4}$. Then
$m=n-q_{1}$ is odd, and thus by a stronger version of Vinogradov’s theorem, it
can be decomposed as

(2.3) $m=q_{2}+q_{3}+q_{4},\text{ where }(1-\varepsilon/2)\frac{m}{3}\leq
q_{j}\leq(1+\varepsilon/2)\frac{m}{3},$

and $q_{2},q_{3},q_{4}$ are primes. This immediately implies (2.2). Actually,
decompositions with bounds tighter than (2.3) are available. More precisely,
one can find a representations such as (2.3) with $|q_{j}-m/3|<m^{\theta}$ for
some $\theta\in(0,1)$, see e.g., [3, 11, 17]. However, the weaker version
presented above will be sufficient for our purposes.

Without loss of generality, assume that $q_{1}\geq\cdots\geq q_{4}=:q$. We
will consider the case $q_{3}>q_{4}$ first. This is the most non-trivial case,
and the other ones will be treated in the same way after obvious
modifications. For $j=\\{1,\ldots,4\\}$, let $U_{j}$ be the matrix $U_{q_{j}}$
constructed in Corollary 2.4, and denote by $U_{j}^{top}$ the submatrix formed
by the $q$ top rows of $U_{j}$. For $j\in\\{1,2,3\\}$, denote by
$U_{j}^{bottom}$ the submatrix of $U_{j}$ formed by its $q_{j}-q$ bottom rows.
We will construct the matrix $W=V^{\top}$ in the following block form:

$W=\begin{pmatrix}W_{1,1}&W_{1,2}&W_{1,3}&W_{1,4}\\\ \vdots&\ddots&&\vdots\\\
\vdots&&\ddots&\vdots\\\ W_{4,1}&W_{4,2}&W_{4,3}&W_{4,4}\\\
W_{5,1}&W_{5,2}&W_{5,3}&W_{5,4}\\\ W_{6,1}&W_{6,2}&W_{6,3}&W_{6,4}\\\
W_{7,1}&W_{7,2}&W_{7,3}&W_{7,4}\\\ \end{pmatrix}=\begin{pmatrix}W^{top}\\\
W^{bottom}\end{pmatrix},$

where the matrix $W^{top}$ consists of the upper $4$ block rows of $W$, and
$W^{bottom}$ consists of the lower three. Here $W_{j,k}$ is a $q\times q_{k}$
matrix if $1\leq j,k\leq 4$ and a $(q_{j-4}-q)\times q_{k}$ matrix if
$j=5,6,7,\ 1\leq k\leq 4$.

Let us define the matrices $W_{j,k}$. The matrix $W^{top}$ will be
deterministic, and the matrix $W^{bottom}$ will consist of deterministic and
random blocks. For $1\leq j,k\leq 4$, set
$W_{j,k}=\varepsilon_{j,k}U_{k}^{top}$, where $\varepsilon_{j,k},\
j,k\in\\{1,\ldots,4\\}$ form a $4\times 4$ Walsh matrix:

$\begin{pmatrix}\varepsilon_{1,1}&\varepsilon_{1,2}&\varepsilon_{1,3}&\varepsilon_{1,4}\\\
\varepsilon_{2,1}&\varepsilon_{2,2}&\varepsilon_{2,3}&\varepsilon_{2,4}\\\
\varepsilon_{3,1}&\varepsilon_{3,2}&\varepsilon_{3,3}&\varepsilon_{3,4}\\\
\varepsilon_{4,1}&\varepsilon_{4,2}&\varepsilon_{4,3}&\varepsilon_{4,4}\end{pmatrix}=\begin{pmatrix}1&1&1&1\\\
1&-1&1&-1\\\ 1&1&-1&-1\\\ 1&-1&-1&1\\\ \end{pmatrix}.$

Now, let us define the matrices $W_{j,k}$ for $j=5,6,7$. Set
$W_{j,j-4}=U_{j-4}^{bottom}$. For $j=5,6,7$ and $k\neq j-4$, let $W_{j,k}$ be
a random matrix with i.i.d. Rademacher entries.

Consider the $(4q)\times(4q)$ matrix $W^{top}(W^{top})^{\top}$ first. The
diagonal blocks of this matrix are close to $nI_{q}$. More precisely, for any
$j\in\\{1,\ldots,4\\}$,

$\displaystyle\left\|\sum_{k=1}^{4}W_{j,k}W_{j,k}^{\top}-nI_{q}\right\|$
$\displaystyle=\left\|\sum_{k=1}^{4}\left(U^{top}_{k}(U^{top}_{k})^{\top}-q_{k}I_{q}\right)\right\|\leq\sum_{k=1}^{4}\left\|U_{k}(U_{k})^{\top}-q_{k}I_{q_{k}}\right\|$
$\displaystyle\leq 12\delta_{q}n,$

where the first inequality follows since $U^{top}_{k}(U^{top}_{k})^{\top}$ is
a submatrix of $U_{k}(U_{k})^{\top}$ and the second one from (2.1).

Let us consider the off-diagonal blocks now. If $i\neq j,\
i,j\in\\{1,\ldots,4\\}$ then similarly

$\displaystyle\left\|\sum_{k=1}^{4}W_{j,k}W_{i,k}^{\top}\right\|$
$\displaystyle=\left\|\sum_{k=1}^{4}\varepsilon_{i,k}\varepsilon_{j,k}U^{top}_{k}(U^{top}_{k})^{\top}\right\|$
$\displaystyle\leq\left\|\sum_{k=1}^{4}\varepsilon_{i,k}\varepsilon_{j,k}\left(U^{top}_{k}(U^{top}_{k})^{\top}-q_{k}I_{q}\right)\right\|+\left|\sum_{k=1}^{4}\varepsilon_{j,k}\varepsilon_{i,k}q_{k}\right|$
$\displaystyle\leq 12\delta_{q}n+\varepsilon n,$

where the first estimate follows from the triangle inequality, and the second
one from $q_{k}\in[(1-\varepsilon)\frac{n}{4},(1+\varepsilon)\frac{n}{4}]$.
Combining the two inequalities, we obtain

(2.4) $\left\|W^{top}(W^{top})^{\top}-nI_{4q}\right\|\leq
12\delta_{q}n+12(12\delta_{q}n+\varepsilon n)\leq 13\varepsilon n$

for all sufficiently large $n$.

Let us introduce auxiliary $(n-4q)\times n$ matrices $S$ and $R$ defined by

$S=\begin{pmatrix}U_{1}^{bottom}&0&0&0\\\ 0&U_{2}^{bottom}&0&0\\\
0&0&U_{3}^{bottom}&0\end{pmatrix}\qquad R=W^{bottom}-S.$

In other words, $R$ is the random part of the matrix $W^{bottom}$, i.e.,

$\displaystyle R=\begin{pmatrix}0&W_{5,2}&W_{5,3}&W_{5,4}\\\
W_{6,1}&0&W_{6,3}&W_{6,4}\\\ W_{7,1}&W_{7,2}&0&W_{7,4}\\\ \end{pmatrix}$

is an $(n-4q)\times n$ matrix with zeros along the block diagonal
corresponding to the positions of $U_{1}^{bottom}$, $U_{2}^{bottom}$, and
$U_{3}^{bottom}$ and i.i.d. Rademacher entries elsewhere.

Recall that $n-4q\leq 4\varepsilon n$. In view of Corollary 2.4 and inequality
(2.1),

(2.5) $\displaystyle\left\|S\right\|$
$\displaystyle\leq\sqrt{\frac{n}{4}}(1+\delta_{q}),\qquad\left\|S(W^{top})^{\top}\right\|\leq
12\delta_{q}n,$ $\displaystyle\left\|S\right\|_{\operatorname{HS}}^{2}$
$\displaystyle\leq 3\varepsilon
n\cdot(1+\varepsilon)\frac{n}{4}\leq\varepsilon n.$

Also,

$\displaystyle\left\|SS^{\top}-\frac{n}{4}I_{n-4q}\right\|$
$\displaystyle\leq\max_{j=1,2,3}\left\|U_{j}^{bottom}(U_{j}^{bottom})^{\top}-q_{j}I_{q_{j}-q}\right\|+\varepsilon\frac{n}{4}$
$\displaystyle\leq\varepsilon\frac{n}{2}.$

Let $\tilde{R}$ be an $(n-4q)\times n$ matrix with i.i.d. Rademacher entries.
Then a simple symmetrization argument yields

$\mathbb{P}\left(\left\|SR^{\top}\right\|\geq C\sqrt{\varepsilon}n\right)\leq
2\mathbb{P}\left(\left\|S\tilde{R}^{\top}\right\|\geq(C/2)\sqrt{\varepsilon}n\right)$

which in combination with [19, Theorem 3.2] implies that

$\mathbb{P}\left(\left\|SR^{\top}\right\|\leq C\sqrt{\varepsilon}n\right)\geq
1-\exp(-c\varepsilon n).$

Another application of symmetrization yields

$\mathbb{P}(\left\|R\right\|\geq 4\sqrt{n})\leq 2\mathbb{P}(\|\tilde{R}\|\geq
2\sqrt{n})\leq\exp(-cn).$

Fix a matrix $R$ for which

(2.6) $\left\|SR^{\top}\right\|\leq C\sqrt{\varepsilon}n\quad\text{and
}\left\|R\right\|\leq 4\sqrt{n}$

at the same time.

Let $x\in S^{n-1}$. Following the previous convention, we write

$x=\begin{pmatrix}x^{top}\\\ x^{bottom}\end{pmatrix},$

where $x^{top}\in\mathbb{R}^{4q}$ and $x^{bottom}\in\mathbb{R}^{n-4q}$. Assume
first that $\left\|x^{bottom}\right\|_{2}\geq\eta$, where the constant
$\eta>0$ will be chosen below. Then

$\displaystyle\left\|W^{\top}x\right\|_{2}$
$\displaystyle\geq\frac{1}{\left\|S\right\|}\cdot\left\|SW^{\top}x\right\|_{2}$
$\displaystyle\geq\frac{1}{\left\|S\right\|}\cdot\left(\left\|S(W^{bottom})^{\top}x^{bottom}\right\|_{2}-\left\|S(W^{top})^{\top}x^{top}\right\|_{2}\right)$
$\displaystyle\geq(1-2\delta_{n})\sqrt{\frac{4}{n}}\cdot$
$\displaystyle\qquad\left(\left\|SS^{\top}x^{bottom}\right\|_{2}-\left\|SR^{\top}x^{bottom}\right\|_{2}-\left\|S(W^{top})^{\top}x^{top}\right\|_{2}\right)$
$\displaystyle\geq(1-2\delta_{n})\sqrt{\frac{4}{n}}\cdot$
$\displaystyle\qquad\qquad\left((1-2\varepsilon)\frac{n}{4}\left\|x^{bottom}\right\|_{2}-\left\|SR^{\top}\right\|-\left\|S(W^{top})^{\top}\right\|\right)$
$\displaystyle\geq(1-4\delta_{n})\sqrt{\frac{n}{4}}\cdot\left((1-2\varepsilon)\left\|x^{bottom}\right\|_{2}-C_{1}\sqrt{\varepsilon}\right)$
$\displaystyle\geq\frac{\eta}{4}\sqrt{n}$

if $\eta$ and $\varepsilon$ are chosen so that $(1-2\varepsilon)\eta-
C_{1}\sqrt{\varepsilon}>\eta/2$.

Assume now that $\left\|x_{bottom}\right\|_{2}<\eta$. Then
$\left\|x_{top}\right\|_{2}>1-\eta$, and (2.4) yields

$\displaystyle\left\|W^{\top}x\right\|_{2}$
$\displaystyle\geq\left\|(W^{top})^{\top}x^{top}\right\|_{2}-\left\|(W^{bottom})^{\top}\right\|\cdot\left\|x^{bottom}\right\|_{2}$
$\displaystyle\geq(1-7\varepsilon)\sqrt{n}\cdot\left\|x^{top}\right\|_{2}-C_{2}\sqrt{n}\cdot\left\|x^{bottom}\right\|_{2}$
$\displaystyle\geq(1-7\varepsilon)\sqrt{n}\cdot(1-\eta)-C_{2}\sqrt{n}\cdot\eta$
$\displaystyle\geq\frac{1}{2}\sqrt{n}$

if $\eta$ is chosen so that $C_{2}\eta<\frac{1}{4}$. Choosing the parameters
$\varepsilon$ and $\eta$ sufficiently small, we can reconcile the two
restrictions, i.e., select $\varepsilon,\eta$ so that the inequalities

$(1-2\varepsilon)\eta-C_{1}\sqrt{\varepsilon}>\eta/2\quad\text{and}\quad
C_{2}\eta<\frac{1}{4}$

hold at the same time. With this choice, the previous argument shows that

$\left\|W^{\top}x\right\|_{2}\geq\min\left(\frac{\eta}{4},\frac{1}{2}\right)\sqrt{n}$

for all $x\in S^{n-1}$, which means that

$s_{\min}(W^{\top})\geq c\sqrt{n}.$

Obtaining a bound for $s_{\max}(W)$ is easier. Inequalities (2.4) and (2.5)
imply

$\left\|W^{top}\right\|\leq 2\sqrt{n}\quad\text{and
}\left\|S\right\|\leq\sqrt{n}.$

This in combination with (2.6) yields

$s_{\max}(W^{\top})\leq C\sqrt{n},$

which proves the theorem in the case $q_{3}>q$.

If $q_{j}=q$ for some $j\in\\{1,2,3\\}$, then we repeat the same argument with
the block rows of $W$ containing $q_{j}-q=0$ rows removed. For instance, if
$q_{1}>q$ and $q_{2}=q_{3}=q$, then we consider the $n\times n$ matrix $W$
with $W^{top}$ being the same as in the previous case and
$W^{bottom}=(W_{5,1}\cdots W_{5,4})$ which is a $(q_{1}-q)\times n$ matrix.

This completes the proof of the theorem in the case when $n$ is even.

Assume that $n$ is odd. By Corollary 2.2, if $n$ is sufficiently large, then
we can find an even number

$m\in\left[\left(1-\frac{\varepsilon}{2}\right)\frac{n}{4},\left(1+\frac{\varepsilon}{2}\right)\frac{n}{4}\right]$

for which there exists an Hadamard matrix $V$ of size $m\times m$. Note that
$n-m$ is odd and

$n-m\in\left[\left(1-\frac{\varepsilon}{2}\right)\frac{3n}{4},\left(1+\frac{\varepsilon}{2}\right)\frac{3n}{4}\right],$

so using Vinogradov’s theorem again, we obtain a decomposition

$n-m=q_{1}+q_{2}+q_{3},$

where $q_{1},q_{2},q_{3}$ are prime numbers and $\frac{1-\varepsilon}{4}n\leq
q_{j}\leq\frac{1+\varepsilon}{4}n$. At this point we can apply the same
argument we used in the case of an even $n$ with one of the matrices
$U_{1},\ldots,U_{4}$ replaced by $V$. This completes the proof of the theorem.
∎

##  3\. Submatrices with a small condition number

In this section we prove Theorem 1.1. As was explained in the Introduction,
the proof relies on finding columns of $A$ which are close to columns of a
scaled copy of the matrix $V$ constructed in the previous section. Conditioned
on the event that such selection is possible, we prove that with high
probability, the constructed submatrix has a bounded condition number. We
start with the latter task, namely with analyzing a random matrix close to
$V$.

######  Lemma 3.1.

Let $V$ be an $n\times n$ matrix with $\pm 1$ entries such that

$c_{\ref{lem: close to V}}\sqrt{n}\leq s_{\min}(V)\leq s_{\max}(V)\leq
C_{\ref{lem: close to V}}\sqrt{n}$

for some $0<c_{\ref{lem: close to V}}\leq C_{\ref{lem: close to V}}$.

There exists $\delta\in(0,1)$ for which any $n\times n$ matrix $Y$ with i.i.d.
entries $Y_{i,j}$ such that

$\operatorname{\mathbb{E}}Y_{i,j}=0\quad\text{and }|Y_{i,j}|\leq\delta\text{
a.s.}$

satisfies

$\mathbb{P}\left(\kappa(V+Y)\leq 4\frac{C_{\ref{lem: close to
V}}}{c_{\ref{lem: close to V}}}\right)\geq 1-\exp(-cn).$

###### Proof.

The proof of Lemma 3.1 uses the basic net argument, see e.g., [22]. Since $Y$
has i.i.d. centered subgaussian entries with
$\left\|Y_{i,j}\right\|_{\psi_{2}}\leq\left\|Y_{i,j}\right\|_{\infty}\leq\delta$,

$\mathbb{P}(\left\|Y\right\|\geq C\sqrt{\delta n})\leq\exp(-cn).$

Therefore,

$\mathbb{P}(s_{\max}(V+Y)\geq 2C_{\ref{lem: close to
V}}\sqrt{n})\leq\mathbb{P}(\left\|V\right\|+\left\|Y\right\|\geq 2C_{\ref{lem:
close to V}}\sqrt{n})\leq\exp(-cn),$

as we can always assume that $C_{\ref{lem: close to V}}\geq 1$ and choose
$\delta$ sufficiently small. Similarly,

$\mathbb{P}(s_{\min}(V+Y)\leq\frac{1}{2}c_{\ref{lem: close to
V}}\sqrt{n})\leq\mathbb{P}(s_{\min}(V)-\left\|Y\right\|\leq\frac{1}{2}c_{\ref{lem:
close to V}}\sqrt{n})\leq\exp(-cn),$

where as before, the last inequality holds for any sufficiently small
$\delta$. The result follows by combining the two bounds above. ∎

We now proceed to proving the main result, Theorem 1.1.

###### Proof ot Theorem 1.1.

Since the distribution of entries of $A$ is non-degenerate, there exists $a>0$
such that for any $\nu>0$

$\mathbb{P}\left(|a_{i,j}-a|<\nu\right)>0.$

By the symmetry of distribution, we also have the same property for $-a$ in
place of $a$.

Let $\delta>0$ be as in Lemma 3.1, and denote $\nu=\frac{a}{4}\delta.$ Let $Z$
be a random variable having the same distribution as $a_{i,j}$ conditioned on
the event that $|a_{i,j}-a|\leq\nu$. More precisely, for a Borel set
$E\subset\mathbb{R}$, set

$\mathbb{P}(Z\in
E)=\frac{1}{\mathbb{P}(|a_{i,j}-a|\leq\nu)}\mathbb{P}(a_{i,j}\in E\ \&\
|a_{i,j}-a|\leq\nu).$

Set

$R=\frac{Z-\operatorname{\mathbb{E}}Z}{\operatorname{\mathbb{E}}Z}.$

Then $R$ is a centered random variable such that

$|R|\leq\frac{2\nu}{(1-\delta/4)a}\leq\delta\ \text{ a.s.}$

Let $C>0$ be a constant to be chosen later, and assume that $N\geq\exp(2Cn)$.
Partition $[N]$ into a union of sets $I_{1},\ldots,I_{n}$ such that

$|I_{j}|\geq\left\lfloor\frac{N}{n}\right\rfloor\geq\exp(Cn).$

Let $V$ be the $n\times n$ matrix with $\pm 1$ entries constructed in Theorem
1.2. Denote its columns by $V_{1},\ldots,V_{n}$ and the columns of $A$ by
$A_{1},\ldots,A_{N}$. Let $M$ be a number to be chosen later. Let
$\mathcal{E}$ be the event that for any $j\in[n]$, there exist at least $M$
numbers $k\in I_{j}$ with

$\left\|A_{k}-aV_{j}\right\|_{\infty}\leq\nu.$

If $\mathcal{E}$ occurs, denote by $k(j,1),\ldots,k(j,M)$ the first $M$
numbers $k\in I_{j}$ having this property. Then conditioned on $\mathcal{E}$,
for any $m\in[M]$, the matrix $A_{\mathcal{E},m}$ with columns
$A_{k(1,m)},\ldots,A_{k(n,m)}$ has the same distribution as
$\operatorname{\mathbb{E}}Z\cdot(V+Y)$, where $Y$ is an $n\times n$ random
matrix whose entries have the form $Y_{i,j}=V_{i,j}R_{i,j}$, where $R_{i,j}$
are independent copies of $R$. In view of Lemma 3.1, this implies that for any
$m\in[M]$,

$\mathbb{P}\left(\kappa(A_{\mathcal{E},m})\leq 4\frac{C_{\ref{lem: close to
V}}}{c_{\ref{lem: close to V}}}\mid\mathcal{E}\right)\geq 1-\exp(-cn).$

Since conditionally on $\mathcal{E}$, the matrices
$A_{\mathcal{E},1},\ldots,A_{\mathcal{E},M}$ are independent, Bernstein’s
inequality allows to conclude that

$\mathbb{P}\left(\kappa(A_{\mathcal{E},m})\leq 4\frac{C_{\ref{lem: close to
V}}}{c_{\ref{lem: close to V}}}\text{ for at least }M/2\text{ numbers
}m\in[M]\mid\mathcal{E}\right)\geq 1-\exp(-c^{\prime}M).$

To complete the proof, we have to show that the probability of
$\mathcal{E}^{c}$ is small. To this end, denote
$\eta=\mathbb{P}(|a_{i,j}-a|\leq\nu)$. Then by the symmetry of distribution of
the entries of $A$,
$\mathbb{P}(|a_{i^{\prime},j^{\prime}}-aV_{i,j}|\leq\nu)=\eta$ for any
$i^{\prime},j^{\prime}$. Let $j\in[n]$. For any $k\in I_{j}$,

$\mathbb{P}(\left\|A_{k}-aV_{j}\right\|_{\infty}\leq\nu)=\eta^{n}.$

Set

$M=\frac{N}{2}\cdot\eta^{n}=\frac{1}{2}\exp\left(Cn-\log\left(\frac{1}{\eta}\right)\cdot
n\right)\geq\exp\left(\frac{Cn}{2}\right)$

where the last inequality holds if $C=C(\eta)$ is chosen sufficiently large.
Note that the events $\left\|A_{k}-aV_{j}\right\|_{\infty}\leq\nu$ are
independent for all $k\in I_{j}$. At this point, Bernstein’s inequality yields

$\displaystyle\mathbb{P}(\left\|A_{k}-aV_{j}\right\|_{\infty}\leq\nu\text{ for
less than }M\text{ numbers }k\in I_{j})$
$\displaystyle\leq\exp(-c^{\prime\prime}M)$
$\displaystyle\leq\exp\left[-\exp\left(\frac{Cn}{4}\right)\right].$

Therefore,

$\displaystyle\mathbb{P}(\mathcal{E}^{c})$
$\displaystyle\leq\sum_{j=1}^{n}\mathbb{P}(\left\|A_{k}-aV_{j}\right\|_{\infty}\leq\nu\text{
for less than }M\text{ numbers }k\in I_{j})$ $\displaystyle\leq
n\cdot\exp\left[-\exp\left(\frac{Cn}{4}\right)\right]\leq\exp\left[-\exp\left(\frac{Cn}{8}\right)\right].$

Let $L=M/2$, and $\alpha=4\frac{C_{\ref{lem: close to V}}}{c_{\ref{lem: close
to V}}}$. Combining the previous inequalities, we obtain that

$\displaystyle\mathbb{P}\big{(}\text{\rm exist disjoint subsets
}I_{1},\ldots,I_{L}\text{\rm\ of }[N]\text{\rm\ such that }\big{.}$
$\displaystyle\qquad\big{.}|I_{j}|=n\text{\rm\ and
}\kappa(A_{I_{j}})<\alpha\text{\rm\ for all }j\in[L]\big{)}$
$\displaystyle\geq\mathbb{P}\left(\kappa(A_{\mathcal{E},m})<\alpha\text{ for
at least }M/2\text{ numbers
}m\in[M]\mid\mathcal{E}\right)\cdot(1-\mathbb{P}(\mathcal{E}^{c}))$
$\displaystyle\geq
1-\exp(-c^{\prime}M)-\exp\left[-\exp\left(\frac{Cn}{8}\right)\right]$
$\displaystyle\geq 1-\exp\left(-\exp(\beta n)\right)$

for an appropriate $\beta>0$. This completes the proof of the theorem. ∎

##  4\. No submatrices with a small condition number

In this section, we prove Theorem 1.3.

###### Proof.

Without loss of generality, we can assume that
$\left\|X\right\|_{2}=(\operatorname{\mathbb{E}}X^{2})^{1/2}=1$. Throughout
the proof, we denote by $C,c,c^{\prime}$, etc. constants depending only on
$\left\|X\right\|_{\psi_{2}}$.

Consider an $n\times n$ random matrix $B$ whose entries are independent copies
of $X$. We claim that

(4.1) $\mathbb{P}(\left\|B\right\|\leq c\sqrt{n})\leq\exp(-c^{\prime}n^{2}).$

Indeed, denoting the columns of $B$ by $B_{1},\ldots,B_{n}$, and applying the
Hanson-Wright inequality [19, Theorem 2.1], we get

$\displaystyle\mathbb{P}(\left\|B\right\|\leq\frac{1}{2}\sqrt{n})\leq\mathbb{P}(\left\|B_{j}\right\|_{2}\leq\frac{1}{2}\sqrt{n}\text{
for all }j\in[n])$
$\displaystyle\leq\left(\mathbb{P}\left[\operatorname{\mathbb{E}}\left\|B_{j}\right\|_{2}^{2}-\left\|B_{j}\right\|_{2}^{2}\geq\frac{1}{2}n\right]\right)^{n}\leq\exp(-c^{\prime}n^{2}).$

Furthermore, we assert that

(4.2) $\mathbb{P}(s_{n}(B)\geq 2\sqrt{\varepsilon
n})\leq\exp(-c^{\prime}\varepsilon^{2}n^{2})$

for any $\varepsilon>0$. Proving (4.2) relies on a standard fact from linear
algebra.

######  Lemma 4.1.

Let $M$ be an $n\times n$ matrix. Let $k<n$, and denote
$H=\operatorname*{span}(Me_{k+1},\ldots,Me_{n})$, where $e_{1},\ldots,e_{n}$
is the standard basis of $\mathbb{R}^{n}$. Then

$s_{n}(M)\leq\min_{j=1,\ldots,k}\left\|P_{H^{\perp}}Me_{j}\right\|_{2},$

where $P_{H^{\perp}}$ is the orthogonal projection on $H^{\perp}$.

###### Proof.

Without loss of generality, we can assume that the matrix $M$ is invertible.
Let $j\in[k]$. Choosing an appropriate
$u\in\operatorname*{span}(e_{k+1},\ldots,e_{n})$, we obtain

$1\leq\left\|e_{j}-u\right\|_{2}\leq\left\|M^{-1}\right\|\cdot\left\|Me_{j}-Mu\right\|_{2}=s_{n}^{-1}(M)\cdot\left\|P_{H^{\perp}}Me_{j}\right\|_{2},$

where the equality holds after optimization over $u$. The lemma follows. ∎

To prove (4.2), we apply Lemma 4.1 to $B$ setting $k=\lfloor\varepsilon
n\rfloor$. It yields

$\mathbb{P}(s_{n}(B)\geq 2\sqrt{\varepsilon
n})\leq\mathbb{P}(\left\|P_{H^{\perp}}Be_{j}\right\|_{2}\geq
2\sqrt{\varepsilon n}\text{ for all }j\in[k]).$

Conditioning on $B_{k+1},\ldots,B_{n}$, we can rewrite the right hand side ov
the above inequality as

$\displaystyle\operatorname{\mathbb{E}}\left(\mathbb{P}\big{[}\left\|P_{H^{\perp}}Be_{j}\right\|_{2}\geq
2\sqrt{\varepsilon n}\text{ for all }j\in[k]\mid
B_{k+1},\ldots,B_{n}\big{]}\right)$ $\displaystyle=$
$\displaystyle\operatorname{\mathbb{E}}\left(\mathbb{P}\big{[}\left\|P_{H^{\perp}}Be_{1}\right\|_{2}\geq
2\sqrt{\varepsilon n}\mid B_{k+1},\ldots,B_{n}\big{]}\right)^{k}$

using independence of the columns of $B$. The conditional probability can be
estimated by applying the Hanson-Wright inequality again. Applying [19,
Theorem 2.1] to the vector $B_{1}=Be_{1}$ having i.i.d. centered subgaussian
coordinates, we get

$\displaystyle\mathbb{P}\big{[}\left\|P_{H^{\perp}}Be_{1}\right\|_{2}\geq
2\sqrt{\varepsilon n}\mid B_{k+1},\ldots,B_{n}\big{]}$ $\displaystyle\leq\ $
$\displaystyle\mathbb{P}\big{[}\left\|P_{H^{\perp}}Be_{1}\right\|_{2}-\left\|P_{H^{\perp}}\right\|_{\operatorname{HS}}\geq\sqrt{\varepsilon
n}\mid B_{k+1},\ldots,B_{n}\big{]}$ $\displaystyle\leq\ $
$\displaystyle\exp(-c\varepsilon n).$

Taking the expectation with respect to $B_{k+1},\ldots,B_{n}$ and combining it
with the previous inequality completes the proof of (4.2).

Using (4.2) with $\varepsilon=t^{-2}/4$ together with (4.1), we derive

$\mathbb{P}(\kappa(B)<t)\leq\exp\left(-c^{\prime}\frac{n^{2}}{t^{4}}\right).$

The proposition follows by using this inequality for $B=A_{I}$ and taking the
union bound over $I\subset[N]$:

$\displaystyle\mathbb{P}\left(\exists I\subset[N]\ |I|=n\text{ and
}\kappa(A_{I})<t\right)$
$\displaystyle\leq\binom{N}{n}\exp\left(-c^{\prime}\frac{n^{2}}{t^{4}}\right)$
$\displaystyle\leq\exp\left(n\log\left(\frac{eN}{n}\right)-c^{\prime}\frac{n^{2}}{t^{4}}\right)$
$\displaystyle\leq\exp\left(-(c^{\prime}-\tilde{c})\frac{n^{2}}{t^{4}}\right),$

where the last inequality follows from the assumption on $N$. Setting
$\tilde{c}=c^{\prime}/2$ completes the proof. ∎

## References

  * [1] S. S. Agaian, Hadamard matrices and their applications. Lecture Notes in Mathematics, 1168. Springer-Verlag, Berlin, 1985.
  * [2] T. Banica, I. Nechita, K Życzkowski _Almost Hadamard matrices: general theory and examples,_ Open Systems & Information Dynamics 19 (2012), no.04 1250024 pp.
  * [3] R.C. Baker, G. Harman, _The three primes theorem with almost equal summands,_ Philosophical Transactions of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences 356 (1998), no. 1738, 763–780 pp.
  * [4] P. Casazza, G. Kutyniok, F.Philipp, Introduction to finite frame theory. Finite frames, 1–53, Appl. Numer. Harmon. Anal., Birkhäuser/Springer, New York, 2013.
  * [5] O. Christensen, Frames and bases. An introductory course. Applied and Numerical Harmonic Analysis. Birkhäuser Boston, Inc., Boston, MA, 2008.
  * [6] O. Christensen, An introduction to frames and Riesz bases. Second edition. Applied and Numerical Harmonic Analysis. Birkhäuser/Springer, 2016.
  * [7] R. Craigen, _Signed groups, sequences, and the asymptotic existence of Hadamard matrices,_ Journal of Combinatorial Theory, Series A 71 (1995), no.2 241–254 pp.
  * [8] H. Davenport, Multiplicative number theory. Second edition. Revised by Hugh L. Montgomery. Graduate Texts in Mathematics, 74. Springer-Verlag, New York-Berlin, 1980.
  * [9] P. J. Davis, Circulant matrices. A Wiley-Interscience Publication. Pure and Applied Mathematics. John Wiley & Sons, New York-Chichester-Brisbane, 1979.
  * [10] W. de Launey, _On the asymptotic existence of Hadamard matrices,_ Journal of Combinatorial Theory, Series A 116 (2009), no.4 1002–1008.
  * [11] C. B. Haselgrove, _Some theorems in the analytic theory of numbers_ , J. London Math. Soc. 26 (1951), 273–277.
  * [12] K. J. Horadam, Hadamard matrices and their applications. Princeton University Press, Princeton, NJ, 2007.
  * [13] K. Ireland, M. Rosen, A classical introduction to modern number theory. Second edition. Graduate Texts in Mathematics, 84. Springer-Verlag, New York, 1990.
  * [14] Ph. Jaming, M. Matolcsi, _On the existence of flat orthogonal matrices,_ Acta Math. Hungar. 147 (2015), no. 1, 179–188.
  * [15] P. Ki-Hyeon, H. Song, _Quasi-hadamard matrix,_ 2010 IEEE International Symposium on Information Theory (2020), 1243–1247 pp.
  * [16] M. Matolcsi, I. Z. Ruzsa, _Difference sets and positive exponential sums I. General properties,_ J. Fourier Anal. Appl. 20 (2014), no. 1, 17–41.
  * [17] K. Matomäki, J. Maynard, X. Shao, _Vinogradov’s theorem with almost equal summands,_ Proceedings of the London Mathematical Society 115 (2017), no. 2, 323–347 pp.
  * [18] M. B. Nathanson, Additive number theory. The classical bases. Graduate Texts in Mathematics, 164. Springer-Verlag, New York, 1996.
  * [19] M. Rudelson, R. Vershynin, _Hanson-Wright inequality and sub-Gaussian concentration,_ Electron. Commun. Probab. 18 (2013), no. 82, 9 pp.
  * [20] J. Sylvester, _LX. Thoughts on inverse orthogonal matrices, simultaneous sign successions, and tessellated pavements in two or more colours, with applications to Newton’s rule, ornamental tile-work, and the theory of numbers.,_ The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science 34 (1867), no.232 461–475 pp.
  * [21] R. Vershynin, Estimation in high dimensions: a geometric perspective. Sampling theory, a renaissance, 3–66, Appl. Numer. Harmon. Anal., Birkhäuser/Springer, 2015.
  * [22] R. Vershynin, High-dimensional probability. An introduction with applications in data science. With a foreword by Sara van de Geer. Cambridge Series in Statistical and Probabilistic Mathematics, 47. Cambridge University Press, Cambridge, 2018.
  * [23] J.S.Wallis, _On the existence of Hadamard matrices,_ J. Combinatorial Theory Ser. A 21 (1976), no. 2, 188–195.