# Polynomial-Time Algorithms for Weaver’s Discrepancy Problem
in a Dense Regime

Ben Jourdan111School of Informatics, University of Edinburgh, UK.
<EMAIL_ADDRESS>Peter Macgregor222School of Informatics, University of
Edinburgh, UK<EMAIL_ADDRESS> He Sun333School of Informatics,
University of Edinburgh, UK<EMAIL_ADDRESS>
###### Abstract

Given $v_{1},\ldots,v_{m}\in\mathbb{C}^{d}$ with $\|v_{i}\|^{2}=\alpha$ for
all $i\in[m]$ as input and suppose $\sum_{i=1}^{m}|\langle
u,v_{i}\rangle|^{2}=1$ for every unit vector $u\in\mathbb{C}^{d}$, Weaver’s
discrepancy problem asks for a partition $S_{1},S_{2}$ of $[m]$, such that
$\sum_{i\in S_{j}}|\langle u,v_{i}\rangle|^{2}\leq 1-\theta$ for some
universal constant $\theta$, every unit vector $u\in\mathbb{C}^{d}$ and every
$j\in\\{1,2\\}$. We prove that this problem can be solved deterministically in
polynomial time when $m\geq 49d^{2}$.

##  1 Introduction

The Kadison-Singer problem is a central problem in operator theory, and has
close connections to a number of problems in quantum mechanics, pure and
applied mathematics, engineering, and computer science. Among several
formulations of the Kadison-Singer problem, Weaver [Wea04] shows that it is
equivalent to the following discrepancy problem (the $\mathsf{KS}_{2}$
problem): there exists a universal constant $\theta>0$ such that the following
holds. Let $v_{1},\ldots,v_{m}\in\mathbb{C}^{d}$ satisfy
$\|v_{i}\|^{2}=\alpha$ for all $i\in[m]$, and suppose $\sum_{i=1}^{m}|\langle
u,v_{i}\rangle|^{2}=1$ for every unit vector $u\in\mathbb{C}^{d}$. Then, there
exists a partition $S_{1},S_{2}$ of $[m]$, such that $\sum_{i\in
S_{j}}|\langle u,v_{i}\rangle|^{2}\leq 1-\theta$ for every unit vector
$u\in\mathbb{C}^{d}$ and every $j\in\\{1,2\\}$.

In their breakthrough result, Marcus, Spielman, and Srivastava [MSS15] present
a non-constructive proof and show that the partition promised by the
$\mathsf{KS}_{2}$ problem exists, leading to an affirmative answer to the
Kadison-Singer problem. On the other side, due to a close connection between
the $\mathsf{KS}_{2}$ problem and many algorithmic problems (e.g.,
constructing unweighted spectral sparsifiers, and spectrally thin trees), they
ask whether such a partition of the $\mathsf{KS}_{2}$ problem can be found in
polynomial time. After a decade-long research (e.g., [AGSS18, JMS23, SZ22]),
this problem remains wide open and has become a very important open problem in
algorithmic spectral graph theory.

This paper studies the $\mathsf{KS}_{2}$ problem in the regime of $m\geq
221d^{2}$. Under this condition, we present two deterministic polynomial-time
algorithms that solve the $\mathsf{KS}_{2}$ problem. These two algorithms
achieve the same approximation guarantee, and their performance is summarised
as follows:

######  Theorem 1.

Let $\mathcal{I}=\\{v_{i}\\}_{i=1}^{m}$ be vectors in $\mathbb{C}^{d}$, such
that $m$ is even and $\sum_{i=1}^{m}|\langle u,v_{i}\rangle|^{2}=1$ for every
unit vector $u\in\mathbb{C}^{d}$. Moreover, assume that $\|v_{i}\|^{2}=\alpha$
for every $i\in[m]$ and $m\geq 221d^{2}$. Then, there is a deterministic
algorithm that finds a partition $S_{1},S_{2}$ of $[m]$ such that
$|S_{1}|=|S_{2}|$ and

$\sum_{i\in S_{j}}|\langle u,v_{i}\rangle|^{2}\leq\frac{3}{4}$

for every unit vector $u\in\mathbb{C}^{d}$ and every $j\in\\{1,2\\}$. The
algorithm runs in time $O(\mathrm{poly}\\!\left(m,d\right))$.

######  Remark 1.

Our second algorithm requires $m\geq 49d^{2}$ instead. Both constants might be
further optimised.

######  Remark 2.

Our presented algorithms can be easily adjusted to work when $m$ is odd. In
this case, $|S_{1}|\neq|S_{2}|$ but the other stated properties from Theorem 1
hold.

We discuss the significance of the result. First of all, our result shows
that, when $m\geq 49d^{2}$, the $\mathsf{KS}_{2}$ problem can be solved by a
deterministic and polynomial-time algorithm. To the best of our knowledge,
this presents the first such algorithm which does not rely on random sampling
and de-randomization techniques [WX08]. Secondly, our work draws a novel
connection between the $\mathsf{KS}_{2}$ problem and the determinant
optimisation problem, and demonstrates how potential functions can be used for
the $\mathsf{KS}_{2}$ problem. Potential functions of various forms are common
tools used in constructing spectral sparsifiers [BSS12, LS17, LS18]; however,
all of the previous works (i) might choose the same vector multiple times, and
(ii) need to reweight the chosen vector. Hence, the previous analyses cannot
be directly applied for the $\mathsf{KS}_{2}$ problem. In our point of view,
overcoming these two “bottlenecks” is significant, and our presented technique
could motivate more research on this important problem.

###  1.1 Overview of our Techniques

#### The First Algorithm.

At a very high level, our algorithm proceeds in $m/2$ iterations, and picks
one vector in each iteration. Formally, starting with
$A_{0}=\mathbf{0}_{d\times d}$ and $\mathcal{A}_{0}=\emptyset$, the algorithm
picks some vector $v\in\mathcal{I}\setminus\mathcal{A}_{j}$ in iteration $j$,
and adds it into $\mathcal{A}_{j+1}$, i.e.,
$\mathcal{A}_{j+1}\triangleq\mathcal{A}_{j}\bigcup\\{v\\}$; the algorithm also
sets $A_{j+1}=A_{j}+vv^{*}$. Despite the similarity, it is important to notice
the difference between our framework and the BSS one [BSS12]: first of all, in
each iteration our algorithm only picks a vector that hasn’t been chosen yet,
while the BSS algorithm might pick the same vector multiple times. Secondly,
our algorithm doesn’t scale the chosen vector, while the BSS algorithm scales
the chosen vector in each iteration. Hence, during the execution of our
algorithm, the set of the chosen vectors and the set of the remaining ones
always form a partition of $\mathcal{I}$.

The analysis of our algorithm is based on a novel potential function defined
by

$\Phi^{u}(A)\triangleq\mathrm{tr}\log(u\mathbb{I}-A)^{-1}$

for some positive semi-definite matrix $A$ and barrier value
$u\in\mathbb{R}^{+}$. Since $\mathrm{tr}\log(A)=\log\det(A)$ holds for any
positive definite matrix $A$, one can rewrite $\Phi^{u}(A)$ as

$\Phi^{u}(A)=-\log\det(u\mathbb{I}-A)=-\log\left(\prod_{i=1}^{d}\lambda_{i}(u\mathbb{I}-A)\right),$
(1)

i.e., the potential function $\Phi^{u}(A)$ is a function of the determinant of
the matrix $u\mathbb{I}-A$. Our objective is to apply this potential function
to keep track of the algorithm’s progress in each iteration. To achieve this,
we set the initial barrier value as $u_{0}\triangleq 1/2$, which increases by
$\delta_{u}$ after each iteration. That is, $u_{j+1}\triangleq
u_{j}+\delta_{u}$, and we set $\delta_{u}\triangleq\alpha/d$.

Next, we reason about the use of $\Phi^{u}(A)$ and our choices of the barrier
values. As we set $\delta_{u}=\alpha/d$, it holds that

$\mathrm{tr}(u_{j}\mathbb{I}-A_{j})=\left(u_{0}+\frac{\alpha}{d}\cdot
j\right)\cdot d-\alpha\cdot j=\mathrm{tr}(u_{0}\cdot\mathbb{I}),$ (2)

hence the trace of $u_{j}\mathbb{I}-A_{j}$ remains constant during the
execution of the algorithm. On the other side, by the AM-GM inequality we have
that

$\det\left(u_{j}\mathbb{I}-A_{j}\right)^{1/d}\leq\frac{1}{d}\cdot\mathrm{tr}\left(u_{j}\mathbb{I}-A_{j}\right).$
(3)

Combining (2) with (3), we know that the potential function
$\Phi^{u_{j}}(A_{j})$ has the same upper bound for all the iterations;
moreover, the closer $\Phi^{u_{j}}(A_{j})$ is to this upper bound, the more
balanced are the eigenvalues of $u_{j}\mathbb{I}-A_{j}$. Hence, in every
iteration $j$ the algorithm picks the vector
$v\in\mathcal{I}\setminus\mathcal{A}_{j}$ that maximises
$\det\left(u_{j+1}I-A_{j}-vv^{*}\right)$. We show that after $m/2$ iterations
the left and right sides of (3) are sufficiently close. Due to a tight bound
of the condition number of any Hermitian positive definite matrix
$B\in\mathbb{C}^{d\times d}$ based on $\det(B)$, $\mathrm{tr}(B)$ and $d$
[MUV+97], we show that the algorithm finds the partition promised by the
$\mathsf{KS}_{2}$ problem.

#### The Second Algorithm.

Our second algorithm proceeds in $m/2$ iterations as well, and picks one
vector in each iteration. Formally, starting with $A_{0}=\mathbf{0}_{d\times
d}$ and $\mathcal{A}_{0}=\emptyset$, the algorithm picks some vector
$v\in\mathcal{I}\setminus\mathcal{A}_{j}$ in iteration $j$, and adds it into
$\mathcal{A}_{j+1}$; the algorithm sets $A_{j+1}=A_{j}+vv^{*}$. However, in
each iteration $j$ the algorithm picks $v$ that minimises
$v^{*}(\mathbb{I}-A_{j})^{-1}v$. Instead of applying a potential function, we
analyse the second algorithm by directly lower bounding
$\det(\mathbb{I}-A_{m/2})$. We prove that such a lower bound of
$\det(\mathbb{I}-A_{m/2})$ is sufficient to bound the condition number of
$A_{m/2}$ and $\mathbb{I}-A_{m/2}$, implying that our algorithm’s output is
the partition promised by the $\mathsf{KS}_{2}$ problem.

###  1.2 Related Work

Our result directly relates to the quest for efficient algorithms for the the
$\mathsf{KS}_{2}$ problem. Anari et al. [AGSS18] show that a valid partition
promised by the $\mathsf{KS}_{2}$ problem can be found in
$d^{O(m^{1/3}\alpha^{-1/4})}$ time. Jourdan et al. [JMS23] present a
randomised algorithm for the problem, which runs in time quasi-polynomial in
$m$ and exponential in $d$. Compared with their results, we show that the
$\mathsf{KS}_{2}$ problem can be solved in polynomial time when $m\geq
49d^{2}$. Weaver [Wea13] gives a polynomial-time algorithm for a one-sided
version of the $\mathsf{KS}_{2}$ problem based on the BSS framework for
spectral sparsification [BSS12]. In comparison, we give a two-sided guarantee
in a more restricted setting.

Our work is also linked to hardness results for the $\mathsf{KS}_{2}$ problem
[SZ22, JMS23]. These results show that the optimisation version of the
$\mathsf{KS}_{2}$ problem is $\mathsf{NP}$-hard. It’s worth mentioning that
the two reductions shown in [SZ22, JMS23] are based on instances satisfying
$m=\Theta(d)$.

Our approach further relates to the determinant maximisation problem which has
been extensively studied in the field of experimental design [BLP+22, BLS24,
SX18]. Compared with the state-of-the-art determinant maximisation algorithm,
our approach can be applied to a wider range of instances. We further discuss
this connection in Section 4.

##  2 Preliminaries

Let $\mathcal{I}\triangleq\\{v_{1},\dots,v_{m}\\}$ be the set of input
vectors, where $\|v_{i}\|^{2}=\alpha$ and $v_{i}\in\mathbb{C}^{d}$ for every
$1\leq i\leq m$. We use $\mathcal{A}_{j}$ to represent the set of vectors
picked till the $j$th iteration, and let
$\mathcal{B}_{j}\triangleq\mathcal{I}\setminus\mathcal{A}_{j}$ be the set of
unpicked vectors; hence, it holds that $|\mathcal{A}_{j}|=j$ and
$|\mathcal{B}_{j}|=m-j$. We always use $A_{j}$ to represent the matrix
constructed in the $j$th iteration, i.e.,
$A_{j}\triangleq\sum_{v\in\mathcal{A}_{j}}vv^{*}$. We write the eigenvalues of
any Hermitian matrix $A\in\mathbb{C}^{d\times d}$ as
$\lambda_{\max}(A)=\lambda_{1}(A)\geq\ldots\geq\lambda_{d}(A)=\lambda_{\min}(A)$,
and the condition number of $A$ as

$\kappa(A)\triangleq\frac{\lambda_{1}(A)}{\lambda_{d}(A)}.$

The following relationship between $\alpha,d$ and $m$ will be repeatedly used
in our analyses.

######  Lemma 2.1.

It holds that $m\cdot\alpha=d$.

###### Proof.

Let $e_{1},\ldots,e_{d}$ be the vectors forming the standard orthonormal
basis, and we have that

$m\cdot\alpha=\sum_{i=1}^{m}\|v_{i}\|^{2}=\sum_{i=1}^{m}\sum_{j=1}^{d}\langle
v_{i},e_{j}\rangle^{2}=\sum_{j=1}^{d}\sum_{i=1}^{m}\langle
v_{i},e_{j}\rangle^{2}=d,$

which proves the statement. ∎

Next we list the facts on matrices that will be used in our analyses.

######  Lemma 2.2 (Theorem 3.30, [NS18]).

It holds for any square matrices $A,B$ of the same size that
$\det(AB)=\det(A)\cdot\det(B)$.

######  Lemma 2.3.

It holds for any Hermitian positive definite matrix $A\in\mathbb{C}^{d\times
d}$ that

$\det(A)^{1/d}\leq\frac{1}{d}\cdot\mathrm{tr}(A).$

###### Proof.

Since we can write $\det(A)=\prod_{i=1}^{d}\lambda_{i}(A)$ and
$\mathrm{tr}(A)=\sum_{i=1}^{d}\lambda_{i}(A)$, the statement holds by the AM-
GM inequality. ∎

######  Lemma 2.4 (Matrix Determinant Lemma, [DZ07]).

If $A$ is an invertible matrix and $u,v$ are vectors, then

$\det\left(A+uv^{*}\right)=\left(1+v^{*}A^{-1}u\right)\cdot\det(A).$

######  Lemma 2.5.

Let $A,B$ be positive definite matrices. Then, the following statements hold:

  1. 1.

$\mathrm{tr}\log(A)=\log\det(A)$;

  2. 2.

$\mathrm{tr}\log(AB)=\mathrm{tr}\log(A)+\mathrm{tr}\log(B)$;

  3. 3.

if $A$ and $B$ commute, then $\log(AB)=\log(A)+\log(B)$;

  4. 4.

$\log(A^{-1})=-\log(A)$.

###### Proof.

Let $\lambda_{1}\geq\dots\geq\lambda_{d}>0$ be the eigenvalues of $A$. Then,
we have that

$\mathrm{tr}\log(A)=\sum_{i=1}^{d}\log(\lambda_{i})=\log\left(\prod_{i=1}^{d}\lambda_{i}\right)=\log(\det(A)),$

which proves the first statement. By the first statement and Lemma 2.2, we
have that

$\mathrm{tr}\log(AB)=\log(\det(AB))=\log\det(A)+\log\det(B)=\mathrm{tr}\log(A)+\mathrm{tr}\log(B),$

hence the second statement holds. The proofs of the third and fourth
statements can be found in Theorems 11.2 and 11.3 of Chapter 11 of [Hig08]. ∎

######  Lemma 2.6 ([MUV+97]).

Let $A\in\mathbb{C}^{d\times d}$ be a Hermitian positive definite matrix.
Then, the condition number $\kappa(A)$ of $A$ satisfies that

$\kappa(A)\leq\frac{1+x}{1-x},\qquad
x\triangleq\sqrt{1-\left(\frac{d}{\mathrm{tr}(A)}\right)^{d}\cdot\det(A)}.$

##  3 The First Algorithm and Analysis

This section presents and analyses our first algorithm, and is organised as
follows. Section 3.1 gives the formal description of our first algorithm,
whose correctness is analysed in Section 3.2; Section 3.3 proves a key lemma
used in our analysis.

###  3.1 Algorithm Description

Our designed algorithm proceeds in $m/2$ iterations, and picks one vector in
each iteration. At the initialisation step, the algorithm sets

$A_{0}=\mathbf{0}_{d\times
d},\quad\mathcal{A}_{0}=\emptyset,\quad\mathcal{B}_{0}=\mathcal{I},$

and $u_{0}=1/2,\delta_{u}=\alpha/d$. Then, in iteration $0\leq j<m/2$, the
algorithm selects a vector $v\in\mathcal{B}_{j}$ and performs the following
operations:

$A_{j+1}=A_{j}+vv^{*},\qquad\mathcal{A}_{j+1}=\mathcal{A}_{j}\cup\\{v\\},\qquad\mathcal{B}_{j+1}=\mathcal{B}_{j}\setminus\\{v\\}.$

The vector $v$ is chosen such that the increase of the potential function from
$\Phi^{u_{j}}(A_{j})$ to $\Phi^{u_{j}+\delta_{u}}(A_{j}+vv^{*})$ is minimised.
That is, the algorithm picks $v$ that minimises the function

$\Phi^{u_{j}+\delta_{u}}(A_{j}+vv^{*})=-\log\Big{(}\det((u_{j}+\delta_{u})\cdot\mathbb{I}-A_{j}-vv^{*})\Big{)}.$

After this, the algorithm sets $u_{j+1}=u_{j}+\delta_{u}$, and moves to the
next iteration. See Algorithm 1 for formal description.

1 Input: $\mathcal{I}=\\{v_{i}\\}_{i=1}^{m}$, where $v_{i}\in\mathbb{C}^{d}$
and $\left\|v_{i}\right\|^{2}=\alpha$

2 $A_{0}\leftarrow\mathbf{0}_{d\times d}$,
$\mathcal{A}_{0}\leftarrow\emptyset$

3 $\mathcal{B}_{0}\leftarrow\mathcal{I}$

4

5$u_{0}\leftarrow 1/2$

6 $\delta_{u}\leftarrow\alpha/d$

7 $j\leftarrow 0$

8 while  _$j <m/2$_ do

9 $u_{j+1}\leftarrow u_{j}+\delta_{u}$

10
$v_{j}\leftarrow\operatorname*{arg\,max}_{v\in\mathcal{B}_{j}}\det(u_{j+1}\mathbb{I}-A_{j}-vv^{*})$

11 $A_{j+1}\leftarrow A_{j}+v_{j}v_{j}^{*}$

12 $\mathcal{A}_{j+1}\leftarrow\mathcal{A}_{j}\cup\\{v_{j}\\}$

13 $\mathcal{B}_{j+1}\leftarrow\mathcal{B}_{j}\setminus\\{v_{j}\\}$

14 $j\leftarrow j+1$

15 end while

return $\mathcal{A}_{m/2}$

Algorithm 1

###  3.2 Proof of Theorem 1

We introduce $c_{j}\triangleq u_{j}-\lambda_{\max}(A_{j})$, which is the
difference between $u_{j}$ and the maximum eigenvalue of $A_{j}$ constructed
by the algorithm in iteration $j$. Recall that Theorem 1 assumes that $m\geq
221d^{2}$, which is equivalent to

$\alpha\leq\frac{1}{221d};$

we assume that this holds throughout the rest of the section. We first claim
that the constructed $A_{j}$ in every iteration satisfies the following:

  1. 1.

the maximum eigenvalue $\lambda_{\max}(A_{j})$ is _far away_ from $u_{j}$ in
every iteration;

  2. 2.

the condition number $\kappa(u_{j}\mathbb{I}-A_{j})$ is at most $3/2$ in every
iteration.

These facts are summarised in Lemma 3.1, which will be proven in the next
subsection.

######  Lemma 3.1.

It holds for every $0\leq j\leq m/2$ that $c_{j}\geq 1/3$ and
$\kappa(u_{j}\mathbb{I}-A_{j})\leq 3/2$.

Lemma 3.1 is sufficient to prove Theorem 1.

###### Proof of Theorem 1.

After $m/2$ iterations of Algorithm 1 we have

$u_{m/2}=u_{0}+\frac{m}{2}\cdot\delta_{u}=\frac{1}{2}+\frac{m}{2}\cdot\frac{\alpha}{d}=1,$

using the fact $d=m\alpha$ (Lemma 2.1). By Lemma 3.1, we have that
$\lambda_{\mathrm{max}}(A_{m/2})\leq 2/3$ and $\kappa(\mathbb{I}-A_{m/2})\leq
3/2$. This implies that

$\lambda_{\mathrm{max}}(\mathbb{I}-A_{m/2})\leq\frac{3}{2}\cdot\lambda_{\mathrm{min}}(\mathbb{I}-A_{m/2}),$

which is equivalent to

$1-\lambda_{\mathrm{min}}(A_{m/2})\leq\frac{3}{2}\cdot(1-\lambda_{\mathrm{max}}(A_{m/2})).$

Combining this with the fact that

$\lambda_{\mathrm{max}}(A_{m/2})\geq\frac{1}{d}\cdot\mathrm{tr}(A_{m/2})=\frac{1}{d}\cdot\frac{\alpha
m}{2}=\frac{1}{2}$

gives us that $\lambda_{\mathrm{min}}(A_{m/2})\geq 1/4$. The algorithm
performs $O(m)$ iterations, each of which consists of elementary matrix
operations, and $O(m)$ determinant computations, each of which has running
time $O(d^{3})$. Thus, the running time of the algorithm is
$O(\mathrm{poly}(m,d))$. ∎

###  3.3 Proof of Lemma 3.1

This subsection analyses the average change of the potential function
$\Phi^{u_{j}}(A_{j})$ in each iteration, and proves by induction that Lemma
3.1 holds for every iteration. We first assume that Lemma 3.1 holds for any
iteration $j^{\prime}\leq j$ for some fixed $j$, and only study the $j$th
iteration of Algorithm 1. For simplicity, we write

$A=A_{j},\quad
B=B_{j},\quad\mathcal{A}=\mathcal{A}_{j},\quad\mathcal{B}=\mathcal{B}_{j},$

as well as $u=u_{j}$ and $\widehat{u}=u_{j+1}=u_{j}+\delta_{u}$.

######  Lemma 3.2.

Assuming Lemma 3.1 holds up to iteration $j$, we have for the constructed
matrix $A=A_{j}$ that

$\displaystyle\sum_{v\in\mathcal{B}}\Phi^{u}(A)-\Phi^{\widehat{u}}(A+vv^{*})$
$\displaystyle=(m-j)\cdot\mathrm{tr}\left[\log\Big{(}(u\mathbb{I}-A)^{-1}(\widehat{u}\mathbb{I}-A)\Big{)}\right]+\sum_{v\in\mathcal{B}}\log\Big{(}1-v^{*}(\widehat{u}\mathbb{I}-A)^{-1}v\Big{)}.$
(4)

###### Proof.

By Lemma 3.1 we have that
$\lambda_{\min}(u\mathbb{I}-A)=u-\lambda_{\max}(A)\geq 1/3>0$ and

$\lambda_{\min}(u\mathbb{I}-A-vv^{*})\geq\lambda_{\min}(u\mathbb{I}-A-\alpha\mathbb{I})\geq\frac{1}{3}-\alpha\geq\frac{1}{3}-\frac{1}{221d}>0;$

as such both of $(u\mathbb{I}-A)$ and $(\widehat{u}\mathbb{I}-A-vv^{*})$ are
invertible. Hence, it holds for any matrix $A$ and vector $v\in\mathbb{R}^{d}$
that

$\displaystyle\Phi^{u}(A)-\Phi^{\widehat{u}}(A+vv^{*})$
$\displaystyle=\mathrm{tr}\Big{[}\log\Big{(}(u\mathbb{I}-A)^{-1}\Big{)}-\log\Big{(}(\widehat{u}\mathbb{I}-(A+vv^{*}))^{-1}\Big{)}\Big{]}$
$\displaystyle=\mathrm{tr}\Big{[}\log\Big{(}(u\mathbb{I}-A)^{-1}\Big{)}+\log\Big{(}\widehat{u}\mathbb{I}-(A+vv^{*})\Big{)}\Big{]}$
$\displaystyle=\mathrm{tr}\Big{[}\log\Big{(}(u\mathbb{I}-A)^{-1}(\widehat{u}\mathbb{I}-(A+vv^{*}))\Big{)}\Big{]},$

where we apply the definition of $\Phi^{u}(A)$ and Lemma 2.5. Thus,

$\displaystyle\sum_{v\in\mathcal{B}}\Phi^{u}(A)-\Phi^{\widehat{u}}(A+vv^{*})$
$\displaystyle=\sum_{v\in\mathcal{B}}\mathrm{tr}\Big{[}\log\Big{(}(u\mathbb{I}-A)^{-1}(\widehat{u}\mathbb{I}-(A+vv^{*}))\Big{)}\Big{]}$
$\displaystyle=\sum_{v\in\mathcal{B}}\log\Big{[}\det\Big{(}(u\mathbb{I}-A)^{-1}(\widehat{u}\mathbb{I}-(A+vv^{*}))\Big{)}\Big{]}$
$\displaystyle=\log\left[\prod_{v\in\mathcal{B}}\det\Big{(}(u\mathbb{I}-A)^{-1}(\widehat{u}\mathbb{I}-(A+vv^{*}))\Big{)}\right]$
$\displaystyle=\log\left[\prod_{v\in\mathcal{B}}\det\Big{(}(u\mathbb{I}-A)^{-1}\Big{)}\det\Big{(}\widehat{u}\mathbb{I}-(A+vv^{*})\Big{)}\right]$
(5)
$\displaystyle=\log\left[\det\Big{(}(u\mathbb{I}-A)^{-1}\Big{)}^{m-j}\prod_{v\in\mathcal{B}}\det\Big{(}\widehat{u}\mathbb{I}-(A+vv^{*})\Big{)}\right]$
$\displaystyle=\log\left[\det\Big{(}(u\mathbb{I}-A)^{-1}\Big{)}^{m-j}\prod_{v\in\mathcal{B}}\det(\widehat{u}\mathbb{I}-A)(1-v^{*}(\widehat{u}\mathbb{I}-A)^{-1}v)\right]$
(6)
$\displaystyle=\log\left[\det\Big{(}(u\mathbb{I}-A)^{-1}\Big{)}^{m-j}\det(\widehat{u}\mathbb{I}-A)^{m-j}\prod_{v\in\mathcal{B}}(1-v^{*}(\widehat{u}\mathbb{I}-A)^{-1}v)\right]$
$\displaystyle=\log\left[\det\Big{(}\Big{(}(u\mathbb{I}-A)^{-1}(\widehat{u}\mathbb{I}-A)\Big{)}^{m-j}\Big{)}\prod_{v\in\mathcal{B}}(1-v^{*}(\widehat{u}\mathbb{I}-A)^{-1}v)\right]$
(7)
$\displaystyle=\log\left[\det\Big{(}\Big{(}u\mathbb{I}-A)^{-1}(\widehat{u}\mathbb{I}-A)\Big{)}^{m-j}\Big{)}\right]+\log\left[\prod_{v\in\mathcal{B}}(1-v^{*}(\widehat{u}\mathbb{I}-A)^{-1}v)\right]$
$\displaystyle=\mathrm{tr}\left[\log\Big{(}(u\mathbb{I}-A)^{-1}(\widehat{u}\mathbb{I}-A)\Big{)}^{m-j}\right]+\sum_{v\in\mathcal{B}}\log\Big{(}1-v^{*}(\widehat{u}\mathbb{I}-A)^{-1}v\Big{)}$
$\displaystyle=(m-j)\cdot\mathrm{tr}\left[\log\Big{(}(u\mathbb{I}-A)^{-1}(\widehat{u}\mathbb{I}-A)\Big{)}\right]+\sum_{v\in\mathcal{B}}\log\Big{(}1-v^{*}(\widehat{u}\mathbb{I}-A)^{-1}v\Big{)},$

where (5) and (7) follow by Lemma 2.2, and (6) follows by Matrix Determinant
Lemma (Lemma 2.4). This completes the proof. ∎

We examine the second term in (4), which involves the set of all the unpicked
vectors $v\in\mathcal{B}$. The following lemma derives a “universal” lower
bound of this term, in the sense that this bound is only a function of $A$
instead of individual vectors in $\mathcal{B}$.

######  Lemma 3.3.

Assuming Lemma 3.1 holds up to iteration $j$, we have for the constructed
$A=A_{j}$ that

$\sum_{v\in\mathcal{B}}\log\Big{(}1-v^{*}(\widehat{u}\mathbb{I}-A)^{-1}v\Big{)}\geq\frac{1}{\alpha}\cdot\mathrm{tr}\left[(\mathbb{I}-A)\cdot\log\Big{(}\mathbb{I}-\alpha(\widehat{u}\mathbb{I}-A)^{-1}\Big{)}\right].$

###### Proof.

By Lemma 3.1 we have that

$v^{*}(\widehat{u}\mathbb{I}-A)^{-1}v\leq\alpha\lambda_{\max}((\widehat{u}\mathbb{I}-A)^{-1})=\frac{\alpha}{\lambda_{\min}(\widehat{u}\mathbb{I}-A)}=\frac{\alpha}{\delta_{u}+(u-\lambda_{\max}(A))}\leq\frac{\alpha}{\delta_{u}+1/3}\leq
3\alpha<1.$

Hence, we can apply the scalar and matrix Maclaurin series of
$\log\left(1-x\right)$ and have that

$\displaystyle\sum_{v\in\mathcal{B}}\log\Big{(}1-v^{*}(\widehat{u}\mathbb{I}-A)^{-1}v\Big{)}$
$\displaystyle=-\sum_{v\in\mathcal{B}}\sum_{k=1}^{\infty}\frac{\Big{(}v^{*}(\widehat{u}\mathbb{I}-A)^{-1}v\Big{)}^{k}}{k}$
$\displaystyle=-\sum_{v\in\mathcal{B}}\sum_{k=1}^{\infty}\frac{\mathrm{tr}\Big{[}\Big{(}(\widehat{u}\mathbb{I}-A)^{-1}vv^{*}\Big{)}^{k}\Big{]}}{k}$
$\displaystyle\geq-\sum_{v\in\mathcal{B}}\sum_{k=1}^{\infty}\frac{\mathrm{tr}\Big{[}(\widehat{u}\mathbb{I}-A)^{-k}(vv^{*})^{k}\Big{]}}{k}$
(8)
$\displaystyle=-\sum_{k=1}^{\infty}\sum_{v\in\mathcal{B}}\frac{\mathrm{tr}\Big{[}(\widehat{u}\mathbb{I}-A)^{-k}(vv^{*})^{k}\Big{]}}{k}$
$\displaystyle=-\sum_{k=1}^{\infty}\sum_{v\in\mathcal{B}}\frac{\mathrm{tr}\Big{[}\alpha^{k-1}(\widehat{u}\mathbb{I}-A)^{-k}(vv^{*})\Big{]}}{k}$
(9)
$\displaystyle=-\sum_{k=1}^{\infty}\frac{\mathrm{tr}\Big{[}\alpha^{k-1}(\widehat{u}\mathbb{I}-A)^{-k}\sum_{v\in\mathcal{B}}(vv^{*})\Big{]}}{k}$
$\displaystyle=-\sum_{k=1}^{\infty}\frac{\mathrm{tr}\Big{[}\alpha^{k-1}(\widehat{u}\mathbb{I}-A)^{-k}(\mathbb{I}-A)\Big{]}}{k}$
$\displaystyle=-\sum_{k=1}^{\infty}\frac{\mathrm{tr}\Big{[}\frac{1}{\alpha}\Big{(}\frac{1}{\alpha}(\widehat{u}\mathbb{I}-A)\Big{)}^{-k}(\mathbb{I}-A)\Big{]}}{k}$
$\displaystyle=\frac{1}{\alpha}\cdot\mathrm{tr}\left[-\sum_{k=1}^{\infty}\frac{\Big{(}\alpha(\widehat{u}\mathbb{I}-A)^{-1}\Big{)}^{k}}{k}\cdot(\mathbb{I}-A)\right]$
$\displaystyle=\frac{1}{\alpha}\mathrm{tr}\left[(\mathbb{I}-A)\cdot\log\Big{(}\mathbb{I}-\alpha(\widehat{u}\mathbb{I}-A)^{-1}\Big{)}\right],$

where (8) holds by the fact that
$\mathrm{tr}((XY)^{k})\leq\mathrm{tr}(X^{k}Y^{k})$ holds for PSD matrices
$X,Y$ and $k\in\mathbb{Z}^{+}$, and (9) holds by the fact that
$\|v\|^{2}=\alpha$ for every $v\in B$. ∎

Next we apply Chebyshev’s sum inequality to replace the factor of
$(\mathbb{I}-A)$ in the lower bound given in Lemma 3.3 with the scalar
$(m-j)/m$.

######  Lemma 3.4 (Chebyshev’s Sum Inequality).

Let $f(x):\mathbb{R}\xrightarrow{}\mathbb{R}$ and
$g(x):\mathbb{R}\xrightarrow[]{}\mathbb{R}$ be both monotone increasing (or
both monotone decreasing) functions on $x$. Then, it holds for
$S\subset\mathbb{R}$ that

$\sum_{x\in S}g(x)f(x)\geq\frac{1}{\left\lvert S\right\rvert}\left(\sum_{x\in
S}g(x)\right)\left(\sum_{x\in S}f(x)\right).$

######  Lemma 3.5.

Assuming Lemma 3.1 holds up to iteration $j$, we have for the constructed
$A=A_{j}$ that

$\displaystyle\sum_{v\in\mathcal{B}}\Phi^{u}(A)-\Phi^{\widehat{u}}(A+vv^{*})$
$\displaystyle\geq(m-j)\cdot\mathrm{tr}\left[\log\Big{(}(u\mathbb{I}-A)^{-1}(\widehat{u}\mathbb{I}-A)\Big{)}\right]+\frac{1}{\alpha}\frac{m-j}{m}\cdot\mathrm{tr}\left[\log\left(\mathbb{I}-\alpha(\widehat{u}\mathbb{I}-A)^{-1}\right)\right].$

###### Proof.

By Lemma 3.2 and Lemma 3.3, it is sufficient to show that

$\mathrm{tr}\left[(\mathbb{I}-A)\cdot\log\Big{(}\mathbb{I}-\alpha(\widehat{u}\mathbb{I}-A)^{-1}\Big{)}\right]\geq\frac{m-j}{m}\cdot\mathrm{tr}\left[\log\left(\mathbb{I}-\alpha(\widehat{u}\mathbb{I}-A)^{-1}\right)\right].$

Similar to the proof of Lemma 3.3, we have
$\left\|\alpha(\widehat{u}\mathbb{I}-A)^{-1}\right\|<1$ and

$\displaystyle\mathrm{tr}\left[(\mathbb{I}-A)\cdot\log\Big{(}\mathbb{I}-\alpha(\widehat{u}\mathbb{I}-A)^{-1}\Big{)}\right]=\sum_{i=1}^{d}\left(1-\lambda_{i}(A)\right)\cdot\log\left(1-\frac{\alpha}{\widehat{u}-\lambda_{i}(A)}\right).$

Applying Lemma 3.4 with $g(x)=(1-x)$ and
$f(x)=\log\left(1-\alpha(\widehat{u}-x)^{-1}\right)$ gives

$\displaystyle\mathrm{tr}\left[(\mathbb{I}-A)\cdot\log\Big{(}\mathbb{I}-\alpha(\widehat{u}\mathbb{I}-A)^{-1}\Big{)}\right]$
$\displaystyle\geq\frac{1}{d}\left(\sum_{i=1}^{d}(1-\lambda_{i}(A))\right)\left(\sum_{i=1}^{d}\log\left(1-\frac{\alpha}{\widehat{u}-\lambda_{i}(A)}\right)\right)$
$\displaystyle=\frac{1}{d}\mathrm{tr}\left(\mathbb{I}-A\right)\mathrm{tr}\left[\log\left(\mathbb{I}-\alpha(\widehat{u}\mathbb{I}-A)^{-1}\right)\right].$

In iteration $j$, we have

$\displaystyle\frac{1}{d}\cdot\mathrm{tr}\left(\mathbb{I}-A\right)$
$\displaystyle=\frac{1}{d}\cdot\left(d-j\cdot\alpha\right)$
$\displaystyle=\frac{1}{d}\cdot\left((m-j)\cdot\alpha\right)$
$\displaystyle=\frac{m-j}{m},$

where we use the fact that $\mathrm{tr}(A_{j})=j\alpha$ and $m\alpha=d$.
Combining the two inequalities above proves the statement. ∎

Now we are ready to apply Lemma 2.6 and Lemma 3.5 to prove Lemma 3.1. For this
proof, we explicitly use index $j$ for all the matrices, sets, and variables
used in iteration $0\leq j<m/2$.

###### Proof of Lemma 3.1.

We proceed by induction. For the base case $j=0$, we have $u_{0}=1/2$ and
$\lambda_{i}(A_{0})=0$ for every $1\leq i\leq d$ and therefore the the
statement holds.

For the inductive step, we assume that the statement holds for all
$j^{\prime}\leq j$ and show that $c_{j+1}\geq 1/3$ and
$\kappa(\widehat{u}_{j+1}-A_{j+1})\leq 2/3$ as long as $j<m/2$. We achieve
this using Lemma 2.6, which will first require us to lower bound
$\det(u_{j+1}\mathbb{I}-A_{j+1})$. We show that we can arrive at a lower bound
for $\det(u_{j+1}\mathbb{I}-A_{j+1})$ as a consequence of upper bounding the
average potential increase. We first upper bound the average potential
increase in terms of $\alpha$ and $c_{j}$. From Lemma 3.5, we have that

$\displaystyle\frac{1}{\left\lvert\mathcal{B}_{j}\right\rvert}\sum_{v\in\mathcal{B}_{j}}\Phi^{u_{j}}(A_{j})-\Phi^{u_{j+1}}(A_{j}+vv^{*})$
$\displaystyle\geq\mathrm{tr}\left[\log\left((u_{j}\mathbb{I}-A_{j})^{-1}(u_{j+1}\mathbb{I}-A_{j})\right)\right]+\frac{1}{\alpha
m}\cdot\mathrm{tr}\left[\log\left(\mathbb{I}-\alpha(u_{j+1}\mathbb{I}-A_{j})^{-1}\right)\right]$
$\displaystyle=\mathrm{tr}\left[\log\left((u_{j}\mathbb{I}-A_{j})^{-1}(u_{j+1}\mathbb{I}-A_{j})\right)\right]+\frac{1}{d}\cdot\mathrm{tr}\left[\log\left(\mathbb{I}-\alpha(u_{j+1}\mathbb{I}-A_{j})^{-1}\right)\right]$
$\displaystyle=\frac{1}{d}\left[d\cdot\mathrm{tr}\left[\log\left((u_{j}\mathbb{I}-A_{j})^{-1}(u_{j+1}\mathbb{I}-A_{j})\right)\right]+\mathrm{tr}\left[\log\left(\mathbb{I}-\alpha(u_{j+1}\mathbb{I}-A_{j})^{-1}\right)\right]\right].$

By writing $(u_{j}-x)^{-1}(u_{j}+\delta_{u}-x)=1+\delta_{u}(u_{j}-x)^{-1}$ we
have that

$\mathrm{tr}\left[\log\left((u_{j}\mathbb{I}-A_{j})^{-1}(u_{j+1}\mathbb{I}-A_{j})\right)\right]=\mathrm{tr}\left[\log\left(\mathbb{I}+\delta_{u}(u_{j}\mathbb{I}-A_{j})^{-1}\right)\right],$

and therefore

$\displaystyle\frac{1}{\left\lvert\mathcal{B}_{j}\right\rvert}\sum_{v\in\mathcal{B}_{j}}\Phi^{u_{j}}(A_{j})-\Phi^{u_{j+1}}(A_{j}+vv^{*})$
$\displaystyle\geq\frac{1}{d}\left[d\cdot\mathrm{tr}\left[\log\left(\mathbb{I}+\delta_{u}(u_{j}\mathbb{I}-A_{j})^{-1}\right)\right]+\mathrm{tr}\left[\log\left(\mathbb{I}-\alpha(u_{j+1}\mathbb{I}-A_{j})^{-1}\right)\right]\right]$
$\displaystyle=\frac{1}{d}\left[\mathrm{tr}\left[\log\left(\mathbb{I}+\delta_{u}(u_{j}\mathbb{I}-A_{j})^{-1}\right)^{d}\right]+\mathrm{tr}\left[\log\left(\mathbb{I}-\alpha(u_{j+1}\mathbb{I}-A_{j})^{-1}\right)\right]\right]$
$\displaystyle\geq\frac{1}{d}\left[\mathrm{tr}\left[\log\left(\mathbb{I}+\alpha(u_{j}\mathbb{I}-A_{j})^{-1}\right)\right]+\mathrm{tr}\left[\log\left(\mathbb{I}-\alpha(u_{j+1}\mathbb{I}-A_{j})^{-1}\right)\right]\right]$
$\displaystyle=\frac{1}{d}\sum_{i=1}^{d}\left[\log\left(1+\frac{\alpha}{u_{j}-\lambda_{i}(A_{j})}\right)+\log\left(1-\frac{\alpha}{u_{j}+\delta_{u}-\lambda_{i}(A_{j})}\right)\right]$
$\displaystyle\geq\frac{1}{d}\sum_{i=1}^{d}\left[\log\left(1+\frac{\alpha}{u_{j}-\lambda_{i}(A_{j})}\right)+\log\left(1-\frac{\alpha}{u_{j}-\lambda_{i}(A_{j})}\right)\right]$
$\displaystyle=\frac{1}{d}\sum_{i=1}^{d}\log\left(1-\frac{\alpha^{2}}{(u_{j}-\lambda_{i}(A_{j}))^{2}}\right).$

Since $\log(1-\alpha^{2}x^{-2})$ is increasing on $x$, we have that

$\displaystyle\frac{1}{\left\lvert\mathcal{B}_{j}\right\rvert}\sum_{v\in\mathcal{B}_{j}}\Phi^{u_{j}}(A_{j})-\Phi^{u_{j+1}}(A_{j}+vv^{*})$
$\displaystyle\geq\frac{1}{d}\sum_{i=1}^{d}\log\left(1-\frac{\alpha^{2}}{(u_{j}-\lambda_{i}(A_{j}))^{2}}\right)$
$\displaystyle\geq\frac{1}{d}\sum_{i=1}^{d}\log\left(1-\frac{\alpha^{2}}{c_{j}^{2}}\right)$
$\displaystyle=\log\left(1-\alpha^{2}c_{j}^{-2}\right)$
$\displaystyle\geq-\frac{\alpha^{2}c_{j}^{-2}}{1-\alpha^{2}c_{j}^{-2}}$
$\displaystyle\geq-\frac{2\alpha^{2}}{c_{j}^{2}},$

where we use the assumption that $c_{j}\geq 1/3>\sqrt{2}\alpha$. Since the
vector picked by Algorithm 1 increases the potential value no more than the
average, we have that

$\displaystyle-\log\det(u_{j}\mathbb{I}-A_{j})+\log\det(u_{j+1}\mathbb{I}-A_{j+1})\geq-\frac{2\alpha^{2}}{c_{j}^{2}},$

which is equivalent to

$\det(u_{j+1}\mathbb{I}-A_{j+1})\geq\exp\left(-\frac{2\alpha^{2}}{c_{j}^{2}}\right)\cdot\det(u_{j}\mathbb{I}-A_{j}).$

By combining these inequalities for every iteration up to $j$, we have

$\det(u_{j+1}\mathbb{I}-A_{j+1})\geq\exp\left(-\sum_{j^{\prime}=0}^{j}\frac{2\alpha^{2}}{c_{j^{\prime}}^{2}}\right)\cdot\det(u_{0}\mathbb{I}).$
(10)

Now we apply the condition number inequality in Lemma 2.6. Let

$x_{j+1}=\sqrt{1-\left(\frac{d}{\mathrm{tr}(u_{j+1}\mathbb{I}-A_{j+1})}\right)^{d}\cdot\det(u_{j+1}\mathbb{I}-A_{j+1})}.$

From (10), we have

$x_{j+1}\leq\sqrt{1-\exp\left(-\sum_{j^{\prime}=0}^{j}\frac{2\alpha^{2}}{c_{j^{\prime}}^{2}}\right)\left(\frac{d}{\mathrm{tr}(u_{j+1}\mathbb{I}-A_{j+1})}\right)^{d}\cdot\det(u_{0}\mathbb{I})}.$

Furthermore, notice that

$\displaystyle\mathrm{tr}(u_{j+1}\mathbb{I}-A_{j+1})$
$\displaystyle=d\cdot(u_{0}+(j+1)\cdot\delta_{u})-(j+1)\cdot\alpha$
$\displaystyle=\frac{d}{2}+(j+1)\cdot\left(d\delta_{u}-\alpha\right)$
$\displaystyle=\frac{d}{2},$

where the final equality follows by the definition of $\delta_{u}=\alpha/d$.
We also have that

$\det(u_{0}\mathbb{I})=\frac{1}{2^{d}}.$

Combined with the inductive hypothesis, we have

$\displaystyle x_{j+1}$
$\displaystyle\leq\sqrt{1-\exp\left(-\sum_{j^{\prime}=0}^{j}\frac{2\alpha^{2}}{c_{j^{\prime}}^{2}}\right)}$
$\displaystyle\leq\sqrt{1-\exp\left(-18\sum_{j^{\prime}=0}^{j}\alpha^{2}\right)}$
$\displaystyle\leq\sqrt{1-\exp\left(-9m\alpha^{2}\right)}$
$\displaystyle=\sqrt{1-\exp\left(-9d\alpha\right)}$
$\displaystyle\leq\sqrt{1-\exp\left(-\frac{9}{221}\right)}$
$\displaystyle\leq\frac{1}{5}.$

Then, it holds by Lemma 2.6 that

$\kappa(u_{j+1}\mathbb{I}-A_{j+1})\leq\frac{1+x_{j+1}}{1-x_{j+1}}\leq\frac{3}{2}.$

We also have that

$\lambda_{\mathrm{max}}(u_{j+1}\mathbb{I}-A_{j+1})\geq\frac{1}{d}\cdot\mathrm{tr}(u_{j+1}\mathbb{I}-A_{j+1})=\frac{1}{2}.$

Then,

$c_{j+1}=\lambda_{\mathrm{min}}(u_{j+1}\mathbb{I}-A_{j+1})\geq\frac{\lambda_{\mathrm{max}}(u_{j+1}\mathbb{I}-A_{j+1})}{\kappa(u_{j+1}\mathbb{I}-A_{j+1})}\geq\frac{1}{3},$

which completes the inductive step. ∎

We believe the tools used to prove Theorem 1 are interesting in their own
right. It is known that the only non-trivial matrix function with a simple
formula for rank-1 updates is $f(x)=x^{-1}$ [BKS18]. Previous potential
function-based sparsification algorithms exploit this formula and the
potential function $\Psi^{u}(A)=\mathrm{tr}(u\mathbb{I}-A)^{-1}$ in their
analysis [BSS12]. Sparsification can be seen as a relaxation of the
$\mathsf{KS}_{2}$ problem in the sense that sparsification algorithms are free
to add different scalar multiples of some $vv^{*}$ in each iteration and use
the same vector multiple times. The analyses of these algorithms appear to
become intractable when these relaxations are removed, partly due to the use
of the Sherman-Morrison formula for the inverse of rank-1 updates. We overcome
this apparent intractability using the logarithmic potential function
$\Phi^{u}(A)=\mathrm{tr}\log(u\mathbb{I}-A)^{-1}$, the Matrix Determinant
Lemma and Lemma 3.3. In addition, instead of examining all the vectors of
$\mathcal{I}$ in each iteration, we analyse the change of potential functions
over all the unpicked vectors in each iteration, ensuring that the set of
picked vectors and the set of unpicked ones always forms a partition; this is
another key difference between our analysis and the related ones in the
literature.

##  4 The Second Algorithm and Analysis

In this section, we present Algorithm 2 which also achieves the theoretical
guarantees stated in Theorem 1. We can view Algorithm 2 as a modification of
Algorithm 1 in which we fix the barrier value to be $1$, and set $\delta_{u}$
to be $0$. Thus, in each iteration we select the vector $v$ which maximizes
the determinant $\det(\mathbb{I}-A_{j}-vv^{*})$. By the Matrix Determinant
Lemma (Lemma 2.4), this is equivalent to choosing $v$ to minimize the
quadratic form $v^{*}(\mathbb{I}-A_{j})^{-1}v$ in each iteration.

1 Input: $\mathcal{I}=\\{v_{i}\\}_{i=1}^{m}$, where $v_{i}\in\mathbb{C}^{d}$
and $\left\|v_{i}\right\|^{2}=\alpha$

2 $A_{0}\leftarrow\mathbf{0}_{d\times d}$,
$\mathcal{A}_{0}\leftarrow\emptyset$

3 $\mathcal{B}_{0}\leftarrow\mathcal{I}$

4 for  _$j=0$ to $m/2-1$_ do

5
$v_{j}\leftarrow\operatorname*{arg\,min}_{v\in\mathcal{B}_{j}}v^{*}(\mathbb{I}-A_{j})^{-1}v$

6 $A_{j+1}\leftarrow A_{j}+v_{j}v_{j}^{*}$

7 $\mathcal{A}_{j+1}\leftarrow\mathcal{A}_{j}\cup\\{v_{j}\\}$

8 $\mathcal{B}_{j+1}\leftarrow\mathcal{B}_{j}\setminus\\{v_{j}\\}$

9

10 end for

return $\mathcal{A}_{m/2}$

Algorithm 2

Rather than considering the change in the potential function $\Phi^{1}(A_{j})$
in each iteration, in Lemma 4.1 we directly bound the value of

$\Phi^{1}(A_{m/2})=\mathrm{tr}\log(\mathbb{I}-A_{m/2})^{-1}=-\log\det(\mathbb{I}-A_{m/2}),$

where $A_{m/2}$ is the matrix corresponding to the output of Algorithm 2.

######  Lemma 4.1.

Let $A_{m/2}$ be the matrix corresponding to $\mathcal{A}_{m/2}$. Then, it
holds that

$\log\det(\mathbb{I}-A_{m/2})\geq-d\log(2)-\frac{2d^{2}}{m}.$

###### Proof.

In each iteration of Algorithm 2, we have that

$\sum_{v\in\mathcal{B}_{j}}v^{*}(\mathbb{I}-A_{j})^{-1}v=\mathrm{tr}\left((\mathbb{I}-A_{j})^{-1}(\mathbb{I}-A_{j})\right)=\mathrm{tr}(\mathbb{I})=d.$

Therefore, it holds for the selected $v_{j}$ that

$v_{j}^{*}(\mathbb{I}-A_{j})^{-1}v_{j}\leq\frac{1}{\left\lvert
B_{j}\right\rvert}\sum_{v\in\mathcal{B}_{j}}v^{*}(\mathbb{I}-A_{j})^{-1}v=\frac{d}{m-j}.$
(11)

By the Matrix Determinant Lemma (Lemma 2.4), we have that

$\displaystyle\det(\mathbb{I}-A_{j+1})$
$\displaystyle=(1-v_{j}^{*}(\mathbb{I}-A_{j})^{-1}v_{j})\det(\mathbb{I}-A_{j})$
$\displaystyle\geq\left(1-\frac{d}{m-j}\right)\det(\mathbb{I}-A_{j})$
$\displaystyle\geq\left[\prod_{i=0}^{j}\left(1-\frac{d}{m-i}\right)\right]\det(\mathbb{I}-A_{0})$
$\displaystyle=\prod_{i=0}^{j}\left(1-\frac{d}{m-i}\right),$

where the second inequality follows by applying (11) a further $j$ times.
Then, we have

$\displaystyle\log\det(\mathbb{I}-A_{m/2})$
$\displaystyle\geq\sum_{i=0}^{m/2-1}\log\left(1-\frac{d}{m-i}\right)$
$\displaystyle\geq\int_{i=0}^{\frac{m}{2}}\log\left(1-\frac{d}{m-i}\right)\mathrm{d}i$
$\displaystyle=\int_{i=0}^{\frac{m}{2}}\log(m-i-d)\mathrm{d}i-\int_{i=0}^{\frac{m}{2}}\log(m-i)\mathrm{d}i$
$\displaystyle=\big{[}-(m-i-d)\log(m-i-d)+(m-i-d)+(m-i)\log(m-i)-(m-i)\big{]}_{i=0}^{m/2}$
$\displaystyle=\big{[}(m-i-d+d)\log(m-i)-(m-i-d)\log(m-i-d)-d\big{]}_{i=0}^{m/2}$
$\displaystyle=\left[d\log(m-i)-(m-i-d)\log\left(1-\frac{d}{m-i}\right)-d\right]_{i=0}^{m/2}$
$\displaystyle=d\log\left(\frac{m}{2}\right)-\left(\frac{m}{2}-d\right)\log\left(1-\frac{2d}{m}\right)-d\log(m)+(m-d)\log\left(1-\frac{d}{m}\right)$
$\displaystyle\geq-d\log(2)+\left(\frac{m}{2}-d\right)\frac{2d}{m}-\frac{(m-d)(d/m)}{1-(d/m)}$
$\displaystyle=-d\log(2)+d-\frac{2d^{2}}{m}-d$
$\displaystyle=-d\log(2)-\frac{2d^{2}}{m},$

where the second line follows since $\log(1-d/(m-i))$ is a decreasing function
on $i$, the second equality follows since
$\int\log(x-y)\mathrm{d}y=-(x-y)\log(x-y)+(x-y)+C$, and for the final
inequality we use the fact that $-x/(1-x)\leq\log(1-x)\leq-x$ for all $0\leq
x<1$. This completes the proof. ∎

With this bound on the determinant of $\left(\mathbb{I}-A_{m/2}\right)$, we
are able to apply Lemma 2.6 to show that Algorithm 2 also achieves the
guarantee given in Theorem 1.

###### Proof of Theorem 1..

Since $m\alpha=d$, we have that

$\mathrm{tr}(\mathbb{I}-A_{m/2})=d-\frac{m\alpha}{2}=\frac{d}{2}.$

Then, by Lemma 4.1 and the condition of $m\geq 49d^{2}$, we have that

$\displaystyle\log\left[\left(\frac{d}{\mathrm{tr}(\mathbb{I}-A_{m/2})}\right)^{d}\det(\mathbb{I}-A_{m/2})\right]$
$\displaystyle\geq
d\log(2)-d\log(2)-\frac{2d^{2}}{m}=-\frac{2d^{2}}{m}\geq\log\left(\frac{24}{25}\right).$

Then, let

$x\triangleq\sqrt{1-\left(\frac{d}{\mathrm{tr}(\mathbb{I}-A_{m/2})}\right)^{d}\det(\mathbb{I}-A_{m/2})}\leq\sqrt{1-\frac{24}{25}}=\frac{1}{5}.$

By Lemma 2.6, we can bound the condition number of $\mathbb{I}-A_{m/2}$ as

$\kappa(\mathbb{I}-A_{m/2})\leq\frac{1+x}{1-x}\leq\frac{3}{2}.$

Then, we have that

$\lambda_{\mathrm{max}}(\mathbb{I}-A_{m/2})\leq\kappa(\mathbb{I}-A_{m/2})\cdot\lambda_{\mathrm{min}}(\mathbb{I}-A_{m/2})\leq\frac{3}{2}\cdot\frac{1}{2}=\frac{3}{4},$

and

$\lambda_{\mathrm{\min}}(\mathbb{I}-A_{m/2})\geq\frac{\lambda_{\mathrm{max}}(\mathbb{I}-A_{m/2})}{\kappa(\mathbb{I}-A_{m/2})}\geq\frac{2}{3}\cdot\frac{1}{2}=\frac{1}{3}.$

Since
$\lambda_{\mathrm{max}}(A_{m/2})=1-\lambda_{\mathrm{min}}(\mathbb{I}-A_{m/2})$
and
$\lambda_{\mathrm{min}}(A_{m/2})=1-\lambda_{\mathrm{max}}(\mathbb{I}-A_{m/2})$,
we have that

$\frac{1}{4}\leq u^{*}A_{m/2}u\leq\frac{2}{3},$

for all unit vectors $u\in\mathbb{C}^{d}$. The time complexity analysis of the
algorithm follows the one for Algorithm 1. ∎

Finally, as our presented algorithms are based on maximizing the determinant
of the constructed matrix $A$ (or $\mathbb{I}-A$) and applying the condition
number inequality (Lemma 2.6), we discuss the difference between our technique
with a direct application of more general determinant maximisation algorithms.
Recall that in the cardinality-based determinant maximisation problem, we are
given as input a set of vectors $\mathcal{I}=\\{v_{i}\\}_{i=1}^{m}$ and an
integer $k$, and the objective is to find

$\widehat{S}=\operatorname*{arg\,max}_{\begin{subarray}{c}S\subset\mathcal{I}\\\
\left\lvert S\right\rvert\leq k\end{subarray}}\det\left(\sum_{v\in
S}vv^{*}\right).$

The state-of-the-art polynomial-time approximation algorithm is presented by
Singh and Xie [SX18] and achieves an $\exp(d)$-approximation of the optimal
solution.

By the result of Marcus et al. [MSS15], we know that for any set
$\mathcal{I}=\\{v_{i}\\}_{i=1}^{m}$ such that
$\sum_{v\in\mathcal{I}}vv^{*}=\mathbb{I}$ and $\left\|v_{i}\right\|=\alpha$
for all $i\in[m]$, there exists a partition $S_{1},S_{2}$ of $\mathcal{I}$
such that

$\left\|\frac{1}{2}\cdot\mathbb{I}-\sum_{i\in S_{j}}v_{i}v_{i}^{*}\right\|\leq
3\sqrt{\alpha}$

for $j\in\\{1,2\\}$. Without loss of generality, let $\left\lvert
S_{1}\right\rvert\geq\left\lvert S_{2}\right\rvert$. Then, we have that

$\det\left(\sum_{i\in
S_{1}}v_{i}v_{i}^{*}\right)\geq\left(\frac{1}{2}-3\sqrt{\alpha}\right)^{d/2}\left(\frac{1}{2}+3\sqrt{\alpha}\right)^{d/2}=2^{-d}\exp\left(-\Theta\left(\frac{d^{2}}{m}\right)\right).$

Thus, the guarantee on the determinant given by Lemma 4.1 matches the
determinant guarantee implied by [MSS15]. Applying Lemma 2.6, we achieve a
non-trivial bound on the eigenvalues of the constructed matrix when
$m=\Omega\left(d^{2}\right)$. On the other hand, applying the algorithm by
Singh and Xie [SX18] returns a set $S$ such that $\det\left(\sum_{i\in
S}v_{i}v_{i}^{*}\right)\geq 2^{-d}\exp\left(-O\left(d^{3}/m\right)\right)$,
and gives a non-trivial bound on the eigenvalues of the constructed matrix
only when $m=\Omega\left(d^{3}\right)$.

## Acknowledgement

This work is supported by EPSRC Early Career Fellowship (EP/T00729X/1) and
EPSRC Doctoral Training Studentship (2590711). Part of this work was done when
Peter Macgregor and He Sun were visiting the Simons Institute for the Theory
of Computing in Fall 2023.

## References

  * [AGSS18] Nima Anari, Shayan Oveis Gharan, Amin Saberi, and Nikhil Srivastava.  Approximating the largest root and applications to interlacing families.  In 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’18), pages 1015–1028, 2018.
  * [BKS18] Bernhard Beckermann, Daniel Kressner, and Marcel Schweitzer.  Low-rank updates of matrix functions.  SIAM Journal on Matrix Analysis and Applications, 39(1):539–565, 2018.
  * [BLP+22] Adam Brown, Aditi Laddha, Madhusudhan Pittu, Mohit Singh, and Prasad Tetali.  Determinant maximization via matroid intersection algorithms.  In 63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS’22), pages 255–266, 2022.
  * [BLS24] Adam Brown, Aditi Laddha, and Mohit Singh.  Maximizing the minimum eigenvalue in constant dimension.  arXiv:2401.14317, 2024.
  * [BSS12] Joshua Batson, Daniel A. Spielman, and Nikhil Srivastava.  Twice-ramanujan sparsifiers.  SIAM Journal on Computing, 41(6):1704–1721, 2012.
  * [DZ07] Jiu Ding and Aihui Zhou.  Eigenvalues of rank-one updated matrices with some applications.  Applied Mathematics Letters, 20(12):1223–1226, 2007.
  * [Hig08] Nicholas J. Higham.  Functions of Matrices.  Society for Industrial and Applied Mathematics, 2008.
  * [JMS23] Ben Jourdan, Peter Macgregor, and He Sun.  Is the algorithmic Kadison-Singer problem hard?  In 34th International Symposium on Algorithms and Computation (ISAAC’23), pages 43:1–43:18, 2023.
  * [LS17] Yin Tat Lee and He Sun.  An sdp-based algorithm for linear-sized spectral sparsification.  In 49th Annual ACM Symposium on Theory of Computing (STOC’17), page 678–687, 2017.
  * [LS18] Yin Tat Lee and He Sun.  Constructing linear-sized spectral sparsification in almost-linear time.  SIAM Journal on Computing, 47(6):2315–2336, 2018.
  * [MSS15] Adam W. Marcus, Daniel A. Spielman, and Nikhil Srivastava.  Interlacing families II: Mixed characteristic polynomials and the Kadison—Singer problem.  Annals of Mathematics, 182(1):327–350, 2015.
  * [MUV+97] Jorma Kaarlo Merikoski, Uoti Urpala, Ari Virtanen, Tin-Yau Tam, and Frank Uhlig.  A best upper bound for the 2-norm condition number of a matrix.  Linear Algebra and its Applications, 254(1):355–365, 1997.
  * [NS18] M. Thamban Nair and Arindama Singh.  Linear Algebra.  Springer Singapore, 2018.
  * [SX18] Mohit Singh and Weijun Xie.  Approximate positive correlated distributions and approximation algorithms for ${D}$-optimal design.  In Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’18), pages 2240–2255, 2018.
  * [SZ22] Daniel A. Spielman and Peng Zhang.  Hardness Results for Weaver’s Discrepancy Problem.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022), volume 245, pages 40:1–40:14, 2022.
  * [Wea04] Nik Weaver.  The Kadison-Singer problem in discrepancy theory.  Discrete Mathematics, 278(1-3):227–239, 2004.
  * [Wea13] Nik Weaver.  The Kadison-Singer problem in discrepancy theory, II.  arXiv:1303.2405, 2013.
  * [WX08] Avi Wigderson and David Xiao.  Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications.  Theory of Computing, 4(1):53–76, 2008.