# Determinant Maximization via Matroid Intersection Algorithms

Adam Brown<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Georgia Institute of Technology.  Aditi Laddha 11footnotemark: 1 Georgia
Institute of Technology.  Madhusudhan Pittu<EMAIL_ADDRESS><EMAIL_ADDRESS>Carnegie Mellon University.  Mohit Singh11footnotemark: 1
Georgia Institute of Technology.  Prasad Tetali22footnotemark: 2 Carnegie
Mellon University.

###### Abstract

Determinant maximization problem gives a general framework that models
problems arising in as diverse fields as statistics [Puk06], convex geometry
[Kha96], fair allocations [AGSS16], combinatorics [AGV18], spectral graph
theory [NST19a], network design, and random processes [KT12]. In an instance
of a determinant maximization problem, we are given a collection of vectors
$U=\\{v_{1},\ldots,v_{n}\\}\subset\mathbb{R}^{d}$, and a goal is to pick a
subset $S\subseteq U$ of given vectors to maximize the determinant of the
matrix $\sum_{i\in S}v_{i}v_{i}^{\top}$. Often, the set $S$ of picked vectors
must satisfy additional combinatorial constraints such as cardinality
constraint $\left(|S|\leq k\right)$ or matroid constraint ($S$ is a basis of a
matroid defined on the vectors).

In this paper, we give a polynomial-time deterministic algorithm that returns
a $r^{O(r)}$-approximation for any matroid of rank $r\leq d$. This improves
previous results that give $e^{O(r^{2})}$-approximation algorithms relying on
$e^{O(r)}$-approximate _estimation_ algorithms [NS16, AG17, AGV18, MNST20] for
any $r\leq d$. All previous results use convex relaxations and their
relationship to stable polynomials and strongly log-concave polynomials. In
contrast, our algorithm builds on combinatorial algorithms for matroid
intersection, which iteratively improve any solution by finding an
_alternating negative cycle_ in the _exchange graph_ defined by the matroids.
While the $\det(.)$ function is not linear, we show that taking appropriate
linear approximations at each iteration suffice to give the improved
approximation algorithm.

##  1 Introduction

Determinant maximization problem gives a general framework that models
problems arising in as diverse fields as statistics [Puk06], convex geometry
[Kha96], fair allocations [AGSS16], combinatorics [AGV18], spectral graph
theory [NST19a], network design and random processes [KT12]. In an instance of
a determinant maximization problem, we are given a collection of vectors
$U=\\{v_{1},\ldots,v_{n}\\}\subset\mathbb{R}^{d}$, and a goal is to pick a
subset $S\subseteq U$ of given vectors to maximize the determinant of the
matrix $\sum_{i\in S}v_{i}v_{i}^{\top}$. Additionally, the set $S$ of picked
vectors must satisfy additional combinatorial constraints such as cardinality
constraint $\left(|S|\leq k\right)$ or matroid constraint ($S$ is a basis of a
matroid defined on the vectors).

Apart from its modeling strength, from a technical perspective, determinant
maximization has brought interesting connections between areas such as
combinatorial optimization, convex analysis, geometry of polynomials, graph
sparsification and complexity of permanent and other counting problems
[ALSW17, AGSS16, AG17, Kha96].

#### Applications.

Observe that when the number of vectors picked is exactly $d$, the objective
is precisely the square of the volume of the parallelepiped spanned by the
selected vectors. The problem of finding the largest volume parallelepiped in
a collection of given vectors has been studied [Nik15a, Kha96, SEFM15] for
over three decades. Another interesting application is the determinantal point
processes [KT12], where a probability distribution over subsets of vectors is
defined. The probability of selecting a subset is defined to be proportional
to the squared volume of the parallelepiped defined by them. These
distributions display nice properties of negative correlation. Finding sets
with the largest probability mass is exactly the determinant maximization
problem. We refer the reader to [NST19a] for applications in experimental
design and to [AGSS16] for application to fair allocations.

The computational complexity of the determinant maximization depends crucially
on the combinatorial set family which constrains the set of feasible
collection of vectors. The simplest constraint being the cardinality
constraint, wherein the number of vectors is fixed, has been the most widely
studied variant. For this, a variety of methods including convex programming
based methods [ALSW17, SEFM15, Nik15b, SX18], combinatorial methods - such as
local search and greedy [Kha96, MSTX19, LZ21] \- as well as close relationship
to graph sparsification [ALSW17] have been exploited to obtain efficient
approximation algorithms with very good guarantees. Overall, these results
give a very clear understanding of the computational complexity of the
problem.

The more general case when the combinatorial constraints are defined by a
matroid constraint has recently received extensive focus [NS16, AGSS16, AG17,
AGV18, MNST20]. This is especially interesting since some of the applications
are naturally modeled as matroid constraints, in particular, as partition
constraints. Unfortunately, there is a big gap between estimation algorithms
and approximation algorithms in this case! Indeed, one can approximately
_estimate_ the value of an optimal solution with a good guarantee, however,
finding such a solution is much more challenging, leading to an exponential
loss in the approximation factor. For example, even for the special case of
the partition matroid, there is an $e^{d}$-approximate estimation algorithm
but the best known approximation algorithms return a solution with an
approximation factor of $e^{O(d^{2})}$, an exponential blow-up111Since we are
computing the determinant of $d\times d$ matrices, the exponent of $d$ in the
approximation factor is appropriate. Indeed, many works even consider the
$d^{\text{th}}$-root of the determinant where the approximation factors are
also the $d^{\text{th}}$-root of the above bounds.. A fundamental reason for
this gap is the reliance on the relationship between convex programming
relaxations for the problem and the theory of stable polynomials and its
generalization to strongly log-concave polynomials. Unfortunately, these
methods are inherently non-algorithmic and do not give a simple way to obtain
efficient algorithms with the same guarantees that match the estimation
bounds.

###  1.1 Our Results and Contributions

In this work, we introduce new combinatorial methods for determinant
maximization under a matroid constraint and give an
$O(d^{O(d)})$-deterministic approximation algorithm. While previous works have
used a convex programming approach and the theory of stable polynomials, our
approach builds on the classical matroid intersection algorithm. Our first
result focuses on the case when the rank of the matroid is exactly $d$, i.e.,
the output solution will contain precisely $d$ vectors.

###### Theorem 1

There is a polynomial time algorithm which, given a collection of vectors
$v_{1},\ldots,v_{n}\in\mathbb{R}^{d}$ and a matroid
$\mathcal{M}=([n],\mathcal{I})$ of rank $d$, returns a set $S\in\mathcal{I}$
such that

$\det\left(\sum_{i\in
S}v_{i}v_{i}^{\top}\right)=\Omega\left(\frac{1}{d^{O(d)}}\right)\max_{S^{*}\in\mathcal{I}}\det\left(\sum_{i\in
S^{*}}v_{i}v_{i}^{\top}\right).$

Our results improve the $e^{O(d^{2})}$-approximation algorithm which relies on
the $e^{O(d)}$-estimation algorithm [AGV18, AG17, MNST20]. Our algorithm
builds on the matroid intersection algorithm and is an iterative algorithm
that starts at any feasible solution and improves the objective in each step.
To maintain feasibility in the matroid constraint, each step of the algorithm
is an exchange of multiple elements as found by an alternating cycle of an
appropriately defined exchange graph.

Result for $r\leq d$. We also generalize the result when the rank $r$ of the
matroid is at most $d$. Observe that the solution matrix $\sum_{i\in
S}v_{i}v_{i}^{\top}$ is a $d\times d$ matrix of rank at most $r$ and,
therefore, the appropriate objective to consider is the product of its largest
$r$ eigenvalues, or equivalently, the elementary symmetric function of order
$r$ of its eigenvalues. Let $sym_{r}(M)$ be the $r^{th}$ elementary symmetric
function of the eigenvalues of the $d\times d$ matrix $M$. Thus, our objective
is to maximize $sym_{r}\left(\sum_{i\in S}v_{i}v_{i}^{\top}\right)$.

###### Theorem 2

There is a polynomial-time algorithm which, given a collection of vectors
$v_{1},\ldots,v_{n}\in\mathbb{R}^{d}$ and a matroid
$\mathcal{M}=([n],\mathcal{I})$ of rank $r\leq d$, returns a set
$S\in\mathcal{I}$ such that

$sym_{r}\left(\sum_{i\in
S}v_{i}v_{i}^{\top}\right)=\Omega\left(\frac{1}{r^{O(r)}}\right)\max_{S^{*}\in\mathcal{I}}sym_{r}\left(\sum_{i\in
S^{*}}v_{i}v_{i}^{\top}\right).$

This again improves the best bound of $e^{{O(r^{2})}}$-approximation algorithm
based on $e^{O(r)}$-approximate estimation algorithms. The proof of Theorem 2
is presented in Appendix B.

Technical Overview. For intuition, let $\operatorname{vol}(S)$ denote the
volume of the parallelepiped spanned by the vectors in $S$. Then
$\operatorname{vol}(S)^{2}=\det\left(\sum_{i\in S}v_{i}v_{i}^{\top}\right)$,
for any $S\subseteq U$ with $|S|=d$, so we can think of
$\operatorname{vol}(S)$ as an equivalent objective function. First, observe
that the feasibility problem of checking whether there is a set
$S\in\mathcal{I}$ such that $\operatorname{vol}(S)>0$ can be reduced to
matroid intersection. Indeed, the feasibility problem is equivalent to
checking if there is a common basis of the matroid $\mathcal{M}$ and the
linear matroid defined by the vectors $\\{v_{1},\ldots,v_{n}\\}$. Since we aim
to maximize $\operatorname{vol}(S)$ over all independent sets $S$, a natural
approach is to use the weighted matroid intersection algorithm. Unfortunately,
our weights are not linear, i.e., $\operatorname{vol}(S)$ does not equal
$\sum_{i\in S}w_{i}$ or log-linear $\prod_{i\in S}w_{i}$ for some weights $w$
on the vectors. Nonetheless, the matroid intersection algorithm forms the
backbone of our approach.

#### Overview of Matroid Intersection.

Before we describe our algorithm, let us review a classical algorithm to find
a maximum weight common basis of two matroids. Given $U=\\{1,\ldots,n\\}$, a
weight function $w:U\rightarrow\mathbb{R}$ and two matroids
$\mathcal{M}_{1}=(U,\mathcal{I}_{1})$ and
$\mathcal{M}_{2}=(U,\mathcal{I}_{2})$, the goal is to find a common basis $S$
of maximum weight $w(S):=\sum_{e\in S}w_{e}$. We assume that there exists a
common basis of the two matroids. Consider the following simple algorithm that
also introduces some of the basic ingredients necessary for our algorithm. The
algorithm will take as an input a common basis $S$ and either certify that $S$
is a maximum weight common basis or return a new common basis $\widehat{S}$ of
higher weight. To explain the algorithm, we recall the important concept of
the exchange graph. Given the set $S$, we construct a directed bipartite graph
$G(S)$ with bipartitions given by $U\setminus S$ and $S$. For any $u\in
U\setminus S$ and $v\in S$, $G(S)$ contains an arc from $u$ to $v$ if $S-v+u$
is a basis in $\mathcal{M}_{2}$ and an arc from $v$ to $u$ if $S-v+u$ is a
basis in $\mathcal{M}_{1}$. For convenience, we use $S-v+u$ to refer to the
set $(S\cup\\{u\\})\setminus\\{v\\}$. Moreover, give each vertex $u\in
U\setminus S$ a weight $-w_{u}$ and each vertex $v\in S$ a weight of $w_{v}$.
A nice fact from matroid theory is that $S$ is a maximum weight basis if and
only if there is no negative weight cycle in this directed graph (Chapter 41,
Theorem 41.5 [Sch03]). Moreover, if $C$ is a directed negative weight cycle
with minimum hops222Hops here refers to the number of arcs of the cycle., then
$S\Delta C$ forms a common basis of the two matroids whose weight is strictly
larger than the weight of $S$. Thus, the algorithm finds a maximum weight
basis by iteratively finding a negative weight cycle in such an exchange
graph.

With the above algorithm as a guiding tool, we describe our algorithm. The two
matroids are precisely the constraint matroid $\mathcal{M}$ and the linear
matroid defined over the vectors. A first challenge is that the objective
function $\operatorname{vol}(S)^{2}=\det\left(\sum_{i\in
S}v_{i}v_{i}^{\top}\right)$ is not linear. Thus it is not possible to define
the vertex weights as was done above. But a natural function to work with
instead is the function $\log\operatorname{vol}(S)$, which is known to be
submodular. While we do not use submodularity explicitly, our algorithm takes
linear approximations of this function at each iteration while searching for
improvements as in the matroid intersection algorithm. We use the geometric
relationship between $\operatorname{vol}$ and $\det$ closely. The first new
ingredient in our algorithm is to introduce _arc_ weights rather than vertex
weights in the exchange graph $G(S)$. Indeed for the forward arcs $(u,v)$ for
$u\not\in S$ and $v\in S$ that correspond to the linear matroid, we introduce
a weight of $-\log\frac{\operatorname{vol}(S-v+u)}{\operatorname{vol}(S)}$. We
also introduce a weight of $0$ for the backward arcs, which correspond to the
arcs for the constraint matroid $\mathcal{M}$. The crucial observation is the
following interpretation of the weight
$\log\frac{\operatorname{vol}(S-v+u)}{\operatorname{vol}(S)}$: write the
vector $u\not\in S$ in the basis $S$, i.e. $u=\sum_{v\in S}a_{uv}v$, for some
$a_{uv}\in\mathbb{R}$ for each $v\in S$. Then
$\frac{\operatorname{vol}(S-v+u)}{\operatorname{vol}(S)}=|a_{uv}|$ (See Lemma
3). Such relationships between the ratio of volumes and coefficients in
expressing the vectors in basis given by $S$ play an important role.

Our first lemma shows that if the volume of the current solution is _much_
smaller than the optimal solution, then there must be a cycle such that the
sum of weights of the arcs on the cycle is significantly negative.

######  Lemma 1 (Determinant to Cycle)

Let $S$ be a basis of $\mathcal{M}$ and $OPT$ be the basis of $\mathcal{M}$
maximizing $\operatorname{vol}(OPT)$. If $\operatorname{vol}(OPT)\geq
e^{5d\log d}\cdot\operatorname{vol}(S)$, then there exists a directed cycle
$C$ of $2\ell$ hops for some $\ell>0$ in the exchange graph $G(S)$ such that

$\prod_{(u,v)\in C,u\notin S,v\in S}|a_{uv}|\geq 2(\ell!)^{3}=:f(\ell).$

We call such a cycle an $f$-violating cycle. Observe that such a cycle can be
found as a negative weight $2\ell$-hop cycle when weights are updated to
$w_{\ell}(u,v)=\frac{1}{\ell}\log f(\ell)-\log|a_{uv}|$ for a forward arc
$(u,v)$ where $u\not\in S$ and $v\in S$. The lemma relies on the following
observation. Abusing notation slightly, let $T$ and $S$ be matrices whose
columns are the vectors in $OPT$ and $S$, respectively. Writing each vector in
$OPT$ in the basis given by $S$ we obtain $T=SA^{\top}$ for some matrix $A$.
The condition in the lemma implies that $\det(A)\geq e^{5d\log d}$. Also
observe that the weight of any $(u,v)$ where $u\in OPT$ and $v\in S$ is
exactly $-\log|a_{uv}|$ where $a_{uv}$ is the $(u,v)^{\text{th}}$-entry in
$A$. Combining these facts, we can show there exists a cycle satisfying the
conditions of the lemma.

The next step in the algorithm is to find an $f$-violating cycle $C$ and then
update the solution to $T=S\Delta C$. Again, we relate the change in objective
$\operatorname{vol}(T)$ to the coefficients. While the entries $|a_{uv}|$ of
the cycle are large, the objective of the new solution $T$ depends not only on
the weight of the edges of the cycle but the weight of all arcs between all
vertices in $C\setminus S$ and $C\cap S$. Indeed, consider a square matrix $B$
with rows and columns indexed by $C\setminus S$ and $S\cap C$ respectively
with entry $(u,v)$ as $a_{uv}$. Recall $a_{uv}$ is the coefficient of vector
$v$ when $u$ is expressed in basis $S$. Then
$\operatorname{vol}(T)=|\det(B)|\cdot\operatorname{vol}(S)$ (Lemma 6). Thus it
remains to lower bound the determinant of $B$. The entries on the diagonal of
the matrix $B$ exactly correspond to entries that define the weights of the
forward arcs on the cycle $C$. Thus Lemma 1 implies that the product of the
diagonal entries of $B$ is large. In the next lemma, we show that if the cycle
$C$ is the _minimum hop_ $f$-violating cycle, then we can in fact lower bound
the determinant of the matrix.

######  Lemma 2 (Cycle to Determinant)

If $C$ is a minimum hop $f$-violating cycle in the exchange graph $G(S)$, then
$\operatorname{vol}(S\Delta C)\geq 2\cdot\operatorname{vol}(S)$. Moreover,
$S\Delta C$ is also a basis of $\mathcal{M}$.

This lemma crucially uses the fact that $C$ is a minimum hop $f$-violating
cycle as in the case for matroid intersection algorithms. Indeed, off-diagonal
entries of the matrix $B$ correspond to arcs that form chords of the cycle
$C$. The minimality of $C$ allows us to show upper bounds on all the off-
diagonal entries of the matrix $B$. A technical calculation then allows us to
lower bound the determinant.

###  1.2 Related Work

Determinant Maximization under Cardinality Constraints. Determinant
maximization problems under a cardinality constraint have been studied widely
[Kha96, SEFM15, Nik15b, SX18, ALSW17, MSTX19]. Currently, the best
approximation algorithm for the case $r\leq d$ is an $e^{r}$-approximation due
to Nikolov [Nik15b] and for $r\geq d$, there is an $e^{d}$-approximation
[SX18]. It turns out that the problem gets significantly easier when $r>>d$,
and there is a $(1+\epsilon)^{d}$-approximation when $r\geq
d+\frac{d}{\epsilon}$ [ALSW17, MSTX19, LZ21]. These results use local search
methods and are closely related to the algorithm discussed in this paper, as
the cycle improving algorithm will always find a $2$-cycle when the matroid is
defined by the cardinality constraint.

Determinant Maximization under Matroid Constraints. As mentioned earlier,
determinant maximization under a matroid constraint is considerably
challenging and the bounds also depend on the rank $r$ of the constraint
matroid. There are $e^{O(r)}$-estimation algorithms when $r\leq d$ [NS16,
AG17, ALGV19] and a $\min\\{e^{O(r)},O\bigl{(}d^{O(d)}\bigr{)}\\}$-estimation
algorithm when $r\geq d$ [MNST20]. The output of these algorithms is a random
feasible set whose objective is at least
$\min\\{e^{O(r)},O\bigl{(}d^{O(d)}\bigr{)}\\}$ of the objective of a convex
programming relaxation, in expectation. Since the approximation guarantees are
exponential, it can happen that the output set has objective zero almost
always. To convert them into deterministic algorithms (or randomized
algorithms that work with high probability), additional loss in approximation
factor is incurred. These results imply an $e^{O(d^{2})}$-approximation
algorithm when $r\leq d$, and a $O\bigl{(}d^{O(d^{3})}\bigr{)}$-approximation
algorithm [MNST20] for $r\geq d$. Approximation algorithms are also known
where the approximation factor is exponential in the size of the ground set
for special classes of matroids [ESV17].

Nash Social Welfare and its generalizations. A special case of the determinant
maximization problem is the Nash Social Welfare problem [CKM+16]. In the Nash
Social Welfare problem, we are given $m$ items and $d$ players and there is a
valuation function $v_{i}:2^{[m]}\rightarrow\mathbb{R}_{+}$ for each player
$i\in[d]$ that specifies value obtained by a player when given a bundle of
items. The goal is to find an assignment of items to players to maximize the
_geometric mean_ of the valuations of each of the players. When the valuation
functions are additive, the problem becomes a special case of the determinant
maximization and this connection can be utilized to give an $e$-approximation
algorithm [AGSS16]. Other methods including rounding algorithms [CG15, CDG+17]
as well as primal-dual methods [BKV18a] have been utilized to obtain improved
bounds. The problem has been studied when the valuation function is more
general [GHM18, BKV18b, AMGV18, GHV21] and a constant-factor approximation is
known when the valuation function is submodular [LV22].

Other Spectral Objectives. While we focus on the determinant objective, the
problem is also interesting when considering other spectral objectives
including minimizing the trace or the maximum eigenvalue of the
$\left(\sum_{i\in S}\left(v_{i}v_{i}^{\top}\right)\right)^{-1}$. These
problems have been studied for the cardinality constraint [ALSW17, NST19b].
For the case of partition matroid, the problem of maximizing the minimum
eigenvalue is closely related to the Kadison-Singer problem [MSS15].

##  2 Algorithm for Partition Matroid

We first show the algorithm and the analysis for a partition matroid with rank
$d$. This allows us to show the basic ideas without going into the details of
matroid theory. The generalizations to general matroid are quite standard. We
detail them in Section 3.

Consider a partition matroid $\mathcal{M}$ with $d$ partitions
$\mathcal{P}_{1},\ldots,\mathcal{P}_{d}$, where each $\mathcal{P}_{i}$
contains $n_{i}$ vectors $v_{i1},\ldots,v_{in_{i}}\in\mathbb{R}^{d}$. Our goal
is to find a set $S$ which provides a good approximation to the objective

$\displaystyle\max\left\\{\det(\sum_{v\in
S}vv^{\top}):|S|=d,|S\cap\mathcal{P}_{i}|=1\;\forall i\right\\}\,.$

Let $OPT$ denote the optimal solution set. The following theorem is a
specialization of Theorem 1 to the case of partition matroid.

###### Theorem 3

Given a partition matroid $\mathcal{M}$ with $d$ parts, let $OPT$ be the
optimal solution to the determinant maximization problem on $\mathcal{M}$.
Then, there is a polynomial-time deterministic algorithm that outputs a
feasible set $S\in\mathcal{M}$ such that

$\det\left(\sum_{i\in S}v_{i}v_{i}^{\top}\right)\geq
e^{-10d\log(d)}\cdot\det\left(\sum_{i\in OPT}v_{i}v_{i}^{\top}\right).$

###  2.1 Algorithm

We begin by formally defining the exchange graph, the different weight
functions, and then the algorithm which helps establish Theorem 1 for the case
of partition matroids.

######  Definition 1 (Exchange Graph)

Formally, for a subset of vectors $S=\\{v_{1},v_{2},\ldots,v_{d}\\}$ with
$v_{i}\in\mathcal{P}_{i}$ for all $i$, we define the exchange graph of $S$,
denoted by $G(S)$ as a bipartite graph, where the right-hand side consists of
vectors in $S$, i.e., $R=\\{v_{1},v_{2},\ldots,v_{d}\\}$ and the left-hand
side consists of all the vectors
$L=\bigcup_{i=1}^{d}\mathcal{P}_{i}\backslash\\{v_{i}\\}$ (See Figure 1). Each
$v_{i}\in R$ has an edge to every $u\in\mathcal{P}_{i}\backslash\\{v_{i}\\}$,
i.e., all the vectors in the same part as $v_{i}$. The vertices on the left-
hand side have forward edges to every vertex in $S$.

Figure 1: The exchange graph $G(S)$

We define a family of weight functions on the exchange graph. The basic weight
function will be denoted by $w_{0}:A(G(S))\rightarrow\mathbb{R}$ and, in
addition, we define weight functions $w_{i}$ for each $1\leq i\leq d$. To
define these weights, we use the function $f:[d]\rightarrow\mathbb{Z}_{+}$
with $f(i)=2(i!)^{3}$ for each $i>0$.

######  Definition 2 (Weight functions on the Exchange graph)

We first define weight function $w_{0}$. All the backward arcs, from any
$v_{i}\in S$ to every $u_{j}\in\mathcal{P}_{i}\backslash\\{v_{i}\\}$, have
weight $0$. For $u_{j}\in L$, let $u_{j}=\sum_{i=1}^{d}a_{ij}\cdot v_{i}$ be
expression for $u_{j}$ in the basis $S$ where $a_{ij}\in\mathbb{R}$ for each
$i$. Then the forward arc $(u_{j},v_{i})$ has weight
$w_{0}(u_{j},v_{i}):=-\log(|a_{ij}|)$ for each $i\in[d]$ and each $u_{j}\in
L$.

Now we define the weight function $w_{\ell}$ on the arcs for any
$1\leq\ell\leq d$. All backward arcs still have weight $0$ but every forward
edge $(u,v)$ has weight
$w_{\ell}(u,v):=\frac{\log(f(\ell))}{\ell}+w_{0}(u,v)$.

The following lemma gives the intuition behind the weight function $w_{0}$
defined above. It shows that the weight on arc $(u_{i},v_{j})$ exactly
measures the change in the objective when we replace element $v_{i}$ with
$u_{j}$ in $S$. The proof appears in the appendix.

###### Lemma 3

Let $S$ be a solution with $\operatorname{vol}(S)>0$ and $u\not\in S$. Then
for any $v\in S$, we have
$w_{0}(u,v)=-\log\frac{\operatorname{vol}\left(S+u-v\right)}{\operatorname{vol}(S)}$.

While we will be specific about which weight function to use, but if it is not
specified, then we refer to the weight function $w_{0}$.

######  Definition 3 (Cycle Weight)

The weight of a cycle $C$ in $G(S)$ is defined as $w_{0}(C)=\sum_{e\in
C}w_{0}(e)$.

Observe that the weight of a cycle depends only on the weight of the forward
edges as backward edges have a weight $0$.

We want to move from the current set $S$ to a set with higher volume by
exchanging on cycles in $G(S)$. But we want to exchange only on cycles that
satisfy certain nice properties. For this purpose, we define $f$-Violating
Cycles and Minimal $f$-Violating Cycles. The algorithm will always exchange on
a Minimal $f$-Violating Cycle.

######  Definition 4 ($f$-Violating Cycle)

A cycle in $G(S)$ is called an $f$-violating cycle if

$w_{0}(C)<-\log f(|C|/2)\,,$

where $|C|$ is the number of arcs in $C$.

We have the following simple observation regarding $f$-violating cycle.

###### Observation 1

If $C$ is a $f$-violating cycle then $\prod_{(u,v)\in C:u\in L,v\in
R}|a_{uv}|>2\left(\left(\frac{|C|}{2}\right)!\right)^{3}.$

(See appendix A)

######  Definition 5 (Minimal $f$-Violating Cycle)

A cycle $C$ in $G(S)$ is called a minimal $f$-violating cycle if

  * •

$C$ is an $f$-violating cycle, and

  * •

for all cycles $C^{\prime}$ such that $V(C^{\prime})\subset V(C)$,
$C^{\prime}$ is not an $f$-violating cycle.

Note that finding an $f$-violating cycle with $2i$ arcs is equivalent to
finding a negative cycle with $2i$ arcs in $G(S)$ with weights $w_{i}$. We use
the following simple algorithm to find a minimal $f$-violating cycle in $G(S)$
(if one exists), where we iterate on the number of arcs in the cycle.

Algorithm 1 Finding minimal $f$-violating cycle

for $i=1,\ldots,d$ do

if there is a negative cycle $C$ with exactly $2i$ arcs in $G(S)$ with weight
function $w_{i}$ then

Return $C$

end if

end for

The following lemma is immediate. A proof appears in the appendix.

###### Lemma 4

Algorithm 1 finds the minimal $f$-violating cycle in $G(S)$.

After finding a minimal $f$-violating cycle, $C$, we modify the current set
$S$ to $S\Delta C$ and repeat. Observe that $S\Delta C$ is always a feasible
set as it will pick exactly one element from each part. The main idea is that
if $\operatorname{vol}(S)$ is small compared to $\operatorname{vol}(OPT)$,
i.e., $\operatorname{vol}(S)<\operatorname{vol}(OPT)\cdot
e^{-\Omega(d\log(d))}$, then there is always an $f$-violating cycle in $G(S)$
(see Lemma 5). Moreover, if $C$ is a minimal $f$-violating cycle, then
$\operatorname{vol}(S\Delta C)\geq 2\cdot\operatorname{vol}(S)$ (see Lemma 7).
If we initialize $S$ to any solution with non-zero determinant, then the ratio
$\operatorname{vol}(OPT)/\operatorname{vol}(S)$ is at most $2^{4\sigma}$ where
$\sigma$ is the encoding length of our problem input (Chapter 3, Theorem 3.2
[Sch00]). This implies that we need only modify the set $S$ polynomially many
times before $\operatorname{vol}(S)$ becomes greater than
$\operatorname{vol}(OPT)\cdot e^{-O(d\log(d))}$, which gives Theorem 3. Such
an initialization can be obtained by finding a basis of $\mathbb{R}^{d}$ that
picks exactly one vector from each part. As discussed above, this problem can
be solved by the matroid intersection algorithm over the partition matroid and
the linear matroid defined by the vectors.

Algorithm 2 Algorithm to find an approximation to $OPT$

$S\leftarrow$ set with $|S|=d$, $|S\cap\mathcal{P}_{i}|=1$ for all $i$, and
$\operatorname{vol}(S)>0$.

while there exists an $f$-violating cycle in $G(S)$ do

$C=$ minimal $f$-violating cycle in $G(S)$

$S=S\Delta C$

end while

Return $S$

###### Lemma 5

For any set $S$ with $|S|=d$ and $\operatorname{vol}(S)>0$, if
$\operatorname{vol}(S)<\operatorname{vol}(OPT)\cdot e^{-5d\log(d)}$, then
there exists an $f$-violating cycle in $G(S)$.

Proof  Let $OPT=\\{u_{1},u_{2},\ldots,u_{d}\\}$ and
$S=\\{v_{1},v_{2},\ldots,v_{d}\\}$ such that $u_{i},v_{i}\in\mathcal{P}_{i}$
for all $i\in[d]$. Observe that $(v_{i},u_{i})$ is an arc in the exchange
graph for each $i$ since $u_{i}$ and $v_{i}$ belong to the same part333Given
$u_{i}\neq v_{i}$.

Abusing notation slightly, let $T$ and $S$ be matrices whose columns are the
vectors in $OPT$ and $S$, respectively. Let $A$ be the coefficient matrix of
$T$ w.r.t. $S$, i.e., $T=SA^{\top}$. Then

$\displaystyle\operatorname{vol}(OPT)^{2}=\det(TT^{\top})=\det(SA^{\top}AS^{\top})=\det(SS^{\top})\cdot|\det(A)|^{2}.$

Let $X=OPT\backslash S$, $Y=S\backslash OPT$, and $|X|=|Y|=k$. Without loss of
generality, let $Y=\\{v_{1},\ldots,v_{k}\\}$ and $X=\\{u_{1},\ldots,u_{k}\\}$.
Then $A=\begin{bmatrix}A_{k}&A^{\prime}\\\ 0&I_{d-k}\end{bmatrix}$, where
$A_{k}$ is the sub-matrix of $A$ corresponding to rows in $X$ and columns in
$Y$. Then $\det(A)=\det(A_{k})$.

As per the hypothesis in the lemma, we have
$\det(SS^{\top})<\det(TT^{\top})\cdot e^{-10d\log(d)}$. Therefore,

$|\det(A_{k})|>e^{5d\log(d)}\geq e^{5k\log(k)}.$ (1)

By the Leibniz formula, we have
$\det(A_{k})=\sum_{\sigma\in\mathcal{S}_{k}}\mathrm{sign}(\sigma)\prod_{i=1}^{k}a_{i\sigma(i)}$.
Taking absolute values gives
$|\det(A_{k})|\leq\sum_{\sigma\in\mathcal{S}_{k}}\prod_{i=1}^{k}|a_{i\sigma(i)}|$.
Since $|S_{k}|=k!\leq e^{k\log(k)}$, there exists a permutation
$\sigma\in\mathcal{S}_{k}$ such that

$\displaystyle\prod_{i=1}^{k}|a_{i\sigma(i)}|>|\det(A_{k})|\cdot
e^{-k\log(k)}\geq e^{4k\log(k)}.$ (2)

Let the cycle decomposition of this $\sigma$ be
$\sigma=\\{C_{1},C_{2},\ldots,C_{\ell}\\}$. Then each $C_{j}$ corresponds to a
unique cycle in $G(S)$ with $2|C_{j}|$ hops by considering the forward arcs
$(u_{i},v_{\sigma(i)})$ for each $i$ on the cycle and the backward arcs
$(v_{i},u_{i})$ for each $i$ in $C_{j}$. We claim that at least one of these
cycles is an $f$-violating cycle. If not, then by the definition of
$f$-violating cycles, we have $\prod_{i\in C_{j}}|a_{i\sigma(i)}|\leq
2(|C_{j}|!)^{3}$. Multiplying over all cycles in $\sigma$ gives

$\displaystyle\prod_{i=1}^{k}|a_{i\sigma(i)}|=\prod_{j=1}^{\ell}\prod_{i\in
C_{j}}|a_{i\sigma(i)}|<\prod_{j=1}^{\ell}2(|C_{j}|!)^{3}<2^{k}(k!)^{3}<e^{4k\log(k)},$

where the second last inequality follows from $\sum_{j=1}^{\ell}|C_{j}|=k$.
This contradicts eq. 2, so $G(S)$ must contain an $f$-violating cycle. $\Box$

The requirement in Lemma 5 that
$\operatorname{vol}(S)<\operatorname{vol}(OPT)\cdot e^{-5d\log(d)}$ is tight,
up to the coefficient in the exponent. Consider the case where $d$ is a power
of two (or more generally, any $d$ for which a Hadamard matrix of order $d$ is
known to exist), $S=\\{e_{1},\ldots,e_{d}\\}$ consists of the standard basis
vectors, and $L=H=\\{h_{1},\ldots,h_{d}\\}$ consists of the columns of the
$d\times d$ Hadamard matrix. The entries of $H$ are all $\pm 1$, and
$h_{i}^{\top}h_{j}=0$ for $i\neq j$. Then $\operatorname{vol}(S)=1$, and the
optimal solution is $OPT=H$, which has objective value

$\operatorname{vol}(H)=\prod_{i=1}^{d}\|h_{i}\|=d^{d/2}=e^{\frac{d}{2}\log(d)}\cdot\operatorname{vol}(S),$

since the vectors in $H$ are orthogonal. Meanwhile, the exchange matrix in
this case is $A=H^{\top}$. Since all the entries of $A$ are $\pm 1$, we know
that the product of the entries along any cycle will have an absolute value of
$1$. Thus, we cannot find an $f$-violating cycle in the same way, despite the
fact that $\operatorname{vol}(S)\leq\operatorname{vol}(OPT)\cdot
e^{-\frac{d}{2}\log(d)}$.

###  2.2 Cycle Exchange and Determinant

Now we show that exchanging on a minimal $f$-violating cycle $C$ increases the
objective of the output set by at least a factor of two. The proof relies on
two technical lemmas. First, observe that the arc weights given by
$w_{0}(u,v)$ are exactly how much the objective will change if switch from the
solution $S$ to $S+u-v\ $ in the solution. But switching on a cycle will
switch multiple elements at the same time. Since our function
$\operatorname{vol}(.)$ (or more appropriately $\log\operatorname{vol}(.)$) is
not additive, it is not clear what the change in the objective. The following
lemma characterizes exactly how the objective changes when we switch a large
set.

Consider our current solution $S$. Let $C$ be the minimal cycle found and
$\ell=|C|/2$. Let $X=C\cap L$ and $Y=C\cap S$. Thus the output set $T=(S\cup
X)\setminus Y$. We will also abuse notation to let $X,Y$ and $S$ represent the
matrices whose columns are the vectors in their respective sets. Note that $S$
is $d\times d$ while both $X$ and $Y$ are $d\times\ell$. Observe that
$\operatorname{vol}(S)^{2}=\det(SS^{\top})$ and
$\operatorname{vol}(T)^{2}=\det(TT^{\top})=\det(SS^{\top}+XX^{\top}-YY^{\top})$.
Crucially, we show that the matrix consisting of coefficients $a_{uv}$ that
define the weights on the arcs of the exchange graph for $u\in X$ and $v\in Y$
also defines the change in objective value.

###### Lemma 6

Let $S$ be a basis, let $X$ and $Y$ be sets with $|X|=|Y|=\ell$ and
$Y\subseteq S$. Let $A$ be the $\ell\times d$ matrix of coefficients so that
$X=SA^{\top}$, and let $A_{C}$ be the $\ell\times\ell$ submatrix of only the
coefficients corresponding to columns in $Y$. If $T=(S\cup X)\backslash Y$
then
$\operatorname{vol}(T)^{2}=\operatorname{vol}(S)^{2}\cdot\det(A_{C}A_{C}^{\top})$.

Without loss of generality, let $C=(v_{0}\rightarrow u_{1}\rightarrow
v_{1}\rightarrow u_{2}\rightarrow v_{2}\rightarrow\ldots u_{\ell}\rightarrow
v_{0})$ so that $X=\\{u_{1},\ldots u_{\ell}\\}$ and
$Y=\\{v_{1},\ldots,v_{\ell-1},v_{0}\\}$, and order the columns of $A_{C}$
accordingly so that the $\ell$-th column corresponds to $v_{0}$. Observe that
diagonal entries of the $A_{C}$ correspond to coefficient of $v_{i}$ when
expressing $u_{i}$ in basis of $S$ and thus equals $a_{ii}$. $C$ being
$f$-violating implies that the product of the diagonal entries
$\prod_{i=1}^{\ell}|a_{ii}|>f(\ell)$. To show that the volume of $T$ is large,
we need to show $|\det(A_{C})|$ is large. To this end, we utilize crucially
that $C$ is the _minimal_ $f$-violating cycle. Observe that the off-diagonal
entries $a_{ij}$ exactly correspond to the weight on chords of the cycle.
Since each chord introduces a cycle with smaller number of arcs, by minimality
we know that it is not $f$-violating. This allows us to prove upper bounds on
the off-diagonal entries of the matrix $A_{C}$. Finally, a careful argument
allows us to give a lower bound on the determinant of any matrix with such
bounds on the off-diagonal entries. We now expand on the above outline below.

###### Lemma 7

If $C$ is a minimal $f$-violating cycle in $G(S)$, then
$\operatorname{vol}(S\Delta C)\geq 2\cdot\operatorname{vol}(S)$.

Proof  Let $C=(v_{0}\rightarrow u_{1}\rightarrow v_{1}\rightarrow
u_{2}\rightarrow v_{2}\rightarrow\ldots u_{\ell}\rightarrow v_{0})$ where
$v_{i},u_{i+1}$ belong to the same part and $v_{i}\in S$ (See Figure 2).

Figure 2: The cycle $C$

By the Lemma 6, we know that $\operatorname{vol}(S\Delta
C)=\det(A_{C}A_{C}^{\top})^{1/2}\cdot\operatorname{vol}(S)=|\det(A_{C})|\cdot\operatorname{vol}(S)$.
We will index the entries of $A_{C}$ according to the indices of $u_{i}$ and
$v_{j}$ where the last column corresponds to $v_{0}$. Since $C$ has $2\ell$
hops, $A_{C}$ is an $\ell\times\ell$ matrix.

(a) Shortcut when $i<j$

(b) Sub-cycle when $i>j$

Figure 3: Structure when the edge $u_{i}\rightarrow v_{j}$ (in blue) is added

We now bound each entry of the matrix $A_{C}$ in terms of the its diagonal
entries, $a_{i,i}$ for $i=1,\ldots,n$. We show upper bounds on the absolute
value of each entry as a function of the diagonal entries. Consider the
$i,j$-th entry of $A_{C}$. For $i>j$, define the cycle
$C_{i,j}:=(u_{i}\rightarrow v_{j}\rightarrow u_{j+1}\rightarrow
v_{j+1}\rightarrow\ldots v_{i-1}\rightarrow u_{i})$. $C_{i,j}$ is a cycle with
$2(i-j)$ hops and $V(C_{i,j})\subset V(C)$. $C$ being a minimal $f$-violating
cycle implies that $C_{i,j}$ is not an $f$-violating cycle. Therefore,
$e^{-w_{0}(C_{i,j})}=|a_{i,j}|\cdot\prod_{s=j+1}^{i-1}|a_{s,s}|<f(i-j)$. This
implies

$|a_{i,j}|<\frac{f(i-j)}{\prod_{s=j+1}^{i-1}|a_{s,s}|}.$ (3)

Similarly for $j=\ell$, we have
$|a_{i,\ell}|<\frac{f(i)}{\prod_{s=1}^{i-1}|a_{s,s}|}\,.$

For $i<j<\ell$, define $C^{\prime}_{i,j}:=(v_{0}\rightarrow u_{1}\rightarrow
v_{1}\rightarrow\ldots u_{i}\rightarrow v_{j}\rightarrow\ldots
u_{\ell}\rightarrow v_{0})$. Again, $C^{\prime}_{i,j}$ is a cycle with
$2(\ell-j+i)$ hops which is not $f$-violating. Therefore,

$|a_{i,j}|\cdot\prod_{s=1}^{i-1}|a_{s,s}|\cdot\prod_{s=j+1}^{\ell}|a_{s,s}|<f(\ell-j+i).$
(4)

Since $C$ is an $f$-violating cycle, we also have

$\prod_{s=1}^{\ell}|a_{s,s}|>f(\ell).$ (5)

Combining (4) and (5) gives

$\displaystyle|a_{i,j}|$
$\displaystyle<\frac{f(\ell-j+i)}{f(\ell)}\cdot\prod_{s=i}^{j}|a_{s,s}|.$

Let $B_{\ell}$ be the matrix obtained by applying the following operations to
$A_{C}$

  * •

Multiply the last column by $a_{1,1}$ and for $j<\ell$, divide the $j$-th
column by $\prod_{s=2}^{j}a_{s,s}$

  * •

Divide the first row by $a_{1,1}$ and for $i>1$, multiply the $i$-th row by
$\prod_{s=2}^{i-1}a_{s,s}$

  * •

Divide the last column by $f(\ell)$ and, if needed, flip the sign of the last
column so that $a_{\ell,\ell}>0$.

Then $|\det(A_{C})|=f(\ell)\cdot|\det(B_{\ell})|$, and $B_{\ell}$ satisfies
the following properties:

  * •

$b_{i,i}$ = 1 for all $i\in[\ell-1]$, $b_{\ell,\ell}\geq 1$,

  * •

$|b_{i,j}|\leq f(i-j)$ for all $j<i\leq\ell$, and

  * •

$|b_{i,j}|\leq f(\ell-j+i)/f(\ell)$ for all $i<j\leq\ell$.

For $\ell\geq 2$, we have the following claim:

###### Claim 2.1

$\det(B_{2})\geq 0.75$ and $\det(B_{\ell})>0.1$ for all $\ell\geq 3$.

With this claim in hand, it implies that $|\det(A_{C})|>0.1\cdot f(\ell)>2$
for all $\ell\geq 3$. For $\ell=2$, $\det(B_{2})\geq 0.75$, and
$\det(A_{C})\geq 0.75\cdot f(2)>2$. Therefore, $\operatorname{vol}(S\Delta
C)\geq|\det(A_{C})|\cdot\operatorname{vol}(S)\geq
2\cdot\operatorname{vol}(S)$. $\Box$

Proof of Claim 2.1 Consider the following process on $B_{\ell}$:

Algorithm 3 Gaussian Elimination Process (Column Operations)

for $s=1,\ldots,\ell$ do $\triangleright$Outer Loop

for $j=s+1,\ldots,\ell$ do $\triangleright$Inner Loop

$b_{:,j}=b_{:,j}-b_{:,s}\cdot\frac{b_{s,j}}{b_{s,s}}$

end for

end for

Note that $\det(B_{2})\geq 0.75$, $\det(B_{3})\geq 0.73$, and $\det(B_{4})\geq
0.83$ (see the end of the Appendix). From hereafter, we will assume that
$\ell\geq 5$.

The output of the Algorithm 3 is a lower triangular matrix. Let $b_{i,j}(s)$
denote the value of $b_{i,j}$ before the $s$-th iteration of the outer loop of
Gaussian Elimination. For example, $b_{i,j}(1)=b_{i,j}$ for all $i,j$.

For any $i<j$, $b_{i,j}$ becomes $0$ at the end of the $i$-th iteration of the
outer loop of the algorithm, and does not change after that. So, the final
value of $b_{i,j}$, before it becomes $0$, is $b_{i,j}(i)$. Similarly, for
$i\geq j$, the value of $b_{i,j}$ does not change after the $(j-1)$-th
iteration of the outer loop, and therefore the final value of $b_{i,j}$, i.e.,
$b_{i,j}(\ell)$ satisfies $b_{i,j}(\ell)=b_{i,j}(j)$.

Since this process does not change the determinant of $B_{\ell}$, we have
$\det(B_{\ell})=\prod_{j=1}^{\ell}b_{j,j}(j)$. By Lemma 8,
$b_{j,j}(j)>1-0.92/\ell$ for $j<\ell$ and $b_{\ell,\ell}(\ell)>0.303$.
Therefore,

$\displaystyle\det(B_{\ell})=\prod_{j=1}^{\ell}b_{j,j}(j)\geq\left(1-\frac{0.92}{\ell}\right)^{\ell-1}\cdot
0.303\,.$

The function $\left(1-\frac{0.92}{\ell}\right)^{\ell-1}$ is a decreasing
function of $\ell$, but has a horizontal asymptote at $\sim 0.39$. Thus,
$\left(1-\frac{0.92}{\ell}\right)^{\ell-1}\geq 0.39$ and this gives

$\det(B_{\ell})>0.39\times 0.303>0.1\,.$

$\Box$

###### Lemma 8

For $\ell\geq 5$, the final values of entries of $B_{\ell}$ after Algorithm 3
are bounded as follows:

  1. 1.

$|b_{i,j}(j)|<\binom{i}{j}\cdot f(i-j)$ for $1<j<i$,

  2. 2.

$|b_{i,j}(i)|<1.5\cdot f(\ell-j+i)/f(\ell)$ for $i<j<\ell$,

  3. 3.

$|b_{i,\ell}(i)|<2.84\cdot f(i)/f(\ell)$ for $i<\ell$,

  4. 4.

$b_{j,j}(j)>1-\frac{0.92}{\ell}$ for all $j<\ell$,

  5. 5.

$b_{\ell,\ell}(\ell)>0.303$ .

Proof  We will prove the lemma by induction on $j$, the column index. Note
that Algorithm 3 does not change the values of the first column of $B_{\ell}$,
and it also does not change the values of the first row of $B_{\ell}$ before
they become $0$. So, the bounds are trivially true for the first column and
the first row.

For $i\geq j$,

$b_{i,j}(j)=b_{i,j}(1)-\sum_{s=1}^{j-1}b_{i,s}(s)\cdot\frac{b_{s,j}(s)}{b_{s,s}(s)}\,.$
(6)

Taking absolute values gives

$|b_{i,j}(j)-b_{i,j}(1)|\leq\sum_{s=1}^{j-1}|b_{i,s}(s)|\cdot\frac{|b_{s,j}(s)|}{|b_{s,s}(s)|}\,.$
(7)

The induction hypothesis implies that for all $s<j$,
$|b_{i,s}(s)|<\binom{i}{s}\cdot f(i-s)$, $|b_{s,j}(s)|<1.5\cdot
f(\ell-j+s)/f(\ell)$, and $b_{s,s}(s)>1-0.92/\ell\geq 0.816$ (since $\ell\geq
5$). Plugging these bounds in (7), we get

$\displaystyle|b_{i,j}(j)-b_{i,j}(1)|$
$\displaystyle<\frac{1.5}{0.816}\cdot\sum_{s=1}^{j-1}\binom{i}{s}\cdot
f(i-s)\cdot\frac{f(\ell-j+s)}{f(\ell)}\,.$ (8)

Note that

$\frac{f(i-s)\cdot f(\ell-j+s)}{f(i-j)\cdot
f(\ell)}=\frac{((i-s)!)^{3}\cdot((\ell-j+s)!)^{3}}{((i-j)!)^{3}\cdot(\ell!)^{3}}=\left(\frac{\binom{\ell+i-j}{\ell}}{\binom{\ell+i-j}{i-s}}\right)^{3}\,.$

For any $1\leq s\leq j-1$,
$\frac{\binom{\ell+i-j}{\ell}}{\binom{\ell+i-j}{i-s}}\leq\frac{(i-j+1)}{\ell}$.
Therefore,

$\displaystyle\frac{f(i-s)\cdot f(\ell-j+s)}{f(i-j)\cdot f(\ell)}$
$\displaystyle\leq\frac{\binom{\ell+i-j}{\ell}}{\binom{\ell+i-j}{i-s}}\cdot\frac{(i-j+1)^{2}}{\ell^{2}}\,.$

Plugging this in (8) gives

$\displaystyle|b_{i,j}(j)-b_{i,j}(1)|$ $\displaystyle\leq
f(i-j)\left(1.84\cdot\frac{(i-j+1)^{2}}{\ell^{2}}\cdot\sum_{s=1}^{j-1}\binom{i}{s}\cdot\frac{\binom{\ell+i-j}{\ell}}{\binom{\ell+i-j}{i-s}}\right)$
$\displaystyle\leq
f(i-j)\left(1.84\cdot\frac{(i-j+1)^{2}}{\ell^{2}}\cdot\frac{i!\binom{\ell+i-j}{\ell}}{(\ell+i-j)!}\sum_{s=1}^{j-1}\frac{(\ell-j+s)!}{s!}\right)$
$\displaystyle=f(i-j)\left(1.84\cdot\frac{(i-j+1)^{2}}{\ell^{2}}\cdot\frac{i!\binom{\ell+i-j}{\ell}(\ell-j)!}{(\ell+i-j)!}\sum_{s=1}^{j-1}\binom{\ell-j+s}{\ell-j}\right)$
$\displaystyle=f(i-j)\left(1.84\cdot\frac{(i-j+1)^{2}}{\ell^{2}}\cdot\frac{i!(\ell-j)!}{\ell!(i-j)!}\sum_{s=1}^{j-1}\binom{\ell-j+s}{\ell-j}\right)\,.$
(9)

For positive integers $a,b,x$ with $x\leq a\leq b$,

$\binom{a}{x}+\binom{a+1}{x}+\binom{a+2}{x}+\ldots+\binom{b}{x}=\binom{b+1}{x+1}-\binom{a}{x-1}\,.$
(10)

Using (10) with $a=\ell-j+1$, $b=\ell-1$, and $x=\ell-j$ gives
$\sum_{s=1}^{j-1}\binom{\ell-j+s}{\ell-j}\leq\binom{\ell}{\ell-j+1}$ and from
(9),

$\displaystyle|b_{i,j}(j)-b_{i,j}(1)|$ $\displaystyle\leq
f(i-j)\left(1.84\cdot\frac{(i-j+1)^{2}}{\ell^{2}}\cdot\frac{i!(\ell-j)!}{(i-j)!\ell!}\cdot\binom{\ell}{\ell-j+1}\right)$
$\displaystyle=f(i-j)\left(1.84\cdot\binom{i}{j}\cdot\frac{(i-j+1)^{2}j}{\ell^{2}(\ell-j+1)}\right)$
(11) $\displaystyle\leq
f(i-j)\left(1.84\cdot\binom{i}{j}\cdot\frac{(\ell-j+1)j}{\ell^{2}}\right).$
(12)

Since $(\ell-j+1)j$ is maximized at $j=(\ell+1)/2$, we have
$\frac{(\ell-j+1)j}{\ell^{2}}\leq\frac{(\ell+1)^{2}}{4\ell^{2}}\leq 0.36$ for
any $\ell\geq 5$.

Plugging this in (12) gives

$\displaystyle|b_{i,j}(j)|$ $\displaystyle\leq|b_{i,j}(j)|+f(i-j)\cdot
0.6624\cdot\binom{i}{j}\leq f(i-j)\left(1+0.6624\cdot\binom{i}{j}\right).$

Now we will restrict ourselves to the case when $i>j$. For $i=2$, $j$ can only
be $1$ and this corresponds to an entry in the first column for which the
bounds are trivially true. So, we only need to consider $i\geq 3$. Since
$1\leq j<i$, we have $\binom{i}{j}\geq i$. Furthermore, since $\ell\geq 5$ and
$i\geq 3$, we have $1\leq 0.3376\cdot i<0.3376\binom{i}{j}$. This gives

$\displaystyle|b_{i,j}(j)|$ $\displaystyle\leq
f(i-j)\left(0.3376\cdot\binom{i}{j}+0.6624\cdot\binom{i}{j}\right)\leq
f(i-j)\cdot\binom{i}{j}.$

This concludes the proof of part 1.

For $j>i$, we have

$|b_{i,j}(i)-b_{i,j}(1)|\leq\sum_{s=1}^{i-1}|b_{i,s}(s)|\cdot\frac{|b_{s,j}(s)|}{|b_{s,s}(s)|}\,.$
(13)

By the induction hypothesis, $|b_{s,j}(s)|<1.5\cdot f(\ell-j+s)/f(\ell)$,
$|b_{i,s}(s)|<\binom{i}{s}\cdot f(i-s)$, and $b_{s,s}(s)>1-0.92/\ell\geq
0.816$. Plugging these bounds in (13), we get

$\displaystyle|b_{i,j}(i)-b_{i,j}(1)|$
$\displaystyle<\frac{1.5}{0.816}\sum_{s=1}^{i-1}\frac{f(\ell-j+s)}{f(\ell)}\cdot\binom{i}{s}\cdot
f(i-s).$ (14)

Note that $\frac{f(\ell-j+s)\cdot
f(i-s)}{f(\ell-j+i)}=\frac{2((\ell-j+s)!)^{3}\cdot((i-s)!)^{3}}{((\ell-j+i)!)^{3}}=2\cdot\left(\frac{1}{\binom{\ell-j+i}{i-s}}\right)^{3}$.
For any $1\leq s\leq i-1$,
$\frac{1}{\binom{\ell-j+i}{i-s}}\leq\frac{1}{\ell-j+i}$. Therefore,

$\displaystyle\frac{f(\ell-j+i-s)\cdot
f(s)}{f(\ell-j+i)}\leq\frac{1}{\binom{\ell-j+i}{i-s}}\cdot\frac{2}{(\ell-j+i)^{2}}\,.$

Plugging this in (14) gives

$\displaystyle|b_{i,j}(i)-b_{i,j}(1)|$
$\displaystyle\leq\frac{f(\ell-j+i)}{f(\ell)}\cdot\frac{3.68}{(\ell-j+i)^{2}}\cdot\left(\sum_{s=1}^{i-1}\binom{i}{s}\cdot\frac{1}{\binom{\ell-j+i}{i-s}}\right)$
$\displaystyle=\frac{f(\ell-j+i)}{f(\ell)}\cdot\frac{3.68\cdot
i!(\ell-j)!}{(\ell-j+i)^{2}\cdot(\ell-j+i)!}\cdot\sum_{s=1}^{i-1}\binom{\ell-j+s}{\ell-j}\,.$

Using (10) again, we get
$\sum_{s=1}^{i-1}\binom{\ell-j+s}{\ell-j}\leq\binom{\ell-j+i}{\ell-j+1}$ and
this gives

$\displaystyle|b_{i,j}(i)-b_{i,j}(i)|$
$\displaystyle\leq\frac{f(\ell-j+i)}{f(\ell)}\cdot\frac{3.68\cdot
i!(\ell-j)!}{(\ell-j+i)^{2}\cdot(\ell-j+i)!}\cdot\binom{\ell-j+i}{\ell-j+1}$
$\displaystyle=\frac{f(\ell-j+i)}{f(\ell)}\cdot\frac{3.68\cdot
i}{(\ell-j+i)^{2}\cdot(\ell-j+1)}\,.$ (15)

The function $\frac{i}{(\ell-j+i)^{2}}$ is maximized at $i=\ell-j$. So for any
$j<\ell$, we have

$\displaystyle|b_{i,j}(i)-b_{i,j}(1)|$
$\displaystyle\leq\frac{f(\ell-j+i)}{f(\ell)}\cdot\frac{3.68}{4(\ell-j)\cdot(\ell-j+1)}\leq
0.5\cdot\frac{f(\ell-j+i)}{f(\ell)}.$

Using the fact that $|b_{i,j}(1)|\leq f(\ell-j+i)/f(\ell)$, we have
$|b_{i,j}(i)|\leq 1.5\cdot f(\ell-j+i)/f(\ell)$ for $i<j<\ell$.

For $j=\ell$ and $i\geq 2$, equation (15) gives

$\displaystyle|b_{i,\ell}(i)-b_{i,\ell}(1)|$
$\displaystyle\leq\frac{f(i)}{f(\ell)}\cdot\frac{3.68}{i}\leq
1.84\cdot\frac{f(i)}{f(\ell)},$

and therefore $|b_{i,\ell}(i)|\leq 2.84\cdot\frac{f(i)}{f(\ell)}$. This
concludes the proof of parts 2 and 3.

For $i=j$ and $j<\ell$, using (11), we get

$\displaystyle|b_{j,j}(j)-1|\leq\frac{1.84\cdot
j}{\ell^{2}(\ell-j+1)}\leq\frac{1.84\cdot(\ell-1)}{2\ell^{2}}\leq\frac{0.92}{\ell}.$

For $i=j=\ell$, by (8) and the induction hypothesis,

$\displaystyle|b_{\ell,\ell}(\ell)-b_{\ell,\ell}(1)|$
$\displaystyle<\frac{2.84}{1-0.92/\ell}\sum_{s=1}^{\ell-1}\binom{\ell}{s}\cdot
f(\ell-s)\cdot\frac{f(s)}{f(\ell)}\,.$

Following the proof outline of equation (11) gives
$|b_{\ell,\ell}(\ell)-b_{\ell,\ell}(1)|\leq\frac{2.84}{0.816}\cdot\frac{1}{\ell}\leq
0.697$. Since $b_{\ell,\ell}(1)\geq 1$, we have $b_{\ell,\ell}(\ell)\geq
b_{\ell,\ell}(1)-0.697\geq 0.303$. $\Box$

##  3 Update Step for General Matroids

Consider the case when $\mathcal{M}=([n],\mathcal{I})$ is a general matroid of
rank $d$. When we exchange on a cycle $C$ and update $S\leftarrow S\Delta C$,
the resulting set is guaranteed to be independent in the linear matroid
because of the determinant bounds in Lemma 7, but it is not clear that it
would be independent in the general constraint matroid, $\mathcal{M}$, when
$\mathcal{M}$ is not a partition matroid. However, by exchanging on a minimal
$f$-violating cycle in our algorithm, we can make the same guarantee.

In this section, we prove the existence of an $f$-violating cycle for any
matroid $\mathcal{M}$ with rank $d$ when the current basis $S$ is sufficiently
smaller in volume than the optimal solution $OPT$. We also prove that
exchanging on a minimal $f$-violating cycle preserves independence in
$\mathcal{M}$.

###### Theorem 4

For any basis $S$ with $|S|=d$ and $\operatorname{vol}(S)>0$, if
$\operatorname{vol}(S)<\operatorname{vol}(OPT)\cdot e^{-5d\log(d)}$, then
there exists an $f$-violating cycle in $G(S)$.

Proof  Since $S$ and $OPT$ are independent and $|S|=|OPT|$, there exists a
perfect matching between $OPT\backslash S$ and $S\backslash OPT$ using the
backward arcs in $G(S)$ (Chapter 39, Corollary 39.12a, [Sch03]). Let
$X=OPT\backslash S$, $Y=S\backslash OPT$, and $|X|=|Y|=k$. Without loss of
generality, let $Y=\\{v_{1},\ldots,v_{k}\\}$ and $X=\\{u_{1},\ldots,u_{k}\\}$
such that $(v_{i}\rightarrow u_{i})$ is an arc in $G(S)$ for all $i\in[k]$.

Let $T$ and $S$ be matrices whose columns are the vectors in $OPT$ and $S$,
respectively. Let $A$ be the coefficient matrix of $T$ w.r.t. $S$, i.e.,
$T=SA^{\top}$. Then $A=\begin{bmatrix}A_{k}&A^{\prime}\\\
0&I_{d-k}\end{bmatrix}$, where $A_{k}$ is the sub-matrix of $A$ corresponding
to rows in $X$ and columns in $Y$. Then by the same proof as in 5, there
exists a permutation $\sigma\in\mathcal{S}_{k}$ such that

$\displaystyle\prod_{i=1}^{k}|a_{i\sigma(i)}|>|\det(A)|\cdot e^{-k\log(k)}\geq
e^{4k\log(k)}\,.$ (16)

Let the cycle decomposition of $\sigma$ be
$\sigma=\\{C_{1},C_{2},\ldots,C_{\ell}\\}$ where $C_{i}=(i_{1}\rightarrow
i_{2}\rightarrow\ldots i_{j}\rightarrow i_{1})$. Since there is an edge from
$v_{\sigma(j)}$ to $u_{\sigma(j)}$ for all $j$, every cyclic permutation
$C_{i}$ corresponds to a cycle $(u_{i_{1}}\rightarrow v_{i_{2}}\rightarrow
u_{i_{2}}\rightarrow v_{i_{3}}\ldots\rightarrow u_{i_{j}}\rightarrow
v_{i_{1}}\rightarrow u_{i_{1}})$ in $G(S)$. We claim that at least one of
these cycles is an $f$-violating cycle. If not, then by the definition of
$f$-violating cycles, we have $\prod_{i\in C_{j}}|a_{i\sigma(i)}|\leq
2(|C_{j}|!)^{3}$ for all $j\leq\ell$. Multiplying over all the cycles in
$\sigma$ gives

$\displaystyle\prod_{i=1}^{k}|a_{i\sigma(i)}|=\prod_{j=1}^{\ell}\prod_{i\in
C_{j}}|a_{i\sigma(i)}|\leq\prod_{j=1}^{\ell}2(|C_{j}|!)^{3}<e^{4k\log(k)},$

where the last inequality follows from $\sum_{j=1}^{\ell}|C_{j}|=k$. This
contradicts (16), so $G(S)$ must contain an $f$-violating cycle. $\Box$

###### Lemma 9

If $C$ is a minimal $f$-violating cycle in $G(S)$, then $S\Delta C$ is
independent in $\mathcal{M}$.

Proof  For clarity, let $V(C)$ denote the vertex set of $C$. Let $T:=S\Delta
V(C)$ and let $|C|=2\ell$. Lets consider the graph $G(S)$ with weights
$w_{\ell}$, and define $w_{\ell}(D):=\sum_{e\in D}w_{\ell}(e)$ for any cycle
$D$. Since $C$ is an $f$-violating cycle,
$w_{\ell}(C)=w_{0}(C)+\log(f(\ell))<0$.

Let the set of backward arcs in $C$ be $N_{1}$, and the set of forward arcs be
$N_{2}$. For the sake of contradiction, assume that $T\notin\mathcal{I}$.
Then, there exists a matching $N_{1}^{\prime}$ on $V(C)$ consisting of only
backward arcs such that $N_{1}\neq N_{1}^{\prime}$ (Chapter 39, Theorem 39.13,
[Sch03]). Let $A$ be a multiset of arcs consisting of all arcs in $N_{2}$
twice and all arcs $N_{1}$ and $N_{1}^{\prime}$ (with arcs in $N_{1}\cap
N_{1}^{\prime}$ appearing twice). Consider the directed graph $D=(V(C),A)$.
Since $N_{1}\neq N_{1}^{\prime}$, $D$ contains a directed circuit $C_{1}$ with
$V(C_{1})\subsetneq V(C)$. Every vertex in $V(C)$ has exactly two in-edges and
two out-edges in $A$. Therefore, $D$ is Eulerian, and we can decompose $A$
into directed circuits $C_{1},\ldots,C_{k}$. Since only arcs in $N_{2}$ have
non-zero weights, we have $\sum_{i=1}^{k}w_{\ell}(C_{i})=2w_{\ell}(C)$.

Because $V(C_{1})\subsetneq V(C)$, at most one cycle $C_{j}$ can have
$V(C_{j})=V(C)$. If for some $j$, $V(C)=V(C_{j})$, then
$w_{\ell}(C_{j})=w_{\ell}(C)$ as $C_{j}$ must contain every edge in $N_{2}$.
So, $\sum_{i\neq j}w_{\ell}(C_{i})=w_{\ell}(C)<0$ and there exists a cycle
$C_{i}$ such that $V(C_{i})\subsetneq V(C)$ and $w_{\ell}(C_{i})<0$. Otherwise
$V(C_{j})\subsetneq V(C^{\prime})$ for all $j$ and
$\sum_{i}w_{\ell}(C_{i})=2w_{\ell}(C)<0$. Again, there exists a cycle $C_{i}$
such that $V(C_{i})\subsetneq V(C)$ and $w_{\ell}(C_{i})<0$.

Let $C^{\prime}$ be the directed cycle such that $V(C^{\prime})\subsetneq
V(C)$ and $w_{\ell}(C^{\prime})\leq w_{\ell}(C)\leq 0$. Define
$y:=|C^{\prime}|/2$. Thus
$w_{\ell}(C^{\prime})=y\cdot\log(f(\ell))/\ell+w_{0}(C^{\prime})<0$. Since
$y<\ell$, $\log(f(y))/y\leq\log(f(\ell))/\ell$. Therefore
$w_{0}(C^{\prime})\leq-y\cdot\log(f(\ell))/\ell\leq-\log(f(y))$. So
$C^{\prime}$ is an $f$-violating cycle with $V(C^{\prime})\subset V(C)$, which
contradicts the fact that $C$ is a minimal $f$-violating cycle. $\Box$

##  4 Acknowledgements

Adam Brown and Mohit Singh were supported in part by NSF CCF-2106444 and NSF
CCF-1910423. Adam Brown was also supported by an ACO-ARC Fellowship. Aditi
Laddha was supported in part by a Microsoft fellowship and NSF awards
CCF-2007443 and CCF-2134105. Madhusudhan Pittu is supported in part by NSF
awards CCF-1955785 and CCF-2006953. Prasad Tetali was supported in part by the
NSF grant DMS-2151283.

## References

  * [AG17] Nima Anari and Shayan Oveis Gharan.  A generalization of permanent inequalities and applications in counting and optimization.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 384–396. ACM, 2017.
  * [AGSS16] Nima Anari, Shayan Oveis Gharan, Amin Saberi, and Mohit Singh.  Nash social welfare, matrix permanent, and stable polynomials.  In Proceedings of Conference on Innovations in Theoretical Computer Science, 2016.
  * [AGV18] Nima Anari, Shayan Oveis Gharan, and Cynthia Vinzant.  Log-concave polynomials, entropy, and a deterministic approximation algorithm for counting bases of matroids.  In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 35–46. IEEE, 2018.
  * [ALGV19] Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant.  Log-concave polynomials ii: high-dimensional walks and an fpras for counting bases of a matroid.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 1–12. ACM, 2019.
  * [ALSW17] Zeyuan Allen-Zhu, Yuanzhi Li, Aarti Singh, and Yining Wang.  Near-optimal discrete optimization for experimental design: A regret minimization approach.  arXiv preprint arXiv:1711.05174, 2017.
  * [AMGV18] Nima Anari, Tung Mai, Shayan Oveis Gharan, and Vijay V Vazirani.  Nash social welfare for indivisible items under separable, piecewise-linear concave utilities.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2274–2290. SIAM, 2018.
  * [BKV18a] Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish.  Finding fair and efficient allocations.  In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 557–574. ACM, 2018.
  * [BKV18b] Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish.  Greedy algorithms for maximizing nash social welfare.  In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pages 7–13. International Foundation for Autonomous Agents and Multiagent Systems, 2018.
  * [Bre90] Francesco Brenti.  Unimodal polynomials arising from symmetric functions.  Proceedings of the American Mathematical Society, 108(4):1133–1141, 1990.
  * [CDG+17] Richard Cole, Nikhil Devanur, Vasilis Gkatzelis, Kamal Jain, Tung Mai, Vijay V Vazirani, and Sadra Yazdanbod.  Convex program duality, fisher markets, and nash social welfare.  In Proceedings of the 2017 ACM Conference on Economics and Computation, pages 459–460, 2017.
  * [CG15] Richard Cole and Vasilis Gkatzelis.  Approximating the nash social welfare with indivisible items.  In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 371–380, 2015.
  * [CKM+16] Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang.  The unreasonable fairness of maximum nash welfare.  In Proceedings of the 2016 ACM Conference on Economics and Computation, EC ’16, pages 305–322, New York, NY, USA, 2016. ACM.
  * [Com74] Louis Comtet.  Advanced combinatorics, enlarged ed., d, 1974.
  * [ESV17] Javad B Ebrahimi, Damian Straszak, and Nisheeth K Vishnoi.  Subdeterminant maximization via nonconvex relaxations and anti-concentration.  In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 1020–1031. Ieee, 2017.
  * [GHM18] Jugal Garg, Martin Hoefer, and Kurt Mehlhorn.  Approximating the nash social welfare with budget-additive valuations.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2326–2340. SIAM, 2018.
  * [GHV21] Jugal Garg, Edin Husić, and László A Végh.  Approximating nash social welfare under rado valuations.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1412–1425, 2021.
  * [Kha96] Leonid G Khachiyan.  Rounding of polytopes in the real number model of computation.  Mathematics of Operations Research, 21(2):307–320, 1996.
  * [KT12] Alex Kulesza and Ben Taskar.  Determinantal point processes for machine learning.  Foundations and Trends® in Machine Learning, 5(2–3):123–286, 2012.
  * [LV22] Wenzheng Li and Jan Vondrák.  A constant-factor approximation algorithm for nash social welfare with submodular valuations.  In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 25–36. IEEE, 2022.
  * [LZ21] Lap Chi Lau and Hong Zhou.  A local search framework for experimental design.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1039–1058. SIAM, 2021.
  * [MNST20] Vivek Madan, Aleksandar Nikolov, Mohit Singh, and Uthaipon Tantipongpipat.  Maximizing determinants under matroid constraints.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 565–576. IEEE, 2020.
  * [MSS15] Adam W Marcus, Daniel A Spielman, and Nikhil Srivastava.  Interlacing families ii: Mixed characteristic polynomials and the kadison—singer problem.  Annals of Mathematics, pages 327–350, 2015.
  * [MSTX19] Vivek Madan, Mohit Singh, Uthaipon Tantipongpipat, and Weijun Xie.  Combinatorial algorithms for optimal design.  In Conference on Learning Theory, pages 2210–2258, 2019.
  * [Nik15a] Aleksandar Nikolov.  Randomized rounding for the largest simplex problem.  In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, pages 861–870. ACM, 2015.
  * [Nik15b] Aleksandar Nikolov.  Randomized rounding for the largest simplex problem.  In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, pages 861–870. ACM, 2015.
  * [NS16] Aleksandar Nikolov and Mohit Singh.  Maximizing determinants under partition constraints.  In ACM symposium on Theory of computing, pages 192–201, 2016.
  * [NST19a] Aleksandar Nikolov, Mohit Singh, and Uthaipon Tao Tantipongpipat.  Proportional volume sampling and approximation algorithms for A-optimal design.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1369–1386. SIAM, 2019.
  * [NST19b] Aleksandar Nikolov, Mohit Singh, and Uthaipon Tao Tantipongpipat.  Proportional volume sampling and approximation algorithms for a-optimal design.  Proceedings of SODA 2019, 2019.
  * [Puk06] Friedrich Pukelsheim.  Optimal design of experiments.  SIAM, 2006.
  * [Sch00] Alexander Schrijver.  Theory of Linear and Integer Programming.  Wiley-Interscience, 2000.
  * [Sch03] Alexander Schrijver.  Combinatorial optimization: polyhedra and efficiency, volume 24.  Springer Science & Business Media, 2003.
  * [SEFM15] Marco Di Summa, Friedrich Eisenbrand, Yuri Faenza, and Carsten Moldenhauer.  On largest volume simplices and sub-determinants.  In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 315–323. Society for Industrial and Applied Mathematics, 2015.
  * [SX18] Mohit Singh and Weijun Xie.  Approximate positive correlated distributions and approximation algorithms for D-optimal design.  In Proceedings of SODA, 2018.

##  Appendix A Omitted Proofs

Proof of Lemma 3 Recall the statement of the Lemma: Let $S$ be a solution with
$\operatorname{vol}(S)>0$ and $u\not\in S$. Then for any $v\in S$, we have
$w_{0}(u,v)=-\log\frac{\operatorname{vol}(S+u-v)}{\operatorname{vol}(S)}$.
Let $S=\\{v_{1},\ldots,v_{d}\\}$ so that $v=v_{1}$ and write
$u=\sum_{i=1}^{d}a_{i}v_{i}$. We can also write
$v=v^{\perp}+\sum_{i=2}^{d}b_{i}v_{i}$ where $v^{\perp}$ is orthogonal to
$S\backslash\\{v\\}$. Then
$u=a_{1}v^{\perp}+\sum_{i=2}^{d}(a_{1}b_{i}+a_{i})v_{i}$. For
$X\subseteq\mathbb{R}^{d}$ with $|X|=k\leq d$, let $\operatorname{vol}(X)$
denote the $k$-dimensional volume of the parallelepiped spanned by $X$. Then

$\operatorname{vol}(S)=\operatorname{vol}(S-v)\cdot\|v^{\perp}\|,$

while

$\operatorname{vol}(S+u-v)=\operatorname{vol}(S-v)\cdot|a_{1}|\|v^{\perp}\|,$

since the change in volume from adding a single new vector is proportional to
the length of the component of that vector which is orthogonal to our current
set. Thus

$-\log\frac{\operatorname{vol}(S+u-v)}{\operatorname{vol}(S)}=-\log\frac{\operatorname{vol}(S-v)\cdot|a_{uv}|\|v^{\perp}\|}{\operatorname{vol}(S-v)\cdot\|v^{\perp}\|}=-\log|a_{uv}|.$

$\Box$

Proof of Observation 1 Recall the statement of the Observation: If $C$ is a
$f$-violating cycle then $\prod_{(u,v)\in C:u\in L,v\in
R}|a_{uv}|>2(|C|/2!)^{3}$.
If $C$ is $f$-violating then $\ell(C)<-\log f(|C|/2)$, where $\ell(C)$ is the
sum of the $w_{0}$ edge weights in $C$, and $f(|C|/2)=2((|C|/2)!)^{3}$. Note
that $|C\cap R|=|C\cap L|=|C|/2$, so $f(|C/2|)=2(|C\cap R|!)^{3}$. By
expanding $\ell(C)$ we see that

$\displaystyle\ell(C)$ $\displaystyle=\sum_{(u,v)\in C:u\in L,v\in
R}w_{0}(u,v)$ $\displaystyle=-\log\left(\prod_{(u,v)\in C:u\in L,v\in
R}|a_{uv}|\right).$

Since $\ell(C)<-\log f(|C|/2)$, we can take the exponential to remove the
logarithms and attain the desired inequality. $\Box$

Proof of Lemma 4 Recall the statement of the Lemma: Algorithm 1 finds the
minimal $f$-violating cycle in $G(S)$, if one exists.
In the $i$th iteration of Algorithm 1 we determine if there is a negative
cycle in $G(S)$ with weights $w_{i}$ and $2i$ hops, as follows. For each
vertex of $G(S)$, we start an instance of Bellman-Ford (See Chapter 8, Section
8.3, [Sch03]) with that vertex as the root, and proceed for $2i$ iterations.
For source $u$, after $2i$ iterations, we check whether the distance from $u$
to $u$ is negative. If so, we have found a negative cycle with at most $2i$
hops. Note that for weights $w_{i}$, any negative cycle with at most $2i$ hops
is an $f$-Violating cycle. Since the $(i-1)$-th iteration of the algorithm
ensured that there are no $f$-Violating cycles with at most $2(i-1)$ hops, a
negative cycle in the $i$-th iteration (if any) must have exactly $2i$ hops.

Suppose there is an $f$-violating cycle $C$ in $G(S)$, so that $\ell=|C|/2$.
Then, with weight $w_{\ell}$, the total weight of the cycle $C$ is

$w_{\ell}(C)=\sum_{(u,v)\in C}w_{\ell}(u,v)=\sum_{(u,v)\in
C}\log(f(\ell))/\ell+w_{0}(u,v)=\log f(\ell)+w_{0}(C).$

Since $C$ is $f$-violating we know that $\log f(\ell)<-w_{0}(C)$, so the above
calculation shows that $C$ has negative total weight with weights $w_{\ell}$.
This guarantees that Algorithm 1 will return an $f$-violating cycle whenever
one exists.

Now suppose that $C$ is the cycle returned by Algorithm 1 and we must show
that $C$ is minimal $f$-violating. Let $C^{\prime}$ be another cycle such that
$V(C^{\prime})\subset V(C)$. Then $C^{\prime}$ has fewer hops than $C$, but it
was not returned in iteration $|C^{\prime}|/2$, so we know that $C^{\prime}$
must not be $f$-violating. Thus $C$ is indeed minimal. $\Box$

Proof of Lemma 6 Recall the statement of the Lemma 6: Let $S$ be a basis, let
$X$ and $Y$ be sets with $|X|=|Y|=\ell$ and $Y\subseteq S$. Let $A$ be the
$\ell\times d$ matrix of coefficients so that $X=SA^{\top}$, and let $A_{C}$
be the $\ell\times\ell$ submatrix of only the coefficients corresponding to
columns in $Y$. If $T=(S\cup X)\backslash Y$ then
$\operatorname{vol}(T)^{2}=\operatorname{vol}(S)^{2}\cdot\det(A_{C}A_{C}^{\top})$.

We will abuse notation slightly to let $S,X,Y$ also denote the matrices with
columns from their respective sets. Order the columns of $S$ so that $Y$ makes
up the first $\ell$ columns of $S$. Let $A^{\prime}$ be the
$\ell\times(d-\ell)$ submatrix of $A$ consisting of the remaining columns not
already in $A_{C}$. Then

$T=S\begin{bmatrix}A_{C}&A^{\prime}\\\ 0&I_{d-\ell}\end{bmatrix}^{\top},$

which implies that

$\det(T)=\det(S)\cdot\det(A_{C}).$

$\Box$

Bounds on $\det(B_{2})$, $\det(B_{3})$, $\det(B_{4})$ mentioned in Proof of
Claim 2.1:

For $\ell=2$, $b_{1,1}(1)=1$, $|b_{1,2}(1)|\leq 0.125$, $|b_{2,1}(1)|\leq 2$,
and $|b_{2,2}(2)|\geq 0.75$.

$\det(B_{2})\geq\prod_{i=1}^{2}b_{i,i}(i)\geq 0.75.$

The bounds on final values of $B_{3}$ are:

$b_{1,1}(1)=1$ | $|b_{1,2}(1)|\leq 0.0371$ | $|b_{1,3}(1)|\leq 0.00463$
---|---|---
$|b_{2,1}(1)|\leq 2.0$ | $b_{2,2}(2)\geq 0.92$ | $|b_{2,3}(2)|\leq 0.0463$
$|b_{3,1}(1)|\leq 16.0$ | $|b_{3,2}(2)|\leq 2.5926$ | $b_{3,3}(3)\geq 0.79$

$\det(B_{3})\geq\prod_{i=1}^{3}b_{i,i}(i)\geq 0.73.$

The bounds on final values of $B_{4}$ are:

$b_{1,1}(1)=1$ | $|b_{1,2}(1)|\leq 0.015625$ | $|b_{1,3}(1)|\leq 0.00057871$ | $|b_{1,4}(1)|\leq 0.000073$
---|---|---|---
$|b_{2,1}(1)|\leq 2.0$ | $b_{2,2}(2)\geq 0.96875$ | $|b_{2,3}(2)|\leq 0.01678241$ | $|b_{2,4}(2)|\leq 0.00072338$
$|b_{3,1}(1)|\leq 16.0$ | $|b_{3,2}(2)|\leq 2.25$ | $b_{3,3}(3)\geq 0.95$ | $|b_{3,4}(3)|\leq 0.018463$
$|b_{4,1}(1)|\leq 432.0$ | $|b_{4,2}(2)|\leq 22.75$ | $|b_{4,3}(3)|\leq 2.645$ | $b_{4,4}(4)\geq 0.9$

$\det(B_{4})\geq\prod_{i=1}^{4}b_{i,i}(i)\geq 0.83.$

##  Appendix B Rank $r\leq d$

In this section, we prove Theorem 2. Consider a matroid
$\mathcal{M}=([n],\mathcal{I})$ with rank $r\leq d$. Starting with a basis $S$
with non-zero volume, we will use a slight modification of Algorithm 2 to
iteratively find a basis with strictly larger volume. However since the set
$S$ is not full dimensional, our edge weight functions will be different.

Let $S=\\{v_{1},v_{2},\ldots,v_{r}\\}$ be a basis of $\mathcal{M}$ with
$\operatorname{vol}(S)>0$. We can write any vector $u_{i}$ in $\mathcal{M}$ as

$u_{i}=\sum_{j=1}^{r}a_{i,j}v_{j}+u_{i}^{\perp},$

where $u_{i}^{\perp}$ is orthogonal to $\operatorname{Span}(S)$.

The change in volume on replacing some $v\in S$ by $u\notin S$ is given by

$\frac{\operatorname{vol}(S-u+v)}{\operatorname{vol}(S)}=\sqrt{a_{uv}^{2}+\frac{\left\lVert
u^{\perp}\right\rVert^{2}}{\left\lVert v^{\perp}\right\rVert^{2}}},$ (17)

where $v^{\perp}$ is the component of $v$ orthogonal to
$\operatorname{Span}(S-v)$. The two terms in equation (17) have geometric
meanings. Let us decompose $u$ into $u^{\perp}+u^{\parallel}$, where
$u^{\perp}$ is the component of $u$ orthogonal to $\operatorname{Span}(S)$.
Then $|a_{uv}|$ is exactly the change in the volume if we project $u$ to
$\operatorname{Span}(S)$ before replacing $v$, i.e.,
$|a_{uv}|=\frac{\operatorname{vol}(S-v+u^{\parallel})}{\operatorname{vol}(S)}$,
and $\frac{\left\lVert u^{\perp}\right\rVert}{\left\lVert
v^{\perp}\right\rVert}$ is the change in the volume if we project $u$
orthogonal to $\operatorname{Span}(S)$ before replacing $v$, i.e.,
$\frac{\left\lVert u^{\perp}\right\rVert}{\left\lVert
v^{\perp}\right\rVert}=\frac{\operatorname{vol}(S-v+u^{\perp})}{\operatorname{vol}(S)}$.
So, we augment the exchange graph to reflect this.

Like Lemma 5, when $\mathrm{sym}_{r}(S)<\mathrm{sym}_{r}(OPT)\cdot
r^{-\Omega(r)}$, we can find an $\tilde{f}$-violating cycle (for an
appropriate function $\tilde{f}$) in the augmented exchange graph.

However unlike Lemma 7, the change in the objective induced by a cycle $C$ in
the augmented graph is not a simple function of the weights of chords and arcs
of $C$. To get around this issue, we use the geometric relation between
$\mathrm{sym}_{r}$ and $\operatorname{vol}$, specifically the subadditivity of
$\operatorname{vol}$ to relate $\mathrm{sym}_{r}$ to the chord and arc weights
of $C$.

We define the exchange graph $G(S)$ exactly as Definition 1 with
$w_{0}(u_{i},v_{j})=-\log(|a_{i,j}|)$. Our approach to find a basis with
larger volume is to first try to exchange on an $f$-violating cycle in $G(S)$.
Like Algorithm 1, exchanging on an $f$-violating cycle implies increase in
volume. Unlike Algorithm 1, failure to find an $f$-violating cycle does not
imply that the volume of the current solution is close to optimal. So, we move
to Stage 2, where we work with an augmented version of the exchange graph
defined below.

We decompose every vector $u_{i}$ in $\mathcal{M}$ as

$u_{i}=u_{i}^{\parallel}+u_{i}^{\perp},$

where $u_{i}^{\parallel}\in\operatorname{Span}(S)$ and $u_{i}^{\perp}$ is
orthogonal to $\operatorname{Span}(S)$.

In the augmented exchange graph $\widetilde{G}(S)$, for every vector
$u_{i}\in\mathcal{M}$, we create two vertices $u_{i}^{\parallel}$ (called a
parallel vertex) and $u_{i}^{\perp}$ (called a perpendicular vertex) in the
left-hand side.

######  Definition 6 (Augmented Exchange Graph)

For a subset of vectors $S=\\{v_{1},v_{2},\ldots,v_{r}\\}$, we define the
augmented exchange graph of $S$, denoted by $\widetilde{G}(S)$ as a bipartite
graph, where the right-hand side consists of vectors in $S$, i.e.,
$R=\\{v_{1},v_{2},\ldots,v_{r}\\}$ and the left-hand side consists of all the
vectors $L=\bigcup_{u\in U\backslash S}\\{u_{i}^{\perp},u_{i}^{\parallel}\\}$.
For each $v_{i}\in R$, if $S-v_{i}+u\in\mathcal{I}$, then $v_{i}$ has an edge
to $u^{\perp}$ and an edge to $u^{\parallel}$. The vertices on the left-hand
side have forward edges to every vertex in $S$ ( See figure Figure 4).

Figure 4: The augmented exchange graph $\widetilde{G}(S)$(An exchange cycle is
shown in bold edges)

Each vector $v_{j}\in S$ can be decomposed as $v_{j}=\sum_{i\neq
j}\alpha_{j,i}v_{i}+v_{j}^{\perp}$, where $v_{j}^{\perp}$ is orthogonal to the
span of $S\backslash\\{v_{j}\\}$. We will call $v_{j}^{\perp}$ the orthogonal
component of $v_{j}$ and use it to define edge weights in $\widetilde{G}(S)$.

######  Definition 7 (Weight functions on the Augmented Exchange graph)

All the arcs from some vertex in $R$ to some vertex in $L$, have weight $0$.
The weights of the forward arcs are defined as

  * •

for every parallel vertex $u_{i}^{\parallel}\in L$, the weight of the arc
$u_{i}^{\parallel}\rightarrow v_{j}$ is

$\widetilde{w}_{0}(u_{i}^{\parallel}\rightarrow v_{j}):=-\log(|a_{i,j}|),$

  * •

for every perpendicular vertex $u_{i}^{\perp}\in L$, the weight of the arc
$u_{i}^{\perp}\rightarrow v_{j}$ is

$\widetilde{w}_{0}(u_{i}^{\perp}\rightarrow
v_{j}):=-\log\left(\frac{\left\lVert u_{i}^{\perp}\right\rVert}{\left\lVert
v_{j}^{\perp}\right\rVert}\right).$

We define a family of weight functions on the exchange graph. To define these
weights we use the new function $\tilde{f}(i)=(i!)^{11}$ if $i\geq 2$ and
$\tilde{f}(1)=2$. Now we define the weight function $\widetilde{w}_{\ell}$
analogously to $w_{\ell}$, i.e., all backward arcs still have weight $0$ but
every forward edge $(u,v)$ has weight

$\widetilde{w}_{\ell}(u,v):=\frac{\log(\tilde{f}(\ell))}{\ell}+\widetilde{w}_{0}(u,v).$

###### Observation 2

For a current solution $S$, let $\widetilde{\mathcal{M}}(S)$ be the matroid
obtained from $\mathcal{M}$ by adding an element parallel to every $u\in
U\backslash S$, and labelling the pair $u^{\perp}$, $u^{\parallel}$. Then the
subgraph of $\widetilde{G}(S)$ induced by edges with finite weight is the
matroid exchange graph where $\mathcal{M}_{1}=\widetilde{\mathcal{M}}(S)$, and
$\mathcal{M}_{2}$ is the linear matroid on $S\cup\bigcup_{u\in U\backslash
S}\\{u^{\perp},u^{\parallel}\\}$.

By construction, no independent set in $\widetilde{\mathcal{M}}(S)$ contains
both $u^{\perp}$ and $u^{\parallel}$, for any $u\in U\backslash S$. Thus, if
$\widetilde{\mathcal{I}}$ is an independent set in
$\widetilde{\mathcal{M}}(S)$ and $\mathcal{I}$ is obtained from
$\widetilde{\mathcal{I}}$ by replacing each instance of $u^{\perp}$, or
$u^{\parallel}$ with the original element $u\in U\backslash S$, then
$\mathcal{I}$ is independent in $\mathcal{M}$.

Similar to Lemma 3, a function of $\widetilde{w}_{0}(u_{i}^{\parallel},v_{j})$
and $\widetilde{w}_{0}(u_{i}^{\perp},v_{j})$ measures the change in objective
when we replace element $v_{j}$ by $u_{i}$.

###### Lemma 10

Let $S$ be a solution with $\operatorname{vol}(S)>0$ and $u\not\in S$ with
$u=u^{\parallel}+u^{\perp}$. Then for any $v\in S$, we have
$\sqrt{e^{-2\widetilde{w}_{0}(u^{\parallel},v)}+e^{-2\widetilde{w}_{0}(u^{\perp},v)}}=\frac{\operatorname{vol}\left(S-u+v\right)}{\operatorname{vol}(S)}$.

Our algorithm works in 2 stages. In the first stage, we try to find an
$f$-violating cycle in the exchange graph $G(S)$. If the algorithm finds such
a cycle, it exchanges on it. If no $f$-violating cycle is found, we move to
the augmented exchange graph $\widetilde{G}(S)$, and search for an
$\tilde{f}$-violating cycle in $\widetilde{G}(S)$. If no such cycle is found
in Stage 2, then Lemma 12 guarantees that $\operatorname{vol}(S)\geq
e^{-O(r\log(r))}\cdot\operatorname{vol}(OPT)$.

Algorithm 4 Algorithm to find an approximation to $OPT$

$S\leftarrow$ basis with $\operatorname{vol}(S)>0$.

Let $f(i)=2(i!)^{3}$ and $\tilde{f}(i)=(i!)^{11}$

while There exists an $f$-violating cycle in $G(S)$ or an
$\tilde{f}$-violating cycle in $\widetilde{G}(S)$ do

if There exists an $f$-violating cycle in $G(S)$ then

Stage 1:

$C=$ minimal $f$-violating cycle in $G(S)$

$S=S\Delta C$

else

Stage 2:

$C=$ minimal $\tilde{f}$-violating cycle in $\widetilde{G}(S)$

$\widetilde{C}=\\{u\in[n]\backslash S:u^{\perp}\text{ or }u^{\parallel}\in
C\\}\cup\\{v\in S:v\in C\\}$

$S=S\Delta\widetilde{C}$

end if

end while

Return $S$

###### Lemma 11

If Algorithm 4 finds an $f$-violating cycle, $C$, in $G(S)$, then
$\operatorname{vol}(S\Delta C)\geq 2\cdot\operatorname{vol}(S)$.

Proof  Let $C^{\prime}$ be the projection of $C$ onto
$\operatorname{Span}(S)$. By Lemma 20, we know that
$\operatorname{vol}(S\Delta C)\geq\operatorname{vol}(S\Delta C^{\prime})$, and
by Lemma 7, we know that $\operatorname{vol}(S\Delta C^{\prime})\geq
2\cdot\operatorname{vol}(S)$. Therefore,

$\operatorname{vol}(S\Delta C)\geq\operatorname{vol}(S\Delta C^{\prime})\geq
2\cdot\operatorname{vol}(S),$

which concludes the proof of the Lemma. $\Box$

From hereafter we analyze the case when Algorithm 4 does not find an
$f$-violating cycle in Stage 1, moves on to Stage 2 and finds an
$\tilde{f}$-violating cycle in $\widetilde{G}(S)$.

###  B.1 Existence of $\tilde{f}$-violating cycle

To guarantee we make progress at every iteration, we need to ensure there will
always be an $\tilde{f}$-violating cycle, whenever our current volume is far
from the optimal volume. Before we prove the existence of an
$\tilde{f}$-violating cycle, we state a couple of useful observations.

For convenience, to specify the volume of a set of vectors
$\\{v_{1},v_{2},\ldots,v_{r}\\}$, instead of writing
$\operatorname{vol}(\\{v_{1},v_{2},\ldots,v_{r}\\})$, we use
$\operatorname{vol}(v_{1},v_{2},\ldots,v_{r})$.

###### Observation 3

For any set of vectors $\\{v_{1}^{a},v_{1}^{b},v_{2},\dots,v_{r}\\}$,

$\displaystyle\operatorname{vol}(v_{1}^{a}+v_{1}^{b},v_{2},\dots,v_{r})$
$\displaystyle\leq\operatorname{vol}(v_{1}^{a},v_{2},\dots,v_{r})+\operatorname{vol}(v_{1}^{b},v_{2},\dots,v_{r})\,,$
$\displaystyle\operatorname{vol}(v_{1}^{a}+v_{1}^{b},v_{2},\dots,v_{r})$
$\displaystyle\geq\operatorname{vol}(v_{1}^{a},v_{2},\dots,v_{r})-\operatorname{vol}(v_{1}^{b},v_{2},\dots,v_{r})\,.$

Proof  Let $P^{\perp}$ be the projection matrix orthogonal to
$\operatorname{Span}(v_{2},\dots,v_{r})$. By triangle inequality, we have that

$\displaystyle\left\lVert P^{\perp}(v_{1}^{a}+v_{1}^{b})\right\rVert$
$\displaystyle\leq\left\lVert P^{\perp}v_{1}^{a}\right\rVert+\left\lVert
P^{\perp}v_{1}^{b}\right\rVert,\text{ and }$ $\displaystyle\left\lVert
P^{\perp}(v_{1}^{a}+v_{1}^{b})\right\rVert$ $\displaystyle\geq\left\lVert
P^{\perp}v_{1}^{a}\right\rVert-\left\lVert P^{\perp}v_{1}^{b}\right\rVert.$

Since $\operatorname{vol}(v_{1}^{a},v_{2},\dots,v_{r})=\left\lVert
P^{\perp}v_{1}^{a}\right\rVert\cdot\operatorname{vol}(v_{2},\dots,v_{r})$,
multiplying both sides by $\operatorname{vol}(v_{2},\dots,v_{r})$ gives us the
required inequalities. $\Box$

###### Observation 4

If $v_{i}^{\perp}$ is the orthogonal projection of $v_{i}$ onto
$\operatorname{Span}(S-v_{i})$, then

$\displaystyle\operatorname{vol}(v_{1},\dots,v_{k})\cdot\prod_{i=k+1}^{r}\left\lVert
v_{i}^{\perp}\right\rVert\leq\operatorname{vol}(v_{1},\dots,v_{r})$

for any $k\in[r]$.

Proof  Let $S_{i}=\\{v_{1},\dots,v_{i}\\}$ for $i\in[r]$ and
$S_{0}=\emptyset$. Since
$\operatorname{vol}(v_{1},\dots,v_{r})=\prod_{i=1}^{r}\frac{\operatorname{vol}(S_{i})}{\operatorname{vol}(S_{i-1})}$
where $vol(\emptyset)=1$, it suffices to prove that
$\frac{\operatorname{vol}(S_{i})}{\operatorname{vol}(S_{i-1})}\geq\left\lVert
v_{i}^{\perp}\right\rVert=\frac{\operatorname{vol}(S)}{\operatorname{vol}(S\backslash\\{v_{i}\\})}$
which follows from the submodularity of $\log\operatorname{vol}(\cdot)$ as
$S_{i-1}\subseteq S\backslash\\{v_{i}\\}$. $\Box$

The following lemma is an extension to Lemma 5 when the current solution has
$r\leq d$ vectors.

###### Lemma 12

For any basis $S\in\mathcal{I}$ with $\operatorname{vol}(S)>0$, if
$\operatorname{vol}(OPT)>\operatorname{vol}(S)\cdot r^{2r}\cdot\tilde{f}(r)$,
then there exists an $\tilde{f}$-violating cycle in $\widetilde{G}(S)$.

Proof  Since $S$ and $OPT$ are independent and $|S|=|OPT|$, there exists a
perfect matching between $OPT\backslash S$ and $S\backslash OPT$ using the
backward arcs in $G(S)$ (Chapter 39, Corollary 39.12a, [Sch03]). Let
$X=OPT\backslash S$, $Y=S\backslash OPT$, and $|X|=|Y|=\ell$. Without loss of
generality, let $Y=\\{v_{1},\ldots,v_{\ell}\\}$ and
$X=\\{u_{1},\ldots,u_{\ell}\\}$ such that $(v_{i}\rightarrow u_{i})$ is an arc
in $G(S)$ for all $i\in[\ell]$. Let $Z=OPT\cap
S=\\{v_{\ell+1},\ldots,v_{r}\\}$ and let us use $T$ instead of $OPT$ for ease
of notation.

From the hypothesis of the lemma, we have

$\displaystyle
r^{2r}\cdot\tilde{f}(r)\leq\frac{\operatorname{vol}(T)}{\operatorname{vol}(S)}$
$\displaystyle=\frac{\operatorname{vol}(X\cup Z)}{\operatorname{vol}(Y\cup
Z)}.$ (18)

Since $u_{i}=\sum_{j=1}^{r}a_{i,j}v_{j}+u_{i}^{\perp}$, we can decompose each
vector $u_{i}$ into a sum of $r+1$ vectors, i.e.,
$u_{i}=\sum_{j=0}^{r}u_{i}^{(j)}$ where

  * •

$u_{i}^{(0)}:=u_{i}^{\perp}$ for all $i$, and

  * •

$u_{i}^{(j)}:=a_{i,j}v_{j}\,$.

Now using Observation 3, we can expand $\operatorname{vol}(T)$ as

$\displaystyle\frac{\operatorname{vol}(T)}{\operatorname{vol}(S)}$
$\displaystyle\leq\sum_{i_{1},i_{2},\ldots,i_{\ell}\in\\{0,\ldots,r\\}}\frac{\operatorname{vol}(\\{u_{1}^{(i_{1})},\,u_{2}^{(i_{2})},\ldots,\,u_{\ell}^{(i_{\ell})}\\}\cup
Z)}{\operatorname{vol}(S)}.$ (19)

If $i_{j}>\ell$ for any $j$, then $u_{j}^{(i_{j})}$ and the vectors in set $Z$
are linearly dependent and therefore the volume is $0$. So we can restrict
ourselves to the case when $i_{j}\in\\{0,\ldots,\ell\\}$ for all $j\in[\ell]$.

For any permutation $\sigma\in\mathcal{S}_{\ell}$, define
$\mathcal{F}(\sigma):=\\{(i_{1},i_{2},\ldots,i_{\ell}):i_{j}\in\\{\sigma(j),0\\}\\}$.
Since $u_{i_{1}}^{(j)}$ and $u_{i_{2}}^{(j)}$ are linearly dependent whenever
$j>0$, we can rewrite $\operatorname{vol}(T)$ as

$\displaystyle\operatorname{vol}(T)$
$\displaystyle\leq\sum_{\tau\in\bigcup_{\sigma}\mathcal{F}(\sigma)}\operatorname{vol}(\\{u_{1}^{(\tau_{1})},\,u_{2}^{(\tau_{2})},\ldots,\,u_{\ell}^{(\tau_{\ell})}\\}\cup
Z)$
$\displaystyle\leq\sum_{\sigma\in\mathcal{S}_{\ell}}\sum_{\tau\in\mathcal{F}(\sigma)}\operatorname{vol}(\\{u_{1}^{(\tau_{1})},\,u_{2}^{(\tau_{2})},\ldots,\,u_{\ell}^{(\tau_{\ell})}\\}\cup
Z)\,.$ (20)

We will upper bound
$\operatorname{vol}(\\{u_{1}^{(\tau_{1})},\,u_{2}^{(\tau_{2})},\ldots,\,u_{\ell}^{(\tau_{\ell})}\\}\cup
Z)$ for each $\tau$ separately. As an illustration for a fixed $\sigma$, let
us consider $\tau=(0,\ldots,0,\sigma(k+1),\ldots,\sigma(\ell))$. The
corresponding volume term is equal to

$\frac{\operatorname{vol}(\\{u_{1}^{(0)},\dots,u_{k}^{(0)},u_{k+1}^{(\tau_{k+1})},\dots,u_{\ell}^{(\tau_{\ell})}\\}\cup
Z)}{\operatorname{vol}(S)}=\frac{\operatorname{vol}(u_{1}^{(0)},\dots,u_{k}^{(0)})\cdot\operatorname{vol}(\\{u_{k+1}^{(\tau_{k+1})},\dots,u_{\ell}^{(\tau_{\ell})}\\}\cup
Z)}{\operatorname{vol}(S)}\,,$

as the sets of vectors $\\{u_{1}^{(0)},\dots,u_{k}^{(0)}\\}$ and
$\\{u_{k+1}^{(\tau_{k+1})},\dots,u_{\ell}^{(\tau_{\ell})}\\}\cup Z$ are
orthogonal to each other. Upper bounding
$\operatorname{vol}(u_{1}^{(0)},\dots,u_{k}^{(0)})$ by
$\prod_{i=1}^{k}\left\lVert u_{i}^{\perp}\right\rVert$, we get

$\displaystyle\frac{\operatorname{vol}(\\{u_{1}^{(0)},\dots,u_{k}^{(0)},u_{k+1}^{(\tau_{k+1})},\dots,u_{\ell}^{(\tau_{\ell})}\\}\cup
Z)}{\operatorname{vol}(S)}\leq\left(\prod_{i=1}^{k}\left\lVert
u_{i}^{\perp}\right\rVert\right)\cdot\frac{\operatorname{vol}(\\{u_{k+1}^{(\tau_{k+1})},\dots,u_{\ell}^{(\tau_{\ell})}\\}\cup
Z)}{\operatorname{vol}(S)}\,.$

To bound
$\operatorname{vol}(\\{u_{k+1}^{(\tau_{k+1})},\dots,u_{\ell}^{(\tau_{\ell})}\\}\cup
Z)$, consider

$\displaystyle\frac{\operatorname{vol}(\\{u_{k+1}^{(\tau_{k+1})},\dots,u_{\ell}^{(\tau_{\ell})}\\}\cup
Z)}{\operatorname{vol}(S)}$
$\displaystyle=\frac{\operatorname{vol}(\\{a_{k+1,\tau_{k+1}}v_{\tau_{k+1}},\ldots,a_{\ell,\tau_{\ell}}v_{\tau_{\ell}}\\}\cup
Z)}{\operatorname{vol}(S)}$
$\displaystyle=\left(\prod_{i=k+1}^{\ell}|a_{i\tau_{i}}|\right)\frac{\operatorname{vol}(\\{v_{\sigma(k+1)},\dots,v_{\sigma(\ell)}\\}\cup
Z)}{\operatorname{vol}(S)}\,.$ (since $\tau_{j}=\sigma(j)$ for $k<j\leq\ell$)

Using 4,

$\frac{\operatorname{vol}(\\{v_{\sigma(k+1)},\dots,v_{\sigma(\ell)}\\}\cup
Z)}{\operatorname{vol}(S)}\leq\prod_{j\in[\ell]\backslash\\{\sigma(k+1),\ldots,\sigma(\ell)\\}}\frac{1}{\left\lVert
v_{j}^{\perp}\right\rVert}=\prod_{j\in\\{\sigma(1),\ldots,\sigma(k)\\}}\frac{1}{\left\lVert
v_{j}^{\perp}\right\rVert}\,.$

Continuing the above chain of inequalities,

$\displaystyle\frac{\operatorname{vol}(\\{u_{k+1}^{(\tau_{k+1})},\dots,u_{\ell}^{(\tau_{\ell})}\\}\cup
Z)}{\operatorname{vol}(S)}$
$\displaystyle\leq\left(\prod_{i=k+1}^{\ell}|a_{i\tau_{i}}|\right)\cdot\prod_{j\in\\{\sigma(1),\ldots,\sigma(k)\\}}\frac{1}{\left\lVert
v_{j}^{\perp}\right\rVert}\cdot\prod_{i=1}^{k}\left\lVert
u_{i}^{\perp}\right\rVert$
$\displaystyle=\left(\prod_{i=k+1}^{\ell}|a_{i\tau_{i}}|\right)\cdot\left(\prod_{i=1}^{k}\frac{\left\lVert
u_{i}^{\perp}\right\rVert}{\left\lVert
v_{\sigma(i)}^{\perp}\right\rVert}\right)\;.$

Now consider any $\tau\in\mathcal{F}(\sigma)$, and let
$I_{\tau}^{0}:=\\{j:\tau(j)=0\\}$ and $I_{\tau}^{\sigma}=[\ell]\backslash
I_{\tau}^{0}$. Then following a similar chain of proof as above, we get

$\frac{\operatorname{vol}(\\{u_{1}^{(\tau_{1})},\dots,\dots,u_{\ell}^{(\tau_{\ell})}\\}\cup
Z)}{\operatorname{vol}(S)}\leq\left(\prod_{i\in
I_{\tau}^{\sigma}}|a_{i\sigma(i)}|\right)\cdot\left(\prod_{i\in
I_{\tau}^{0}}\frac{\left\lVert u_{i}^{\perp}\right\rVert}{\left\lVert
v_{\sigma(i)}^{\perp}\right\rVert}\right)\,.$

Summing over all $\tau\in\mathcal{F}(\sigma)$,

$\displaystyle\sum_{\tau\in\mathcal{F}(\sigma)}\frac{\operatorname{vol}(\\{u_{1}^{(\tau_{1})},\dots,\dots,u_{r}^{(\tau_{r})}\\}\cup
Z)}{\operatorname{vol}(S)}$
$\displaystyle\leq\sum_{\tau\in\mathcal{F}(\sigma)}\left(\prod_{i\in
I_{\tau}^{\sigma}}|a_{i\sigma(i)}|\right)\left(\prod_{i\in
I_{\tau}^{0}}\frac{\left\lVert u_{i}^{\perp}\right\rVert}{\left\lVert
v_{\sigma(i)}^{\perp}\right\rVert}\right)$
$\displaystyle=\sum_{\tau\in\mathcal{F}(\sigma)}\left(\prod_{i\in
I_{\tau}^{\sigma}}e^{-\tilde{w}_{0}(u_{i}^{\parallel},v_{\sigma(i)})}\right)\left(\prod_{i\in
I_{\tau}^{0}}e^{-\tilde{w}_{0}(u_{i}^{\perp},v_{\sigma(i)})}\right)\,.$

Summing over all permutations,

$\displaystyle
r^{2r}\cdot\tilde{f}(r)\leq\frac{\operatorname{vol}(T)}{\operatorname{vol}(S)}$
$\displaystyle\leq\sum_{\sigma\in\mathcal{S}_{\ell}}\sum_{\tau\in\mathcal{F}(\sigma)}\left(\prod_{i\in
I_{\tau}^{\sigma}}e^{-\tilde{w}_{0}(u_{i}^{\parallel},v_{\sigma(i)})}\right)\left(\prod_{i\in
I_{\tau}^{0}}e^{-\tilde{w}_{0}(u_{i}^{\perp},v_{\sigma(i)})}\right).$

The RHS is sum of $2^{\ell}\ell!$ positive terms. So, there exists some
permutation $\sigma\in\mathcal{S}_{\ell}$ and $\tau\in\mathcal{F}(\sigma)$
such that

$\left(\prod_{i\in
I_{\tau}^{\sigma}}e^{-\tilde{w}_{0}(u_{i}^{\parallel},v_{\sigma(i)})}\right)\left(\prod_{i\in
I_{\tau}^{0}}e^{-\tilde{w}_{0}(u_{i}^{\perp},v_{\sigma(i)})}\right)\geq\frac{r^{2r}\cdot\tilde{f}(r)}{2^{\ell}\ell!}\geq\tilde{f}(r)\,.$

Let the cycle decomposition of $\sigma=\\{\pi_{1},\pi_{2},\ldots,\pi_{k}\\}$
with $\pi_{i}=\\{j_{1},j_{2},\ldots,j_{x_{i}}\\}$. For each vector $u_{i}$, we
define symbols $p_{i}$ indicating whether $u_{i}$ is present as a
perpendicular vector in $\tau$, i.e., $p_{i}=\parallel$ if $i\in
I_{\tau}^{\sigma}$ and $p_{i}=\perp$ otherwise.

Then each cyclic permutation $\pi_{i}$ corresponds to a cycle $C_{i}$ in
$\widetilde{G}(S)$ given by

$C_{i}=(u_{j_{1}}^{p_{j_{1}}}\rightarrow v_{j_{2}}\rightarrow
u_{j_{2}}^{p_{j_{2}}}\rightarrow v_{j_{3}}\ldots
u_{j_{x_{i}}}^{p_{j_{x_{i}}}}\rightarrow v_{j_{1}}\rightarrow
u_{j_{1}}^{p_{j_{1}}}),$

and for every $i\in[k]$, $\left(\prod_{j\in
I_{\tau}^{\sigma}\cap\pi_{i}}e^{-\tilde{w}_{0}(u_{j}^{\parallel},v_{\sigma(j)})}\right)\cdot\left(\prod_{j\in
I_{\tau}^{0}\cap\pi_{i}}e^{-\tilde{w}_{0}(u_{j}^{\perp},v_{\sigma(j)})}\right)=e^{-\tilde{w}_{0}(C_{i})}$
and therefore,

$\left(\prod_{i\in
I_{\tau}^{\sigma}}e^{-\tilde{w}_{0}(u_{i}^{\parallel},v_{\sigma(i)})}\right)\cdot\left(\prod_{i\in
I_{\tau}^{0}}e^{-\tilde{w}_{0}(u_{i}^{\perp},v_{\sigma(i)})}\right)=\prod_{i=1}^{k}e^{-\tilde{w}_{0}(C_{i})}\geq\tilde{f}(r).$
(21)

At least one of the $C_{i}$’s must be an $\tilde{f}$-violating cycle. If not,
then $e^{-\tilde{w}_{0}(C_{i})}\leq\tilde{f}(|C_{i}|/2)$ and

$\left(\prod_{i\in
I_{\tau}^{\sigma}}e^{-\tilde{w}_{0}(u_{i}^{\parallel},v_{\sigma(i)})}\right)\left(\prod_{i\in
I_{\tau}^{0}}e^{-\tilde{w}_{0}(u_{i}^{\perp},v_{\sigma(i)})}\right)=\prod_{i=1}^{k}e^{-\tilde{w}_{0}(C_{i})}\leq\prod_{i=1}^{k}\tilde{f}(|C_{i}|/2)\leq\tilde{f}(r),$
(22)

where the last inequality follows from $\sum_{i=1}^{k}|C_{i}|=2\ell\leq 2r$.
Equation (22) contradicts (21), so there exist $i$ such that $C_{i}$ is an
$\tilde{f}$-violating cycle in $\widetilde{G}(S)$. $\Box$

###  B.2 Analysis of Stage 2

In this section, we prove that if the algorithm finds an $\tilde{f}$-violating
cycle in Stage 2, then exchanging on this cycle increases the volume by a
constant factor. However, since the algorithm fails to find a cycle in Stage
1, a cycle in Stage 2 must contain a perpendicular vertex. We first bound the
number of vertices a minimal $\tilde{f}$-violating cycle can contain, and use
this fact to prove that exchanging on such a cycle increases the volume.

###### Lemma 13

If $C$ is a minimal $\tilde{f}$-violating cycle in $\widetilde{G}(S)$ and
$\widetilde{C}=\\{u\in[n]\backslash S:u^{\perp}\text{ or }u^{\parallel}\in
C\\}\cup\\{v\in S:v\in C\\}$, then $S\Delta\widetilde{C}$ is independent in
$\mathcal{M}$.

Proof  Observation 2 and Lemma 9 imply that $S\Delta\widetilde{C}$ is
independent in $\widetilde{\mathcal{M}}(S)$, and the second part of Observatio
2 then implies that $S\Delta\widetilde{C}$ is independent in $\mathcal{M}$.
$\Box$

To make our later calculations possible, we first prove that any minimal
$\tilde{f}$-violating cycle in $\widetilde{G}(S)$ contains exactly one
perpendicular vector. The following lemma is slightly more general than we
need now, but will be useful later.

###### Lemma 14

Let $C$, $|C|=2y$ be a cycle in $\widetilde{G}(S)$ such that there are no
$\tilde{f}$-violating cycles with less than $2y$ hops in $\widetilde{G}(S)$.
Let $C$ contain $k\geq 2$ perpendicular vertices
$u_{1}^{\perp},u_{2}^{\perp},\ldots,u_{k}^{\perp}$ such that the section of
$C$ from $u_{i}^{\perp}$ to $u_{(i\;\mathrm{mod}\;k)+1}^{\perp}$ has $2x_{i}$
hops for $i\in[k]$. Then

$e^{-\tilde{w}_{0}(C)}\leq\prod_{i=1}^{k}\tilde{f}(x_{i}).$

Proof  The proof is by induction on $k>1$. Let the perpendicular vertices
$u_{1}^{\perp},u_{2}^{\perp},\ldots,u_{k}^{\perp}$ appear in order along
around $C$. Let $C^{\prime}$ and $C^{\prime\prime}$ be the two cycles created
by replacing the edges $u_{1}^{\perp}\rightarrow v_{1}$ and
$u_{2}^{\perp}\rightarrow v_{2}$ with the new edges $u_{1}^{\perp}\rightarrow
v_{2}$ and $u_{2}^{\perp}\rightarrow v_{1}$, so that $C^{\prime}$ is the cycle
containing $u_{1}^{\perp}$. Note that $C^{\prime}$ has $2y-2x_{1}<2y$ hops and
$C^{\prime\prime}$ has $2x_{1}<2y$ hops. So by the hypothesis of the Lemma,
both $C^{\prime}$ and $C^{\prime\prime}$ are not $\tilde{f}$-violating.

Additionally,

$\tilde{w}_{0}(u_{1}^{\perp}\rightarrow
v_{2})+\tilde{w}_{0}(u_{2}^{\perp}\rightarrow
v_{1})=-\log\left(\frac{\|u_{1}^{\perp}\|\|u_{2}^{\perp}\|}{\|v_{1}^{\perp}\|\|v_{2}^{\perp}\|}\right)=\tilde{w}_{0}(u_{1}^{\perp}\rightarrow
v_{1})+\tilde{w}_{0}(u_{2}^{\perp}\rightarrow v_{2}),$

and therefore

$e^{-\tilde{w}_{0}(C)}=e^{-\tilde{w}_{0}(C^{\prime})-\tilde{w}_{0}(C^{\prime\prime})}.$
(23)

When $k=2$, both cycles $C^{\prime}$ and $C^{\prime\prime}$ contain exactly
one perpendicular vertex, and since they are not $\tilde{f}$-violating,
$e^{-\tilde{w}_{0}(C^{\prime})}\leq\tilde{f}(2y-2x_{1})$ and
$e^{-\tilde{w}_{0}(C^{\prime\prime})}\leq\tilde{f}(2x_{1})$.

Using equation (23), we conclude that
$e^{-\tilde{w}_{0}(C)}=e^{-\tilde{w}_{0}(C^{\prime})-\tilde{w}_{0}(C^{\prime\prime})}\leq\tilde{f}(2y-2x_{1})\cdot\tilde{f}(x_{1})$,
as desired.

When $k>2$ the cycle $C^{\prime}$ has $k-1\geq 2$ perpendicular vertices since
it no longer contains $u_{2}^{\perp}$. Thus, the induction hypothesis implies
that $e^{-\tilde{w}_{0}(C^{\prime})}\leq\prod_{i=2}^{k}\tilde{f}(x_{i})$.
Since $C^{\prime\prime}$ is not $\tilde{f}$-violating, it satisfies
$e^{-\tilde{w}_{0}(C^{\prime\prime})}\leq\tilde{f}(2x_{1})$.

Again using equation (23), we conclude that
$e^{-\tilde{w}_{0}(C)}=e^{-\tilde{w}_{0}(C^{\prime})-\tilde{w}_{0}(C^{\prime\prime})}\leq\prod_{i=1}^{k}\tilde{f}(x_{i})$,
as desired. $\Box$

When $y=\sum_{i=1}^{k}x_{i}$, we know that
$\tilde{f}(y)\geq\prod_{i=1}^{k}\tilde{f}(x_{i})$. Thus, we obtain the
following corollary:

###### Corollary 1

If $C$ is a minimal $\tilde{f}$-violating cycle in $\widetilde{G}(S)$, then
$C$ contains exactly one perpendicular vector.

Now we will prove that for a minimal $\tilde{f}$-violating cycle $C$, the
volume of $S\Delta C$ is strictly larger than $\operatorname{vol}(S)$.

###### Lemma 15

If $C$ is a minimal $\tilde{f}$-violating cycle in $\widetilde{G}(S)$, then
$\operatorname{vol}(S\Delta C)\geq 2\cdot\operatorname{vol}(S)$.

Proof  If $|C|=2$, then let $C=(u^{\perp}\rightarrow v)$. Since $C$ is an
$\tilde{f}$-violating cycle, $e^{-\tilde{w}_{0}(C)}=\frac{\left\lVert
u^{\perp}\right\rVert}{\left\lVert v^{\perp}\right\rVert}>\tilde{f}(1)\geq 2$.
By Lemma 10,

$\frac{\operatorname{vol}(S-v+u)}{\operatorname{vol}(S)}=\sqrt{a_{uv}^{2}+\frac{\left\lVert
u^{\perp}\right\rVert^{2}}{\left\lVert v^{\perp}\right\rVert^{2}}}\geq
e^{-\tilde{w}_{0}(C)}\geq 2.$

This concludes the proof when $C$ has $2$ arcs.

Now consider the case when $C$ has at least $4$ arcs. By Corollary 1, we can
assume that $C$ contains exactly one perpendicular vertex. Let
$C=(u_{1}^{\perp}\rightarrow v_{1}\rightarrow u_{2}^{\parallel}\rightarrow
v_{2}\rightarrow\ldots u_{\ell}^{\parallel}\rightarrow v_{\ell}\rightarrow
u_{1}^{\perp})$, where $\ell\geq 2$, $v_{i}\in S$, and $v_{i}\rightarrow
u_{i+1}$ is an arc in $G(S)$.

Define $T:=S\Delta C$, $X:=C\backslash S=\\{u_{1},u_{2},\ldots,u_{\ell}\\}$,
and $Y:=S\cap C=\\{v_{1},v_{2},\ldots,v_{\ell}\\}$, and let $S\backslash
Y=\\{v_{\ell+1},\ldots,v_{r}\\}$. Let $\mathbf{P}$ denote the projection
matrix orthogonal to the span of $S\backslash Y$.

Then

$\displaystyle\frac{\operatorname{vol}(T)}{\operatorname{vol}(S)}=\frac{\operatorname{vol}(\\{S\backslash
Y\\}\cup X)}{\operatorname{vol}(\\{S\backslash Y\\}\cup
Y)}=\frac{\operatorname{vol}(u_{1},u_{2},\ldots,u_{\ell},v_{\ell+1},\ldots,v_{r})}{\operatorname{vol}(v_{1},v_{2},\ldots,v_{\ell},v_{\ell+1},\ldots,v_{r})}\,.$

Note that for any set of vectors $\\{x_{1},\ldots,x_{\ell}\\}$,

$\operatorname{vol}(x_{1},x_{2},\ldots,x_{\ell},v_{\ell+1},\ldots,v_{r})=\operatorname{vol}(\mathbf{P}x_{1},\mathbf{P}x_{2},\ldots,\mathbf{P}x_{\ell})\cdot\operatorname{vol}(v_{\ell+1},\ldots,v_{r}).$

Applying this to the sets $X$ and $Y$, we get

$\displaystyle\frac{\operatorname{vol}(T)}{\operatorname{vol}(S)}=\frac{\operatorname{vol}(\mathbf{P}u_{1},\mathbf{P}u_{2},\ldots,\mathbf{P}u_{\ell})}{\operatorname{vol}(\mathbf{P}v_{1},\mathbf{P}v_{2},\ldots,\mathbf{P}v_{\ell})}=\frac{\operatorname{vol}(\mathbf{P}X)}{\operatorname{vol}(\mathbf{P}Y)}\;.$

By definition, $u_{i}=\sum_{j=1}^{r}a_{i,j}v_{j}+u_{i}^{\perp}$. Taking the
projection of $u_{i}$ orthogonal to $\operatorname{Span}(S\backslash Y)$, we
get $\mathbf{P}u_{i}=\sum_{j=1}^{\ell}a_{i,j}\mathbf{P}v_{j}+u_{i}^{\perp}$,
since $Pv_{j}=0$ for all $j>\ell$. So we can decompose each vector
$\mathbf{P}u_{i}$ into a sum of $\ell+1$ vectors, i.e.,
$\mathbf{P}u_{i}=\sum_{j=0}^{\ell}u_{i}^{(j)}$ where

  * •

$u_{i}^{(0)}:=u_{i}^{\perp}$ for all $i$, and

  * •

$u_{i}^{(j)}:=a_{i,j}\mathbf{P}v_{j}$.

Note that for any $i_{1},i_{2}\in[\ell]$, the vectors $u_{i_{1}}^{(j)}$ and
$u_{i_{2}}^{(j)}$ are linearly dependent for any $j>0$.

Let $I_{C}$ denote the tuple $(0,2,3,\ldots,\ell)$. Using Observation 3, we
can lower bound $\operatorname{vol}(\mathbf{P}X)$ as

$\operatorname{vol}(\mathbf{P}X)\geq\operatorname{vol}(\,u_{1}^{(0)},\,u_{2}^{(2)},\ldots,\,u_{\ell}^{(\ell)})\;-\sum_{\begin{subarray}{c}i_{1},i_{2},\ldots,i_{\ell}\in\\{0,1,\dots,\ell\\}\\\
(i_{1},i_{2},\ldots,i_{\ell})\neq
I_{C}\end{subarray}}\operatorname{vol}(\,u_{1}^{(i_{1})},\,u_{2}^{(i_{2})},\ldots,\,u_{\ell}^{(i_{\ell})})\,.$
(24)

For any permutation $\sigma\in\mathcal{S}_{\ell}$, define
$\mathcal{F}(\sigma):=\\{(i_{1},i_{2},\ldots,i_{\ell}):i_{j}\in\\{\sigma(j),0\\}\\}$.
Since $u_{i_{1}}^{(j)}$ and $u_{i_{2}}^{(j)}$ are linearly dependent, we can
rewrite (24) as

$\displaystyle\operatorname{vol}(\mathbf{P}X)$
$\displaystyle\geq\operatorname{vol}(\,u_{1}^{(0)},\,u_{2}^{(2)},\ldots,\,u_{\ell}^{(\ell)})\;-\sum_{\tau\in\bigcup_{\sigma}\mathcal{F}(\sigma)\backslash
I_{C}}\operatorname{vol}(\,u_{1}^{(\tau_{1})},\,u_{2}^{(\tau_{2})},\ldots,\,u_{\ell}^{(\tau_{\ell})})$
$\displaystyle\geq\operatorname{vol}(\,u_{1}^{(0)},\,u_{2}^{(2)},\ldots,\,u_{\ell}^{(\ell)})\;-\sum_{\sigma\in
S_{\ell}}\sum_{\tau\in\mathcal{F}(\sigma)\backslash
I_{C}}\operatorname{vol}(\,u_{1}^{(\tau_{1})},\,u_{2}^{(\tau_{2})},\ldots,\,u_{\ell}^{(\tau_{\ell})})\,.$
(25)

For a fixed $\sigma\neq id_{\ell}$ and some $\tau\in\mathcal{F}(\sigma)$, let
$I_{\tau}^{0}:=\\{j\in[\ell]:\tau(j)=0\\}$ and
$I_{\tau}^{\sigma}:=[\ell]\backslash I_{\tau}^{0}$. Also, let
$X_{\tau}=\\{v_{\sigma(i)}:i\in I_{\tau}^{\sigma}\\}$. Then

$\displaystyle\frac{\operatorname{vol}(\,u_{1}^{(\tau_{1})},\,u_{2}^{(\tau_{2})},\ldots,\,u_{\ell}^{(\tau_{\ell})})}{\operatorname{vol}(\mathbf{P}Y)}$
$\displaystyle=\frac{\operatorname{vol}\left(\bigcup_{i\in
I_{\tau}^{0}}\,\\{u_{i}^{\perp}\\}\right)\cdot\operatorname{vol}\left(\bigcup_{i\in
I_{\tau}^{\sigma}}\,\\{a_{i,\sigma(i)}\mathbf{P}v_{\sigma(i)})\\}\right)}{\operatorname{vol}(\mathbf{P}Y)}$
$\displaystyle\leq\prod_{i\in I_{\tau}^{0}}\left\lVert
u_{i}^{\perp}\right\rVert\cdot\prod_{i\in
I_{\tau}^{\sigma}}|a_{i,\sigma(i)}|\cdot\frac{\operatorname{vol}\left(\bigcup_{i\in
I_{\tau}^{\sigma}}\,\\{\mathbf{P}v_{\sigma(i)})\\}\right)}{\operatorname{vol}(\mathbf{P}Y)}$
$\displaystyle\leq\prod_{i\in I_{\tau}^{0}}\left\lVert
u_{i}^{\perp}\right\rVert\cdot\prod_{i\in
I_{\tau}^{\sigma}}|a_{i,\sigma(i)}|\cdot\frac{1}{\prod_{i\in
I_{\tau}^{0}}\left\lVert v_{\sigma(i)}^{\perp}\right\rVert}$ (from Observation
4) $\displaystyle=\prod_{i\in I_{\tau}^{0}}\frac{\left\lVert
u_{i}\right\rVert}{\left\lVert
v^{\perp}_{\sigma(i)}\right\rVert}\cdot\prod_{i\in
I_{\tau}^{\sigma}}|a_{i,\sigma(i)}|=\prod_{i\in
I_{\tau}^{0}}e^{-\tilde{w}_{0}(u_{i}^{\perp},v_{\sigma(i)})}\cdot\prod_{i\in
I_{\tau}^{\sigma}}e^{-\tilde{w}_{0}(u_{i}^{\parallel},v_{\sigma(i)})}\,.$

Summing over all tuples $\tau\in\mathcal{F}(\sigma)$, we get

$\displaystyle\sum_{\tau\in\mathcal{F}(\sigma)}\frac{\operatorname{vol}(\,u_{1}^{(\tau_{1})},\,u_{2}^{(\tau_{2})},\ldots,\,u_{\ell}^{(\tau_{\ell})})}{\operatorname{vol}(\mathbf{P}Y)}$
$\displaystyle\leq\prod_{i\in
I_{\tau}^{0}}e^{-\tilde{w}_{0}(u_{i}^{\perp},v_{\sigma(i)})}\cdot\prod_{i\in
I_{\tau}^{\sigma}}e^{-\tilde{w}_{0}(u_{i}^{\parallel},v_{\sigma(i)})}$
$\displaystyle=\prod_{i=1}^{\ell}\left(e^{-\tilde{w}_{0}(u_{i}^{\perp},v_{\sigma(i)})}+e^{-\tilde{w}_{0}(u_{i}^{\parallel},v_{\sigma(i)})}\right)\,.$
(26)

Let $W_{C}\in\mathbb{R}^{\ell\times\ell}$ be a matrix with
$[W_{C}]_{i,j}=e^{-\tilde{w}_{0}(u_{i}^{\perp},v_{\sigma(i)})}+e^{-\tilde{w}_{0}(u_{i}^{\parallel},v_{\sigma(i)})}$.
Then we can rewrite (26) as

$\displaystyle\sum_{\tau\in\mathcal{F}(\sigma)}\frac{\operatorname{vol}(\,u_{1}^{(\tau_{1})},\,u_{2}^{(\tau_{2})},\ldots,\,u_{\ell}^{(\tau_{\ell})})}{\operatorname{vol}(\mathbf{P}Y)}$
$\displaystyle\leq\prod_{i=1}^{\ell}[W_{C}]_{i,\sigma(i)}\,.$ (27)

Similarly, the sum of tuples for the identity permutation $id_{\ell}$ gives

$\displaystyle\frac{\operatorname{vol}(\,u_{1}^{(0)},\,u_{2}^{(2)},\ldots,\,u_{\ell}^{(\ell)})}{\operatorname{vol}(\mathbf{P}Y)}$
$\displaystyle+\sum_{\tau\in\mathcal{F}(id_{\ell})\backslash
I_{C}}\frac{\operatorname{vol}(\,u_{1}^{(\tau_{1})},\,u_{2}^{(\tau_{2})},\ldots,\,u_{\ell}^{(\tau_{\ell})})}{\operatorname{vol}(\mathbf{P}X)}\leq\prod_{i=1}^{\ell}[W_{C}]_{i,i}\,.$
(28)

Plugging equation (27) and equation (28) in (25), we get

$\displaystyle\frac{\operatorname{vol}(\mathbf{P}X)}{\operatorname{vol}(\mathbf{P}Y)}$
$\displaystyle\geq\frac{\operatorname{vol}(\,u_{1}^{(0)},\,u_{2}^{(2)},\ldots,\,u_{\ell}^{(\ell)})}{\operatorname{vol}(\mathbf{P}Y)}-\sum_{\sigma\neq{id}}\prod_{i=1}^{\ell}[W_{C}]_{i,\sigma(i)}-\left(\prod_{i=1}^{\ell}[W_{C}]_{i,i}-\frac{\operatorname{vol}(\,u_{1}^{(0)},\,u_{2}^{(2)},\ldots,\,u_{\ell}^{(\ell)})}{\operatorname{vol}(\mathbf{P}Y)}\right)$
$\displaystyle=\frac{2\operatorname{vol}(\,u_{1}^{(0)},\,u_{2}^{(2)},\ldots,\,u_{\ell}^{(\ell)})}{\operatorname{vol}(\mathbf{P}Y)}-\sum_{\sigma\neq{id}}\prod_{i=1}^{\ell}[W_{C}]_{i,\sigma(i)}-\prod_{i=1}^{\ell}[W_{C}]_{i,i}$
$\displaystyle=\frac{2\operatorname{vol}(\,u_{1}^{(0)},\,u_{2}^{(2)},\ldots,\,u_{\ell}^{(\ell)})}{\operatorname{vol}(\mathbf{P}Y)}-\operatorname{perm}(W_{C})\,.$
(29)

From Lemma 16, we have

$\operatorname{perm}(W_{C})\leq 1.56\cdot\frac{\left\lVert
u_{1}^{\perp}\right\rVert}{\left\lVert
v_{1}^{\perp}\right\rVert}\cdot\prod_{i=2}^{\ell}|a_{i,i}|\,.$ (30)

Note that

$\frac{\operatorname{vol}(\,u_{1}^{(0)},\,u_{2}^{(2)},\ldots,\,u_{\ell}^{(\ell)})}{\operatorname{vol}(\mathbf{P}Y)}=\frac{\left\lVert
u_{1}^{\perp}\right\rVert}{\left\lVert
v_{1}^{\perp}\right\rVert}\cdot\prod_{i=2}^{\ell}|a_{i,i}|\,.$ (31)

Inserting the bounds from (30) and (31) in (29) gives

$\displaystyle\frac{\operatorname{vol}(\mathbf{P}X)}{\operatorname{vol}(\mathbf{P}Y)}$
$\displaystyle\geq\frac{\left\lVert u_{1}^{\perp}\right\rVert}{\left\lVert
v_{1}^{\perp}\right\rVert}\cdot\prod_{i=2}^{\ell}|a_{i,i}|\cdot(2-1.56)=0.44\cdot\frac{\left\lVert
u_{1}^{\perp}\right\rVert}{\left\lVert
v_{1}^{\perp}\right\rVert}\cdot\prod_{i=2}^{\ell}|a_{i,i}|\,.$

Since $C$ is an $\tilde{f}$-Violating cycle,
$e^{-\tilde{w}_{0}(C)}=\frac{\left\lVert
u_{1}^{\perp}\right\rVert}{\left\lVert
v_{1}^{\perp}\right\rVert}\cdot\prod_{i=2}^{\ell}|a_{i,i}|\geq\tilde{f}(\ell)$.
Therefore,

$\displaystyle\frac{\operatorname{vol}(S\Delta
C)}{\operatorname{vol}(S)}=\frac{\operatorname{vol}(\mathbf{P}X)}{\operatorname{vol}(\mathbf{P}Y)}$
$\displaystyle\geq 0.44\cdot\tilde{f}(\ell)\geq 2\,.$

$\Box$

###  B.3 Miscellaneous Lemmas

###### Lemma 16

Let $C=(v_{0}\rightarrow u^{\perp}_{1}\rightarrow v_{1}\rightarrow
u^{\parallel}_{2}\rightarrow v_{2}\rightarrow\ldots
u^{\parallel}_{\ell}\rightarrow v_{0})$ be a minimal $\tilde{f}$-violating
cycle in $\widetilde{G}(S)$ with $\ell\geq 2$ and let $W_{C}$ be a matrix with
$[W_{C}]_{i,j}=|a_{i,j}|+\frac{\left\lVert
u_{i}^{\perp}\right\rVert}{\left\lVert v_{j}^{\perp}\right\rVert}$, then

$\operatorname{perm}(W_{C})\leq 1.56\cdot\frac{\left\lVert
u_{1}^{\perp}\right\rVert}{\left\lVert
v_{1}^{\perp}\right\rVert}\cdot\prod_{i=2}^{\ell}|a_{i,i}|\,.$

Proof  Define $z_{1}:=\frac{\left\lVert u_{1}^{\perp}\right\rVert}{\left\lVert
v_{1}^{\perp}\right\rVert}$, $p_{1}=\perp$, and $z_{i}:=|a_{i,i}|$,
$p_{i}=\parallel$ for all $i\geq 2$.

We show upper bounds on the absolute value of each entry of $W_{C}$ as a
function of $z_{i}$’s. Consider the $i,j$-th entry of $W_{C}$. For $i>j$, let
$C_{i,j}^{\perp}:=(u_{i}^{\perp}\rightarrow v_{j}\rightarrow
u_{j+1}^{p_{j+1}}\rightarrow v_{j+1}\rightarrow\ldots v_{i-1}\rightarrow
u_{i}^{\perp})$. $C_{i,j}^{\perp}$ is a cycle of with $2(i-j)$ hops and
$V(C_{i,j}^{\perp})\subset V(C)$. $C$ being a minimal $\tilde{f}$-violating
cycle implies that $C_{i,j}^{\perp}$ is not an $\tilde{f}$-violating cycle.
Therefore, $e^{-\tilde{w}_{0}(C_{i,j}^{\perp})}=\frac{\left\lVert
u_{i}^{\perp}\right\rVert}{\left\lVert
v_{j}^{\perp}\right\rVert}\cdot\prod_{s=j+1}^{i-1}z_{s}<\tilde{f}(i-j)$. This
implies

$\frac{\left\lVert u_{i}^{\perp}\right\rVert}{\left\lVert
v_{j}^{\perp}\right\rVert}<\frac{\tilde{f}(i-j)}{\prod_{s=j+1}^{i-1}z_{s}}\,.$
(32)

Similarly for $j=\ell$, we have $\frac{\left\lVert
u_{i}^{\perp}\right\rVert}{\left\lVert
v_{0}^{\perp}\right\rVert}<\frac{\tilde{f}(i)}{\prod_{s=1}^{i-1}z_{s}}\,.$

Similarly, let $C_{i,j}^{\parallel}:=(u_{i}^{\parallel}\rightarrow
v_{j}\rightarrow u_{j+1}^{p_{j+1}}\rightarrow v_{j+1}\rightarrow\ldots
v_{i-1}\rightarrow u_{i}^{\parallel})$. Again, using the fact that
$C_{i,j}^{\parallel}$ is not $\tilde{f}$-Violating we get

$|a_{i,j}|<\frac{\tilde{f}(i-j)}{\prod_{s=j+1}^{i-1}z_{s}}\,,$ (33)

for any $i>j$ and for $j=\ell$, we have
$a_{i,0}<\frac{\tilde{f}(i)}{\prod_{s=1}^{i-1}z_{s}}\,.$

For $i<j<\ell$, let $C^{\perp}_{i,j}:=(v_{0}\rightarrow
u_{1}^{p_{i}}\rightarrow v_{1}\rightarrow\ldots u_{i}^{\perp}\rightarrow
v_{j}\rightarrow\ldots u_{\ell}^{p_{\ell}}\rightarrow v_{0})$. Again,
$C^{\perp}_{i,j}$ is a cycle with $2(\ell-j+i)$ hops and which is not
$\tilde{f}$-violating. Therefore,

$\frac{\left\lVert u_{i}^{\perp}\right\rVert}{\left\lVert
v_{j}^{\perp}\right\rVert}\cdot\prod_{s=1}^{i-1}z_{s}\cdot\prod_{s=j+1}^{\ell}z_{s}<\tilde{f}(\ell-j+i).$
(34)

Since $C$ is an $\tilde{f}$-violating cycle, we also have

$e^{-\tilde{w}_{0}(C)}=\prod_{s=1}^{\ell}z_{s}>\tilde{f}(\ell)\,.$ (35)

Combining (34) and (35) gives

$\displaystyle\frac{\left\lVert u_{i}^{\perp}\right\rVert}{\left\lVert
v_{j}^{\perp}\right\rVert}$
$\displaystyle<\frac{\tilde{f}(\ell-j+i)}{\tilde{f}(\ell)}\cdot\prod_{s=i}^{j}z_{s}\,.$

Similarly, for $i<j<\ell$,

$\displaystyle|a_{i,j}|$
$\displaystyle<\frac{\tilde{f}(\ell-j+i)}{\tilde{f}(\ell)}\cdot\prod_{s=i}^{j}z_{s}\,.$

Define $x_{1}:=(|a_{1,1}|+\frac{\left\lVert
u_{1}^{\perp}\right\rVert}{\left\lVert
v_{1}^{\perp}\right\rVert})/\frac{\left\lVert
u_{1}^{\perp}\right\rVert}{\left\lVert v_{1}^{\perp}\right\rVert}$ and
$x_{i}:=(|a_{i,i}|+\frac{\left\lVert u_{i}^{\perp}\right\rVert}{\left\lVert
v_{i}^{\perp}\right\rVert})/|a_{i,i}|$ for $i\geq 2$. Then $x_{i}\geq 1$ and
the $i$-th diagonal entry of $W_{C}$ is $x_{i}\cdot z_{i}$.

Let $B_{\ell}$ be the matrix obtained by applying the following operations to
$W_{C}$

  * •

Multiply the last column by $z_{1}$ and for $j>1$, divide the $j$-th column by
$\prod_{s=2}^{j}z_{s}$

  * •

Divide the first row by $z_{1}$ and for $i>1$, multiply the $i$-th row by
$\prod_{s=2}^{i-1}z_{s}$

  * •

Divide the last column by $\prod_{i=1}^{\ell}z_{i}$.

  * •

Divide the $j$-th column by $x_{j}$.

Then
$|\operatorname{perm}(W_{C})|=(\prod_{i=1}^{\ell}x_{i}z_{i})\cdot|\operatorname{perm}(B_{\ell})|$,
and $B_{\ell}$ satisfies the following properties:

  * •

$b_{i,i}$ = 1 for all $i\in[\ell]$,

  * •

$|b_{i,j}|\leq 2\cdot\tilde{f}(i-j)/x_{j}\leq 2\cdot\tilde{f}(i-j)$ for all
$j<i\leq\ell$, and

  * •

$|b_{i,j}|\leq 2\cdot\tilde{f}(\ell-j+i)/(\tilde{f}(\ell)x_{j})\leq
2\cdot\tilde{f}(\ell-j+i)/\tilde{f}(\ell)$ for all $i<j\leq\ell$.

If $\ell=1$, $\operatorname{perm}(B_{\ell})=1$ and for $\ell\geq 2$, Lemma 18
gives $\operatorname{perm}(B_{\ell})\leq 1.3$. Therefore, we have

$\operatorname{perm}(W_{C})\leq
1.3\cdot\prod_{i=1}^{\ell}x_{i}z_{i}=1.3\cdot\prod_{i=1}^{\ell}\left(|a_{i,i}|+\frac{\left\lVert
u_{i}^{\perp}\right\rVert}{\left\lVert v_{i}^{\perp}\right\rVert}\right)\leq
1.3\cdot 1.2\cdot\frac{\left\lVert u_{1}^{\perp}\right\rVert}{\left\lVert
v_{1}^{\perp}\right\rVert}\cdot\prod_{i=2}^{\ell}|a_{i,i}|=1.56\cdot
e^{-\tilde{w}_{0}(C)}\;,$

where the last inequality follows from Lemma 17. $\Box$

###### Lemma 17

If $C=(v_{0}\rightarrow u^{\perp}_{1}\rightarrow v_{1}\rightarrow
u^{\parallel}_{2}\rightarrow v_{2}\rightarrow\ldots
u^{\parallel}_{\ell}\rightarrow v_{0})$ is a minimal $\tilde{f}$-violating
cycle with $\ell\geq 2$, then

$\prod_{i=1}^{\ell}\left(|a_{i,i}|+\frac{\left\lVert
u_{i}^{\perp}\right\rVert}{\left\lVert v_{i}^{\perp}\right\rVert}\right)\leq
1.2\cdot e^{-\tilde{w}_{0}(C)}.$ (36)

Proof  Since $C$ is an $\tilde{f}$-violating cycle,

$e^{-\tilde{w}_{0}(C)}=\frac{\left\lVert
u_{1}^{\perp}\right\rVert}{\left\lVert
v_{1}^{\perp}\right\rVert}\cdot\prod_{i=2}^{\ell}|a_{i,i}|\geq\tilde{f}(\ell).$
(37)

Define $x_{i,0}:=\frac{\left\lVert u_{i}^{\perp}\right\rVert}{\left\lVert
v_{i}^{\perp}\right\rVert}$ and $x_{i,1}:=|a_{i,i}|$ for all $i\in[\ell]$.
Then we can decompose the LHS of (36) as follows:

$\displaystyle\prod_{i=1}^{\ell}\left(|a_{i,i}|+\frac{\left\lVert
u_{i}^{\perp}\right\rVert}{\left\lVert
v_{i}^{\perp}\right\rVert}\right)=\sum_{Z\subseteq[\ell]}\prod_{i\in
Z}x_{i,0}\cdot\prod_{i\notin Z}x_{i,1}=:\sum_{Z\subseteq[\ell]}w(Z),$

We now upper bound $w(Z)$ for all $Z\neq\\{1\\}$ based on the cardinality of
$Z$. For the empty set, i.e., $|Z|=0$, since Algorithm 4 did not return a
cycle in Stage 1, $w(Z)=\prod_{i=1}^{\ell}|a_{i,i}|=e^{-w_{0}(C)}\leq
f(\ell)$.

Consider a subset $Z$ with $|Z|=k$ where $k\geq 2$. We define a cycle $C_{Z}$
such that $C_{Z}$ contains the same arcs as $C$ but a vertex $u_{i}\in
C\backslash S$ is present as a perpendicular vertex in $C_{Z}$ if and only if
$u\in Z$. Then $w(Z)=e^{-\tilde{w}_{0}(C_{Z})}$. Let the distance between
successive perpendicular vertices in $C_{Z}$ be $b_{1},b_{2},\ldots,b_{k}$.
Then $\sum_{i=1}^{k}b_{i}=\ell$ and by Lemma 14,
$w(Z)=e^{-\tilde{w}_{0}(C_{Z})}\leq\prod_{i=1}^{k}\tilde{f}(b_{i})$.

Since $C_{Z}$ has the same structure as $C$, we can completely characterize
$C_{Z}$ by the first vertex among $u_{1},u_{2},\ldots,u_{\ell}$ which is
perpendicular, and the distances between successive perpendicular vertices in
$C_{Z}$, i.e., $b_{1},b_{2},\ldots,b_{k}$. There are only $\ell$ options for
the first perpendicular vertex. Therefore,

$\displaystyle\sum_{Z:|Z|=k}w(Z)\leq\ell\cdot\sum_{\begin{subarray}{c}\sum_{j=1}^{k}b_{j}=\ell\\\
b_{1},b_{2},\ldots,b_{k}\geq
1\end{subarray}}\prod_{i=1}^{k}\tilde{f}(b_{i})\leq\ell\cdot\binom{\ell-1}{k-1}\cdot\tilde{f}(\ell-k+1)\leq\frac{\tilde{f}(\ell)}{\ell^{8}}\,.$
(38)

For a subset with one element, i.e., $Z=\\{x\\}$, $x\neq 1$, $-\log w(Z)$ is
the same as the weight of the cycle

$C_{x}:=(v_{0}\rightarrow u_{1}^{\parallel}\rightarrow v_{1}\rightarrow\ldots
u_{x}^{\perp}\rightarrow v_{2}\rightarrow\ldots\rightarrow
u_{\ell}^{\parallel}\rightarrow v_{0})\,.$

Combining $C_{x}$ with $C$, we get two cycles

$\displaystyle C_{x}^{(1)}$ $\displaystyle=(v_{0}\rightarrow
u_{1}^{\perp}\rightarrow v_{1}\rightarrow\ldots u_{x}^{\perp}\rightarrow
v_{2}\rightarrow\rightarrow\ldots u_{\ell}^{\parallel}\rightarrow v_{0})$
$\displaystyle C_{x}^{(2)}$ $\displaystyle=(v_{0}\rightarrow
u_{1}^{\parallel}\rightarrow v_{1}\rightarrow\ldots
u_{x}^{\parallel}\rightarrow v_{2}\rightarrow\ldots\rightarrow
u_{\ell}^{\parallel}\rightarrow v_{0})\,,$

such that
$\tilde{w}_{0}(C)\cdot\tilde{w}_{0}(C_{x})=\tilde{w}_{0}(C_{x}^{(1)})\cdot\tilde{w}_{0}(C_{x}^{(2)}))$.
By Lemma 14, we know that
$e^{-\tilde{w}_{0}(C_{x}^{(1)})}\leq\tilde{f}(x-1)\tilde{f}(\ell-x+1)$. Also,
since $C_{x}^{(2)}$ only contains parallel vectors,
$\tilde{w}_{0}(C_{x}^{(2)})=w_{0}(C_{x}^{(2)})$; and since $C_{x}^{(2)}$ is
not $f$-violating, $e^{-\tilde{w}_{0}(C_{x}^{(2)})}\leq f(\ell)$. Therefore,
$e^{-\tilde{w}_{0}(C)-\tilde{w}_{0}(C_{x})}\leq\tilde{f}(x-1)\tilde{f}(\ell-x+1)\cdot
f(\ell)$. $C$ being $\tilde{f}$-violating implies
$e^{-\tilde{w}_{0}(C)}\geq\tilde{f}(\ell)$, and therefore
$e^{-\tilde{w}_{0}(C)}\leq\tilde{f}(x-1)\tilde{f}(\ell-x+1)f(\ell)/\tilde{f}(\ell)$.

Summing over all choices of $x$, we get

$\sum_{Z,|Z|=1}w(Z)=\sum_{x=2}^{\ell}e^{-\tilde{w}_{0}(C_{x})}\leq\sum_{x=2}^{\ell}\frac{\tilde{f}(x-1)\tilde{f}(\ell-x+1)f(\ell)}{\tilde{f}(\ell)}\leq\frac{4f(\ell)}{\ell}\,.$
(39)

Combining (37), (38), and (39), we get

$\displaystyle\prod_{i=1}^{\ell}\left(|a_{i,i}|+\frac{\left\lVert
u_{i}^{\perp}\right\rVert}{\left\lVert v_{i}^{\perp}\right\rVert}\right)$
$\displaystyle=\sum_{Z\subseteq[\ell]}w(Z)\leq
w(\emptyset)+\sum_{Z:|Z|=1}w(Z)+\sum_{Z:|Z|\geq 2}w(Z)$ $\displaystyle\leq
f(\ell)+e^{-\tilde{w}_{0}(C)}+\frac{4f(\ell)}{\ell}+\frac{\tilde{f}(\ell)}{\ell^{8}}\,.$

Since $e^{-\tilde{w}_{0}(C)}\geq\tilde{f}(\ell)\geq(\ell!)^{4}\cdot f(\ell)$,

$\displaystyle\prod_{i=1}^{\ell}\left(|a_{i,i}|+\frac{\left\lVert
u_{i}^{\perp}\right\rVert}{\left\lVert v_{i}^{\perp}\right\rVert}\right)$
$\displaystyle\leq
e^{-\tilde{w}_{0}(C)}\left(1+\frac{3}{(\ell!)^{4}}+\frac{1}{\ell^{8}}\right)\leq
1.2\cdot e^{-\tilde{w}_{0}(C)}.$

$\Box$

###### Lemma 18

Let $B_{\ell}\in\mathbb{R}^{\ell\times\ell}$ satisfy the following properties:

  * •

$b_{i,i}$ = 1 for all $i\in[\ell]$,

  * •

$0\leq b_{i,j}\leq 2\cdot\tilde{f}(i-j)$ for all $j<i\leq\ell$, and

  * •

$0\leq b_{i,j}\leq 2\cdot\tilde{f}(\ell-j+i)/\tilde{f}(\ell)$ for all
$i<j\leq\ell$.

Then the permanent of $B_{\ell}$ is at most $1.13$.

Proof  For $\ell=2$, $\operatorname{perm}(B_{2})=1+b_{1,2}\cdot b_{2,1}\leq
1+\frac{4\tilde{f}(1)^{2}}{\tilde{f}(2)}<1.1$.

Now, consider the case when $\ell\geq 3$. Let $id_{\ell}$ denote the identity
permutation on $\ell$ elements. Expanding the permanent of $B_{\ell}$ gives

$\operatorname{perm}(B_{\ell})=\sum_{\sigma\in\mathcal{S}_{\ell}}\prod_{i=1}^{\ell}b_{i,\sigma(i)}=1+\sum_{\sigma\in\mathcal{S}_{\ell}\backslash\\{id_{\ell}\\}}\prod_{i=1}^{\ell}b_{i,\sigma(i)}\,.$
(40)

We categorize all permutations in
$\mathcal{S}_{\ell}\backslash\\{id_{\ell}\\}$ based on the number of fixed
points and the number of exceedances. The set of fixed points of a permutation
$\sigma\in\mathcal{S}_{\ell}$ is defined as $\\{i\in[\ell]:\sigma(i)=i\\}$ and
the exceedance of $\sigma$ is defined to be the number of indices $i$ such
that $\sigma(i)>i$ (for more details, see Remark 1 and Lemma 19). Let
$\mathcal{S}_{\ell}(n,k)$ denote the subset of $\mathcal{S}_{\ell}$ with
$\ell-n$ fixed points and $k$ exceedances. Then

$|\mathcal{S}_{\ell}(n,k)|=\binom{\ell}{n}\cdot T(n,k),$

where $T(n,k)$ is the derangement number defined in Remark 1.

Since all permutations in $\mathcal{S}_{\ell}\backslash\\{id_{\ell}\\}$ have
at most $\ell-2$ fixed points and at least $1$ exceedance, we can further
expand (40) as

$\operatorname{perm}(B_{\ell})=1+\sum_{n=2}^{\ell}\;\sum_{k=1}^{n-1}\sum_{\sigma\in\mathcal{S}_{\ell}(n,k)}\prod_{i=1}^{\ell}b_{i,\sigma(i)}\,.$
(41)

For a permutation $\sigma\in\mathcal{S}_{\ell}(n,k)$,

$\prod_{i=1}^{\ell}b_{i,\sigma(i)}=\prod_{i>\sigma(i)}b_{i,\sigma(i)}\cdot\prod_{i<\sigma(i)}b_{i,\sigma(i)}\leq\prod_{i>\sigma(i)}2\tilde{f}(i-\sigma(i))\cdot\prod_{i<\sigma(i)}\frac{2\tilde{f}(\ell-\sigma(i)+i)}{\tilde{f}(\ell)}\,.$

where the last inequality follows from the hypothesis of the Lemma.

Since $\sum_{i=1}^{\ell}i-\sigma(i)=0$ for any permutation $\sigma$,
$\sum_{i>\sigma(i)}i-\sigma(i)+\sum_{i<\sigma(i)}\ell-\sigma(i)+i=\ell\cdot|\\{i:\sigma(i)>i\\}|=\ell\cdot
k$ for any $\sigma\in\mathcal{S}_{\ell}(n,k)$. Therefore, if
$\sigma\in\mathcal{S}_{\ell}(n,k)$, then there exist integers $1\leq
x_{1},x_{2},\ldots,x_{n}\leq n-1$ with $\sum_{i=1}^{n}x_{i}=\ell\cdot k$, such
that

$\displaystyle\prod_{i=1}^{\ell}b_{i,\sigma(i)}\leq
2^{n}\cdot\frac{\prod_{i=1}^{n}\tilde{f}(x_{i})}{\tilde{f}(\ell)^{k}}\,.$

Since $\tilde{f}$ satisfies $\tilde{f}(a+b)\geq\tilde{f}(a)\cdot\tilde{f}(b)$,
under the constraints on $x_{i}$’s, for any $k\geq n/2$,

$\displaystyle\prod_{i=1}^{\ell}b_{i,\sigma(i)}\leq
2^{n}\cdot\frac{\tilde{f}(\ell-1)^{k}\cdot\tilde{f}(2k-n+1)\cdot\tilde{f}(1)^{n-k-1}}{\tilde{f}(\ell)^{k}}\,,$

and for $k<n/2$,

$\displaystyle\prod_{i=1}^{\ell}b_{i,\sigma(i)}\leq
2^{n}\cdot\frac{\tilde{f}(\ell-1)^{k-1}\cdot\tilde{f}(\ell-n+2k-1)\cdot\tilde{f}(1)^{n-k}}{\tilde{f}(\ell)^{k}}\,.$

Using the definition of $\tilde{f}$, for any $k\geq n/2$,

$\displaystyle\prod_{i=1}^{\ell}b_{i,\sigma(i)}\leq
2^{2n-k-1}\cdot\frac{((2k-n+1)!)^{11}}{\ell^{11k}}\,,$ (42)

and for $k<n/2$,

$\displaystyle\prod_{i=1}^{\ell}b_{i,\sigma(i)}\leq
2^{2n-k}\cdot\frac{1}{\ell^{11(k-1)}\cdot(\ell\cdot(\ell-1)\ldots(\ell-n+2k))^{11}}\,.$
(43)

For some $k$ and $n$ with $k<n/2$, summing over all permutations in
$\mathcal{S}_{\ell}(n,k)$ gives

$\displaystyle\sum_{\sigma\in\mathcal{S}_{\ell}(n,k)}\prod_{i=1}^{\ell}b_{i,\sigma(i)}\leq\binom{\ell}{n}\cdot
T(n,k)\cdot
2^{2n-k}\cdot\frac{1}{\ell^{11(k-1)}\cdot(\ell\cdot(\ell-1)\ldots(\ell-n+2k))^{11}}\,.$
(44)

We will bound the three terms of equation (44), namely $\binom{\ell}{n}$,
$T(n,k)$, and $2^{2n-k}$ separately.

Expanding the first term, we get

$\displaystyle\binom{\ell}{n}\cdot\frac{1}{\ell^{(k-1)}\cdot(\ell\cdot(\ell-1)\ldots(\ell-n+2k))}=\frac{\ell\cdot(\ell-1)\ldots(\ell-n+1)}{n!\cdot\ell^{(k-1)}\cdot(\ell\cdot(\ell-1)\ldots(\ell-n+2k))}<\frac{1}{n!\cdot\ell^{k-1}}\,.$
(45)

For the third term, note that $k<n/2$ implies that $2^{2n-k}<2^{3n-3k}$, and
since $k\geq 1$, $\ell-n+2k>2$. Using these two facts, we get

$2^{2n-k}\cdot\frac{1}{\ell^{3(k-1)}\cdot(\ell\cdot(\ell-1)\ldots(\ell-n+2k))^{3}}<\frac{2^{3(n-k)}}{(\ell-n+2k)^{3(n-k)}}<1\,.$
(46)

Plugging (45) and (46) in (44), we get

$\displaystyle\sum_{\sigma\in\mathcal{S}_{\ell}(n,k)}\prod_{i=1}^{\ell}b_{i,\sigma(i)}\leq\frac{1}{n!\cdot\ell^{k-1}}\cdot
T(n,k)\cdot\frac{1}{\ell^{7(k-1)}\cdot(\ell\cdot(\ell-1)\ldots(\ell-n+2k))^{7}}\,.$
(47)

For $k=1$, $T(n,k)=1$ and therefore

$\displaystyle\sum_{\sigma\in\mathcal{S}_{\ell}(n,k)}\prod_{i=1}^{\ell}b_{i,\sigma(i)}$
$\displaystyle\leq\frac{1}{n!}\cdot\frac{1}{(\ell\cdot(\ell-1)\ldots(\ell-n+2))^{7}}\,.$
(48)

For any $2\leq k<n/2$, using Lemma 19, we have $T(n,k)\leq(2k+3)^{n}$. Since
$k\geq 2$, $2k+3\leq 2\cdot 2k$, and therefore $T(n,k)\leq(2\cdot 2k)^{n+2}$.
Plugging this is (47), we get

$\displaystyle\sum_{\sigma\in\mathcal{S}_{\ell}(n,k)}\prod_{i=1}^{\ell}b_{i,\sigma(i)}$
$\displaystyle\leq\frac{1}{n!\cdot\ell^{k-1}}\cdot(2k)^{n}\cdot
2^{n}\cdot\frac{1}{\ell^{7(k-1)}\cdot(\ell\cdot(\ell-1)\ldots(\ell-n+2k))^{7}}\,.$
(49)

Moreover $k<n/2$ implies that $n-k>n/2$, and as a result $n\leq 2(n-k)$ and
$2^{n}\cdot(2k)^{n}\leq 2^{2(n-k)}\cdot(2k)^{2(n-k)}$. Therefore,

$\displaystyle 2^{n}\cdot(2k)^{n}$
$\displaystyle\cdot\frac{1}{\ell^{4(k-1)}\cdot(\ell\cdot(\ell-1)\ldots(\ell-n+2k))^{4}}$
$\displaystyle<2^{2(n-k)}\cdot(2k)^{2(n-k)}\cdot\frac{1}{\ell^{4(k-1)}\cdot(\ell\cdot(\ell-1)\ldots(\ell-n+2k))^{4}}$
$\displaystyle<\frac{(2)^{2(n-k)}}{(\ell-n+2k)^{2(n-k)}}\cdot\frac{(2k)^{2(n-k)}}{(\ell-n+2k)^{2(n-k)}}<1,$
(50)

where the last inequality follows from $2k\leq\ell-n+2k$ and $2\leq\ell-n+2k$.

Combining (49) and (50), we have for any $2\leq k<n/2$,

$\sum_{\sigma\in\mathcal{S}_{\ell}(n,k)}\prod_{i=1}^{\ell}b_{i,\sigma(i)}\leq\frac{1}{n!\cdot\ell^{k-1}}\cdot\frac{1}{\ell^{3(k-1)}\cdot(\ell\cdot(\ell-1)\ldots(\ell-n+2k))^{3}}\,.$
(51)

For a fixed $k$ and $n$ with $k\geq n/2$, summing over all permutations in
$\mathcal{S}_{\ell}(n,k)$,

$\displaystyle\sum_{\sigma\in\mathcal{S}_{\ell}(n,k)}\prod_{i=1}^{\ell}b_{i,\sigma(i)}$
$\displaystyle\leq\binom{\ell}{n}\cdot T(n,k)\cdot
2^{2n-k-1}\cdot\frac{((2k-n+1)!)^{11}}{\ell^{11k}}\,.$ (52)

We will again bound the three terms, namely $\binom{\ell}{n}$, $T(n,k)$, and
$2^{2n-k-1}$ separately.

For the first term, since $n/2\leq k$, $2n-k-1\leq 3k-1$, and therefore

$\displaystyle 2^{2n-k-1}\cdot\frac{((2k-n+1)!)^{3}}{\ell^{3k}}$
$\displaystyle\leq 2^{3k-1}\cdot\frac{((2k-n+1)!)^{3}}{\ell^{3k}}\,.$

Since $2k-n+1\leq k$, and $k+1\leq\ell$,

$\displaystyle 2^{3k-1}\cdot\frac{((2k-n+1)!)^{3}}{\ell^{3k}}$
$\displaystyle\leq\frac{1}{2}\cdot\frac{(2^{k}\,k!)^{3}}{(k+1)^{3k}}\,.$

For $k=1,2,3,4,5$, $\frac{(2^{k}k!)^{3}}{(k+1)^{3k}}\leq 1$. For $k\geq 6$,
$2^{k}k!\leq k^{k}$. Therefore,

$\displaystyle 2^{2n-k-1}\cdot\frac{((2k-n+1)!)^{3}}{\ell^{3k}}$
$\displaystyle\leq\frac{1}{2}\,.$ (53)

Expanding the third term,

$\displaystyle\binom{\ell}{n}\cdot\frac{((2k-n+1)!)^{2}}{\ell^{2k}}$
$\displaystyle=\frac{\ell\cdot(\ell-1)\ldots(\ell-n+1)}{n!}\cdot\frac{((2k-n+1)!)^{2}}{\ell^{2k}}$
$\displaystyle\leq\frac{1}{n!}\cdot\frac{((2k-n+1)!)^{2}}{\ell^{2k-n}}=\frac{1}{\ell(n-1)!}\cdot\frac{((2k-n+1)!)^{2}}{n\ell^{2k-n-1}}\leq\frac{(2k-n+1)!}{\ell(n-1)!}\,.$

Since $k+1\leq n$, we have $2k-n+1\leq n-1$, and therefore

$\displaystyle\binom{\ell}{n}\cdot\frac{((2k-n+1)!)^{2}}{\ell^{2k}}$
$\displaystyle\leq\frac{(2k-n+1)!}{l(n-1)!}\leq\frac{1}{\ell}\,.$ (54)

Plugging in (53) and (54) in (52),

$\displaystyle\sum_{\sigma\in\mathcal{S}_{\ell}(n,k)}\prod_{i=1}^{\ell}b_{i,\sigma(i)}$
$\displaystyle\leq\frac{1}{2\ell}\cdot
T(n,k)\cdot\frac{((2k-n+1)!)^{6}}{\ell^{6k}}\,.$ (55)

Since $T(n,n-1)=1$, for $k=n-1$, we have

$\displaystyle\sum_{\sigma\in\mathcal{S}_{\ell}(n,k)}\prod_{i=1}^{\ell}b_{i,\sigma(i)}$
$\displaystyle\leq\frac{1}{2\ell}\cdot\frac{((n-1)!)^{6}}{\ell^{6(n-1)}}\,.$
(56)

By Lemma 19, for $k<n-1$, $T(n,k)\leq(2n-2k+5)^{n}$ for $k\geq n/2$, and

$\displaystyle\sum_{\sigma\in\mathcal{S}_{\ell}(n,k)}\prod_{i=1}^{\ell}b_{i,\sigma(i)}$
$\displaystyle\leq\frac{1}{2\ell}\cdot(2n-2k+5)^{n}\cdot\frac{((2k-n+1)!)^{6}}{\ell^{6k}}\,.$

Let $n=2k-z$, then

$\displaystyle(2n-2k+5)^{n}$
$\displaystyle\cdot\frac{((2k-n+1)!)^{6}}{\ell^{6k}}=(2k-2z+5)^{2k-z}\cdot\frac{((z+1)!)^{6}}{\ell^{6k}}$
$\displaystyle\leq(2k-z+5)^{2k-z}\cdot\frac{((z+1)!)^{6}}{\ell^{6k}}\,.$

Taking derivative of $\frac{(2k-z+7)^{2k-z+2}}{\ell^{6k}}$ with respect to
$k$,

$\displaystyle\frac{(2k-z+5)^{2k-z}}{\ell^{6k}}\left(2\cdot\log(2k-z+5)+2\cdot\frac{2k-z}{2k-z+5}-6\log(\ell)\right)\leq
0\,.$

Therefore $\frac{(2k-z+5)^{2k-z+2}}{\ell^{6k}}$ is a non-increasing function
of $k$. Since $n=2k-z\geq 1$, $k$ satisfies $2k\geq z+1$. So
$\frac{(2k-z+5)^{2k-z}}{\ell^{6k}}$ is maximized when $2k=z+1$. Therefore,

$\displaystyle(2k-z+5)^{2k-z}\cdot\frac{((z+1)!)^{6}}{\ell^{6k}}$
$\displaystyle\leq
6\cdot\frac{((z+1)!)^{6}}{\ell^{6k}}=6\cdot\frac{((2k-n+1)!)^{6}}{\ell^{6k}}\leq
6\cdot\frac{1}{\ell^{6(n-k-1)}}\,,$

where the last inequality follows from $2k-n+1\leq\ell$. Plugging this bound
in (55) gives

$\displaystyle\sum_{\sigma\in\mathcal{S}_{\ell}(n,k)}\prod_{i=1}^{\ell}b_{i,\sigma(i)}$
$\displaystyle\leq\frac{1}{2\ell}\cdot\frac{6}{\ell^{6(n-k-1)}}\,.$ (57)

Plugging in (48), (51), (56), and (57) into (41),

$\displaystyle\operatorname{perm}(B_{\ell})=$ $\displaystyle
1+\sum_{n=2}^{\ell}\sum_{k=1}^{n-1}\sum_{\sigma\in\mathcal{S}_{\ell}(n,k)}\prod_{i=1}^{\ell}b_{i,\sigma(i)}$
$\displaystyle=$ $\displaystyle
1+\sum_{n=2}^{\ell}\sum_{\sigma\in\mathcal{S}_{\ell}(n,1)}\prod_{i=1}^{\ell}b_{i,\sigma(i)}+\sum_{n=5}^{\ell}\sum_{2\leq
k<n/2}\sum_{\sigma\in\mathcal{S}_{\ell}(n,k)}\prod_{i=1}^{\ell}b_{i,\sigma(i)}$
$\displaystyle+\sum_{n=2}^{\ell}\sum_{\sigma\in\mathcal{S}_{\ell}(n,n-1)}\prod_{i=1}^{\ell}b_{i,\sigma(i)}+\sum_{n=2}^{\ell}\sum_{k=\lceil
n/2\rceil}^{n-2}\sum_{\sigma\in\mathcal{S}_{\ell}(n,k)}\prod_{i=1}^{\ell}b_{i,\sigma(i)}$
$\displaystyle\leq$ $\displaystyle
1+\sum_{n=2}^{\ell}\frac{1}{n!}\cdot\frac{1}{(\ell\cdot(\ell-1)\ldots(\ell-n+2))^{7}}$
$\displaystyle+\sum_{n=5}^{\ell}\sum_{2\leq
k<n/2}\frac{1}{n!\cdot\ell^{4(k-1)}\cdot(\ell\cdot(\ell-1)\ldots(\ell-n+2k))^{3}}$
$\displaystyle+\sum_{n=2}^{\ell}\frac{1}{2\ell}\cdot\frac{((n-1)!)^{6}}{\ell^{6(n-1)}}+\sum_{n=2}^{\ell}\sum_{k\geq
n/2}\frac{1}{2\ell}\cdot\frac{6}{\ell^{6(n-k-1)}}$ $\displaystyle\leq$
$\displaystyle
1+\frac{1}{\ell^{5}}+\frac{1}{\ell^{2}}+\frac{1}{2\ell^{6}}+\sum_{n=2}^{\ell}\frac{3}{\ell}\cdot\frac{1}{\ell^{6}-1}$
$\displaystyle\leq$ $\displaystyle
1+\frac{1}{\ell^{5}}+\frac{1}{\ell^{2}}+\frac{1}{2\ell^{6}}+\frac{3}{\ell^{6}-1}\leq
1.13\,,$

for $\ell\geq 3$. $\Box$

######  Remark 1 (Exceedances and the Eulerian Number)

For a permutation $\sigma\in\mathcal{S}_{n}$,

  * •

The exceedance of $\sigma$ is defined as $|\\{i\in[n-1]:\sigma(i)>i\\}|$.

  * •

The Eulerian number $E(n,k)$ is defined to be the number of permutations in
$\mathcal{S}_{n}$ with $k-1$ exceedances.

  * •

The derangement number $T(n,k)$ is defined to be the number of derangements in
$\mathcal{S}_{n}$ with $k$ exceedances.

The explicit formula for $E(n,k)$ is
$E(n,k)=\sum_{j=0}^{k+1}(-1)^{j}{\binom{n+1}{j}}\cdot(k+1-j)^{n}$ (page 273,
[Com74]). The exponential generating function of $E(n,k)$ is given by (page
273, [Com74])

$\sum_{n=0}^{\infty}\sum_{k=0}^{n}E(n,k)\;t^{k}\;\frac{x^{n}}{n!}=\frac{t-1}{t-e^{(t-1)x}}\,.$
(58)

The exponential generating function of $T(n,k)$ is given by (Proposition 5,
[Bre90])

$\sum_{n=0}^{\infty}\sum_{k=1}^{n-1}T(n,k)\;t^{k}\;\frac{x^{n}}{n!}=e^{-t}\cdot\frac{t-1}{t-e^{(t-1)x}}\,.$
(59)

Comparing (58) and (59), we infer

$T(n,k)=\sum_{j=0}^{n}(-1)^{(n-j)}\cdot\binom{n}{j}\cdot E(j,k)\,.$ (60)

###### Lemma 19

For any positive integer $n$,

  * •

$T(n,1)=T(n,n-1)=1$,

  * •

$T(n,k)=T(n,n+1-k)<(2k+3)^{n}$ for any $k\in\\{2,\ldots,n-2\\}$.

Proof  Since
$E(n,m)=\sum_{k=0}^{m+1}(-1)^{k}{\binom{n+1}{k}}\cdot(m+1-k)^{n}$, taking
absolute values, we get

$\displaystyle E(n,m)$
$\displaystyle<\binom{n+1}{0}\cdot(m+1)^{n}+\binom{n+1}{2}\cdot(m+1-2)^{n}+\ldots$
$\displaystyle<(m+1)^{n}\cdot\left(\sum_{i=0}^{n}\binom{n+1}{2i}\right)\leq(m+1)^{n}\cdot
2^{n}.$

Using equation 60 and taking absolute values, we get

$\displaystyle T(n,k)$ $\displaystyle<\sum_{j=0}^{n}\binom{n}{j}\cdot
E(j,k)<\sum_{j=0}^{n}\binom{n}{j}\cdot 2^{j}\cdot(k+1)^{j}=(1+2(k+1))^{n}.$

$\Box$

The following lemma is an extension to lemma 6.

###### Lemma 20

Let $S$ be a subset of $r<d$ vectors in $\mathbb{R}^{d}$. Let $C$ be a cycle
in $G(S)$, and let $X=C\backslash S$ and $Y=S\backslash C$ such that
$|X|=|Y|=\ell$. Let $X=YA_{C}+X_{\perp}$, where $X_{\perp}$ denotes the
projection of vectors in $X$ orthogonal to $\operatorname{Span}(Y)$. Then the
change in objective value is given by

$\frac{\operatorname{vol}(S\Delta
C)^{2}}{\operatorname{vol}(S)^{2}}\geq\det(A_{C}^{\top}A_{C}).$

In particular, if $C^{\prime}$ is the projection of the vectors in $C$ onto
$\operatorname{Span}(S)$, then $\operatorname{vol}(S\Delta
C)^{2}\geq\operatorname{vol}(S\Delta C^{\prime})^{2}$.

Proof  Let $W=S\backslash Y$. Let us abuse notation to denote by $X$ the
matrix whose columns are the vectors in set $X$ and similarly for other sets
defined above. Then let $X=YA_{C}+WA^{\prime}+Z$, where $Z$ is the component
of $X$ which is orthogonal to $\operatorname{Span}(S)$. Let
$Y=Y_{\perp}+Y_{W}$, where $Y_{\perp}$ is the component of $Y$ orthogonal to
$\operatorname{Span}(W)$.

Let $M$ denote the matrix whose columns are the elements of $S\Delta C$.
Concretely, $M=[X\,\,W]$ following the notation above. Note that

$\displaystyle\operatorname{vol}(S\Delta C)^{2}$
$\displaystyle=\det(M^{\top}M)=\det\left(\begin{bmatrix}X^{\top}\\\
W^{\top}\end{bmatrix}\begin{bmatrix}X&W\end{bmatrix}\right)=\det\left(\begin{bmatrix}X^{\top}X&X^{\top}W\\\
W^{\top}X&W^{\top}W\end{bmatrix}\right)$
$\displaystyle=\det\left(W^{\top}W\right)^{1/2}\det\left(X^{\top}X-X^{\top}W(W^{\top}W)^{-1}W^{\top}X\right),$
(61)

where the last equation follows from the fact that $M^{\top}M$ is positive
definite.

Now, since $Z$ is orthogonal to both $Y$ and $W$, we get

$X^{\top}X=(YA_{C})^{\top}(YA_{C})+(WA^{\prime})^{\top}(WA^{\prime})+Z^{\top}Z+(YA_{C})^{\top}(WA^{\prime})+(WA^{\prime})^{\top}(YA_{C}).$
(62)

Additionally, $W(W^{\top}W)^{-1}W^{\top}$ is the projection matrix on the
column space of $W$, so

$W(W^{\top}W)^{-1}W^{\top}X=Y_{W}A_{C}+WA^{\prime}\,.$ (63)

Multiplying equation (63) with $X$ gives

$X^{\top}W(W^{\top}W)^{-1}W^{\top}X=(YA_{C})^{\top}(Y_{W}A_{C})+(YA_{C})^{\top}(WA^{\prime})+(WA^{\prime})^{\top}(Y_{W}A_{C})+(WA^{\prime})^{\top}(WA^{\prime}).$
(64)

Subtracting equation (64) from equation (62), we see that

$\displaystyle X^{\top}X-X^{\top}W(W^{\top}W)^{-1}W^{\top}X$
$\displaystyle=(YA_{C})^{\top}(Y-Y_{W})A_{C}+(WA^{\prime})^{\top}(Y-Y_{W})A_{C}+Z^{\top}Z$
$\displaystyle=(Y_{\perp}A_{C})^{\top}(Y_{\perp}A_{C})+Z^{\top}Z.$

Substituting the value of $X^{\top}X-X^{\top}W(W^{\top}W)^{-1}W^{\top}X$ from
the above equation in equation (61), we conclude that

$\operatorname{vol}(S\Delta
C)^{2}=\det\left(W^{\top}W\right)\det\left((Y_{\perp}A_{C})^{\top}(Y_{\perp}A_{C})+Z^{\top}Z\right).$

Similarly,

$\displaystyle\operatorname{vol}(S)^{2}$
$\displaystyle=\det\left(\begin{bmatrix}Y^{\top}\\\
W^{\top}\end{bmatrix}\begin{bmatrix}Y&W\end{bmatrix}\right)=\det\left(\begin{bmatrix}Y^{\top}Y&Y^{\top}W\\\
W^{\top}Y&W^{\top}W\end{bmatrix}\right)$
$\displaystyle=\det\left(W^{\top}W\right)^{1/2}\det\left(Y^{\top}Y-Y^{\top}W(W^{\top}W)^{-1}W^{\top}Y\right)$
$\displaystyle=\det\left(W^{\top}W\right)^{1/2}\det\left(Y^{\top}Y-Y^{\top}Y_{W}\right)$
(65)
$\displaystyle=\det\left(W^{\top}W\right)^{1/2}\det\left(Y_{\perp}^{\top}Y_{\perp}\right).$
(66)

Finally, dividing equation (64) by equation (13) gives

$\frac{\operatorname{vol}(S\Delta
C)^{2}}{\operatorname{vol}(S)^{2}}=\frac{\det\left((Y_{\perp}A_{C})^{\top}(Y_{\perp}A_{C})+Z^{\top}Z\right)}{\det\left(Y_{\perp}^{\top}Y_{\perp}\right)}.$

Since $Z^{\top}Z$ is positive semidefinite, we conclude that

$\displaystyle\frac{\operatorname{vol}(S\Delta
C)^{2}}{\operatorname{vol}(S)^{2}}$
$\displaystyle=\frac{\det\left((Y_{\perp}A_{C})^{\top}(Y_{\perp}A_{C})+Z^{\top}Z\right)}{\det\left(Y_{\perp}^{\top}Y_{\perp}\right)}$
$\displaystyle\geq\frac{\det\left((Y_{\perp}A_{C})^{\top}(Y_{\perp}A_{C})\right)}{\det\left(Y_{\perp}^{\top}Y_{\perp}\right)}=\det(A_{C}^{\top}A_{C}).$

If $C^{\prime}$ is the projection of $C$ onto $\operatorname{Span}(S)$, then
Lemma 6 implies that $\operatorname{vol}(S\Delta
C^{\prime})^{2}=\operatorname{vol}(S)^{2}\cdot\det(A_{C}^{\top}A_{C})\leq\operatorname{vol}(S\Delta
C)^{2}$. $\Box$